Array Implementierung - Einfach verkettete Liste

[Skym0sh0]

volkard schrieb:

Den stl-containern kann man so ein Array auch als Allokator unterschubsen.

volkard, kannst du mir kurz mal in 1-2 sätzen erklären was ein allokator überhaupt ist?!?

[314159265358979]

Danke volkard, ich denke ich habe es jetzt verstanden.

Ein Allokator ist ein Objekt, dass dir deinen Speicher alloziert, auf welche Art auch immer.

[seldon]

Jetzt hat Volkard mir schon einiges vorweggenommen. Ja, genau das ist die Idee - es macht vor allem dann Sinn, wenn man zur Compilezeit grob abschätzen kann, wie viel man zur Laufzeit etwa benötigen kann und trotzdem eine Liste braucht. Ich sehe auch keinen Grund, den ersten Batzen nicht auf den Stack zu legen.

Dieser Ansatz ist bei kanonischen verketteten Listen etwas weniger sinnvoll als beispielsweise bei Vektoren - man verliert Teile der Listenfunktionalität (Splicing zwischen verschiedenen Containern). Ich kann mir aber vorstellen, dass man ihn beispielsweise auf Kantentänzer (dancing links) erweitern kann. Damit befinden wir uns im Dunstkreis von Backtracking-Algorithmen, mithin wieder bei der Möglichkeit starker Parallelisierung.

Naja. Ansonsten - Volkard hat schon Code gepostet, der die Idee verdeutlicht, aber ich will euch die Früchte meiner Arbeit auch nicht vorenthalten. Ich stelle mir das etwa so vor:

#include <cstddef>
#include <new>
#include <tr1/type_traits>
#include <stdexcept>

template<typename T>
class stack_list_node {
public:
  typedef T value_type;

  stack_list_node *prev, *next;
  value_type       &data()       { return *storage(); }
  value_type const &data() const { return *storage(); }

  void init(stack_list_node *pos, value_type const &value) {
    new (storage()) value_type(value);

    prev = pos->prev;
    next = pos;
    pos->prev->next = this;
    pos->prev       = this;
  }

  void destroy(stack_list_node *&head_deleted) {
    data().~value_type();

    prev->next = next;
    next->prev = prev;
    next = head_deleted;
    head_deleted = this;
  }

private:
  value_type       *storage()       { return static_cast<T       *>(static_cast<void       *>(&storage_)); }
  value_type const *storage() const { return static_cast<T const *>(static_cast<void const *>(&storage_)); }
  typename std::tr1::aligned_storage<sizeof(T), std::tr1::alignment_of<T>::value>::type storage_;
};

template<typename T>
struct stack_list_iterator {
  typedef T                                value_type;
  typedef std::ptrdiff_t                   difference_type;
  typedef std::bidirectional_iterator_tag  iterator_category;
  typedef value_type                      *pointer;
  typedef value_type                      &reference;

  stack_list_iterator() : pos_(0) { }
  stack_list_iterator(stack_list_node<value_type> *pos) : pos_(pos) { }

  stack_list_iterator &operator++(   ) { pos_ = pos_->next; return *this; }
  stack_list_iterator  operator++(int) { stack_list_iterator copy(*this); ++*this; return copy; }

  stack_list_iterator &operator--(   ) { pos_ = pos_->prev; return *this; }
  stack_list_iterator  operator--(int) { stack_list_iterator copy(*this); --*this; return copy; }

  reference operator* () const { return  pos_->data(); }
  reference operator->() const { return &pos_->data(); }

  bool operator==(stack_list_iterator const &other) const { return pos_ == other.pos_; }
  bool operator!=(stack_list_iterator const &other) const { return pos_ != other.pos_; }

  stack_list_node<value_type> *pos_;
};

// const_iterator in gleicher Weise

template<typename T, std::size_t N>
class stack_list {
public:

  typedef T                               value_type;
  typedef stack_list_iterator<value_type> iterator;
  static std::size_t const preallocated_size = N;

  stack_list()
    : head_        (local_storage_),
      tail_        (local_storage_ + 1),
      next_unused_ (local_storage_ + 2),
      head_deleted_(0),
      size_        (0)
  {
    // Dummy-Elemente
    head_->prev = tail_->prev = head_;
    head_->next = tail_->next = tail_;
  }

  ~stack_list() {
    while(size_ > 0) {
      erase(begin());
    }
  }

  iterator begin() { return iterator(head_->next); }
  iterator end  () { return iterator(tail_      ); }

  iterator insert(iterator pos, value_type const &val) {
    get_node().init(pos.pos_, val);
    ++size_;
  }

  iterator erase(iterator pos) {
    pos.pos_->destroy(head_deleted_);
    --size_;
  }

private:
  // TODO: Implementieren
  stack_list(stack_list const &);
  stack_list &operator=(stack_list const &);

  typedef stack_list_node<value_type> node_type;

  node_type &get_node() {
    node_type *result;

    if(head_deleted_ != 0) {
      result = head_deleted_;
      head_deleted_ = head_deleted_->next;
    } else if(size_ < preallocated_size) {
      result = next_unused_;
      ++next_unused_;
    } else {
      // Im Zusammenhang hiermit: Sinnvolle Aufräumarbeit ist zu leisten.
      // Wann soll der Speicher wieder freigegeben werden?
      throw std::logic_error("Unimplementiert: Auf den Heap ausweichen");
    }

    return *result;
  }

  node_type    local_storage_[preallocated_size + 2];
  node_type   *head_;
  node_type   *tail_;
  node_type   *next_unused_;
  node_type   *head_deleted_;
  std::size_t  size_;
};

#include <algorithm>
#include <iostream>
#include <iterator>

int main() {
  stack_list<int, 100> ls;

  ls.insert(ls.begin(), 1);
  ls.insert(ls.begin(), 2);
  ls.insert(ls.end  (), 3);

  std::copy(ls.begin(), ls.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;

  stack_list<int, 100>::iterator iter = ls.begin();
  ++iter;
  ls.erase(iter);

  std::copy(ls.begin(), ls.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
}