Списки, стеки, очереди - C++ - Ответ 1693182

// базовый класс элемента связного списка
// так же содержит некоторую логику
struct node_base_ {
  node_base_ *next; // указатель на следующую запись
  node_base_ *prev; // указатель на предыдущую запись
  // при создании без параметров, поля указывают сами на себя
  node_base_() : next(this), prev(this) {}
  // при задании параметров, реализует "вставку" элемента в список
  node_base_(node_base_ *next_, node_base_ *prev_)
    : next(next_), prev(prev_) {
    prev_->next = this;
    next_->prev = this;
  }
  // при удалении элемента удаляет разрыв в списке
  virtual ~node_base_() {
    prev->next = next;
    next->prev = prev;
  }
};
 
// шаблонная структура элемента связного списка
template <class Tp_>
struct node_: public node_base_ {
  Tp_ value;  // содержимое элемента
  // конструктор, вызывает базовый
  node_() : node_base_() {}
  // конструктор с параметрами, вызывает базовый
  node_(node_base_ *next_, node_base_ *prev_, const Tp_ &value_)
    : node_base_(next_, prev_), value(value_) {}
};
 
// шаблонный класс итератора двусвязного списка
template <class ValueType,
          class Pointer = ValueType*, class Reference = ValueType&>
class iterator_base_ {
 public:
  typedef ValueType  value_type;
  typedef Pointer    pointer;
  typedef Reference  reference;
  typedef node_base_ node_base;
  typedef node_<value_type> node;
  iterator_base_() : data_(0) {}
  iterator_base_(node_base *data) : data_(data) {}
  // приведение к типу node для реализации вставки элемента 
  // (допущение для упрощения)
  operator node*() { return (node*)data_; }
  iterator_base_ &operator++() {
    data_ = data_->next;
    return *this;
  }
  iterator_base_ operator++(int) {
    iterator_base_ result(data_);
    data_ = data_->next;
    return result;
  }
  iterator_base_ &operator--() {
    data_ = data_->prev;
    return *this;
  }
  iterator_base_ operator--(int) {
    iterator_base_ result(data_);
    data_ = data_->prev;
    return result;
  }
  iterator_base_ operator-(int count) {
    iterator_base_ result(data_);
    while (count--) --result;
    return result;
  }
  iterator_base_ operator+(int count) {
    iterator_base_ result(data_);
    while (count--) ++result;
    return result;
  }
  bool operator==(const iterator_base_ &other) const {
    return data_ == other.data_;
  }
  bool operator!=(const iterator_base_ &other) const {
    return data_ != other.data_;
  }
  value_type &operator*() { return   ((node*)data_)->value; }
  value_type *operator->() { return &((node*)data_)->value; }
 private:
  node_base *data_;
};
 
template <class ValueType>
class list {
 public:
  typedef ValueType value_type;
  typedef ValueType& reference;
  typedef node_<value_type> node;
  typedef node_base_ node_base;
  typedef iterator_base_<value_type> iterator;
  list() : data_(new node_base()) {}
  ~list() {
    clear();
    delete data_;
  }
  int size() const {
    int result = 0;
    for (iterator i = begin(); i != end(); ++i)
      ++result;
    return result;
  }
  bool empty() {
    return (data_->next == data_ && data_->prev == data_);
  }
  void clear() {
    while (!empty()) delete data_->next;
  }
  reference back() { return *(end() - 1); }
  reference front() { return *begin(); }
  iterator begin() const { return data_->next; }
  iterator end() const { return data_; }
  iterator insert(iterator before, const value_type &value) {
    return new node((node_base_*)before, ((node_base_*)before)->prev, value);
  }
  iterator find_first(const value_type &what) {
    iterator result = begin();
    while (result != end() && *result != what)
      ++result;
    return result;
  }
  iterator erase(iterator what) {
    iterator result = what + 1;
    delete (node*)what;
    return result;
  }
  // erases elements in range [begin, end)
  iterator erase(iterator begin, iterator end) {
    while (begin != end)
      begin = erase(begin);
    return begin;
  }
  iterator push_back(const value_type &value) {
    return insert(end(), value);
    //return new node(data_, data_->prev, value);
  }
 private:
  node_base *data_; // элемент, находящийся "перед" списком и сразу
                    // "за" списком
};

#include "ilist.h"
#include <cstdio>
 
int main_(int argc, char *argv[]) {
  list<int> lst;
  for (int i = 0; i < 10; ++i)
    lst.push_back(i);
  lst.insert(lst.end() - 2, 10);
  lst.erase(lst.end() - 3);
  lst.erase(lst.find_first(4), lst.find_first(5) + 1);
  list<int>::iterator j = lst.begin();
  while (j != lst.end())
    printf("%d\n", *(j++));
  printf("Size: %d\n", lst.size());
  return 0;
}

template <class ValueType>
class vector {
 public:
  typedef ValueType  value_type;
  typedef ValueType* pointer;
  typedef ValueType& reference;
  typedef pointer iterator;
  vector() : begin_(0), end_(0), end_of_storage_(0) {}
  ~vector() { delete [] begin_; }
  void clear() { end_ = begin_; }
  bool empty() const { return begin_ == end_; }
  int size() const { return end_ - begin_; }
  void reserve(int new_size) {
    if (new_size > size()) {
      pointer new_begin = new ValueType[new_size];
      pointer new_end = new_begin;
      for (iterator i = begin(); i != end(); ++i) *new_end++ = *i;
      delete [] begin_;
      begin_ = new_begin;
      end_ = new_end;
      end_of_storage_ = begin_ + new_size;
    }
  }
  iterator begin() const { return begin_; }
  iterator end() const { return end_; }
  reference front() const { return *begin_; }
  reference back() const { return *(end_ - 1); }
  iterator erase(iterator what) {
    for (iterator i = what; i != end() - 1; ++i)
      *i = *(i + 1);
    --end_;
    return what;
  }
  reference at(int position) const { return begin_[position]; }
  iterator insert(iterator before, const value_type &value) {
    if (end_ == end_of_storage_) reserve(size() + 5);
    ++end_;
    for (iterator i = end() - 1; i != before; --i)
      *i = *(i - 1);
    *before = value;
    return before;
  }
  iterator push_back(const value_type &value) {
    if (end_ == end_of_storage_) reserve(size() + 5);
    *end_++ = value;
    return end_ - 1;
  }
  reference operator[](int position) const { return begin_[position]; }
 private:
  pointer begin_;
  pointer end_;
  pointer end_of_storage_;
};

#include "ivector.h"
#include <cstdio>
int main(int argc, char *argv[]) {
  vector<int> v;
  for (int i = 0; i < 10; ++i)
    v.push_back(i);
  v.erase(v.begin() + 1);
  v.insert(v.begin() + 1, 1);
  for (vector<int>::iterator i = v.begin(); i != v.end(); ++i)
    printf("%4d", *i);
  printf("\n");
  for (int i = 0; i < v.size(); ++i)
    printf("%4d", v[i]);
  printf("\n");
  return 0;
}