Написание собственного контейнера STL

Есть ли рекомендации о том, как следует писать новый контейнер, который будет вести себя как любой контейнер STL ?

Вот последовательность псевдо-контейнеров, которые я собрал из § 23.2.1 \ 4. Обратите внимание, что iterator_category должна быть одной из std::input_iterator_tag , std::output_iterator_tag , std::forward_iterator_tag , std::random_access_iterator_tag , std::random_access_iterator_tag . Также обратите внимание, что ниже технически более строгий, чем требуется, но это идея. Обратите внимание, что подавляющее большинство «стандартных» функций являются технически необязательными из-за удивительности, которая является iteratorом.

 template  > class X { public: typedef A allocator_type; typedef typename A::value_type value_type; typedef typename A::reference reference; typedef typename A::const_reference const_reference; typedef typename A::difference_type difference_type; typedef typename A::size_type size_type; class iterator { public: typedef typename A::difference_type difference_type; typedef typename A::value_type value_type; typedef typename A::reference reference; typedef typename A::pointer pointer; typedef std::random_access_iterator_tag iterator_category; //or another tag iterator(); iterator(const iterator&); ~iterator(); iterator& operator=(const iterator&); bool operator==(const iterator&) const; bool operator!=(const iterator&) const; bool operator<(const iterator&) const; //optional bool operator>(const iterator&) const; //optional bool operator<=(const iterator&) const; //optional bool operator>=(const iterator&) const; //optional iterator& operator++(); iterator operator++(int); //optional iterator& operator--(); //optional iterator operator--(int); //optional iterator& operator+=(size_type); //optional iterator operator+(size_type) const; //optional friend iterator operator+(size_type, const iterator&); //optional iterator& operator-=(size_type); //optional iterator operator-(size_type) const; //optional difference_type operator-(iterator) const; //optional reference operator*() const; pointer operator->() const; reference operator[](size_type) const; //optional }; class const_iterator { public: typedef typename A::difference_type difference_type; typedef typename A::value_type value_type; typedef typename const A::reference reference; typedef typename const A::pointer pointer; typedef std::random_access_iterator_tag iterator_category; //or another tag const_iterator (); const_iterator (const const_iterator&); const_iterator (const iterator&); ~const_iterator(); const_iterator& operator=(const const_iterator&); bool operator==(const const_iterator&) const; bool operator!=(const const_iterator&) const; bool operator<(const const_iterator&) const; //optional bool operator>(const const_iterator&) const; //optional bool operator<=(const const_iterator&) const; //optional bool operator>=(const const_iterator&) const; //optional const_iterator& operator++(); const_iterator operator++(int); //optional const_iterator& operator--(); //optional const_iterator operator--(int); //optional const_iterator& operator+=(size_type); //optional const_iterator operator+(size_type) const; //optional friend const_iterator operator+(size_type, const const_iterator&); //optional const_iterator& operator-=(size_type); //optional const_iterator operator-(size_type) const; //optional difference_type operator-(const_iterator) const; //optional reference operator*() const; pointer operator->() const; reference operator[](size_type) const; //optional }; typedef std::reverse_iterator reverse_iterator; //optional typedef std::reverse_iterator const_reverse_iterator; //optional X(); X(const X&); ~X(); X& operator=(const X&); bool operator==(const X&) const; bool operator!=(const X&) const; bool operator<(const X&) const; //optional bool operator>(const X&) const; //optional bool operator<=(const X&) const; //optional bool operator>=(const X&) const; //optional iterator begin(); const_iterator begin() const; const_iterator cbegin() const; iterator end(); const_iterator end() const; const_iterator cend() const; reverse_iterator rbegin(); //optional const_reverse_iterator rbegin() const; //optional const_reverse_iterator crbegin() const; //optional reverse_iterator rend(); //optional const_reverse_iterator rend() const; //optional const_reverse_iterator crend() const; //optional reference front(); //optional const_reference front() const; //optional reference back(); //optional const_reference back() const; //optional template void emplace_front(Args&&...); //optional template void emplace_back(Args&&...); //optional void push_front(const T&); //optional void push_front(T&&); //optional void push_back(const T&); //optional void push_back(T&&); //optional void pop_front(); //optional void pop_back(); //optional reference operator[](size_type); //optional const_reference operator[](size_type) const; //optional reference at(size_type); //optional const_reference at(size_type) const; //optional template iterator emplace(const_iterator, Args&&...); //optional iterator insert(const_iterator, const T&); //optional iterator insert(const_iterator, T&&); //optional iterator insert(const_iterator, size_type, T&); //optional template iterator insert(const_iterator, iter, iter); //optional iterator insert(const_iterator, std::initializer_list); //optional iterator erase(const_iterator); //optional iterator erase(const_iterator, const_iterator); //optional void clear(); //optional template void assign(iter, iter); //optional void assign(std::initializer_list); //optional void assign(size_type, const T&); //optional void swap(X&); size_type size() const; size_type max_size() const; bool empty() const; A get_allocator() const; //optional }; template  > void swap(X&, X&); //optional 

Кроме того, всякий раз, когда я создаю контейнер, я тестирую class более или менее следующим образом:

 #include  struct verify; class tester { friend verify; static int livecount; const tester* self; public: tester() :self(this) {++livecount;} tester(const tester&) :self(this) {++livecount;} ~tester() {assert(self==this);--livecount;} tester& operator=(const tester& b) { assert(self==this && b.self == &b); return *this; } void cfunction() const {assert(self==this);} void mfunction() {assert(self==this);} }; int tester::livecount=0; struct verify { ~verify() {assert(tester::livecount==0);} }verifier; 

Создавайте контейнеры объектов tester и вызывайте каждую function() при проверке контейнера. Не делайте никаких глобальных объектов tester . Если ваш контейнер обманывает где угодно, этот class tester будет assert и вы узнаете, что вы случайно где-то обманули.

Вам нужно будет прочитать раздел C ++ Standard о контейнерах и требованиях, которые C ++ Standard налагает на реализации контейнеров.

Соответствующая глава в стандарте C ++ 03:

Раздел 23.1 Требования к контейнеру

Соответствующая глава в стандарте C ++ 11:

Раздел 23.2 Требования к контейнеру

Здесь доступен бесплатный проект стандарта C ++ 11.

Вы могли бы также прочитать несколько отличных книг, которые помогут вам понять требования с точки зрения пользователя контейнера. Две отличные книги, которые легко меня поразили:

Эффективный STL от Scott Meyers &
Стандартная библиотека C ++: учебник и справочник Николая Йосутиля

Вот очень упрощенная реализация фальшивого вектора, который в основном является оберткой вокруг std::vector и имеет свой собственный (но реальный) iterator, который имитирует iterator STL. Опять же, iterator очень упрощен, пропускает многие понятия, такие как const_iterator , проверки достоверности и т. Д.

Код запускается из коробки.

 #include  #include  #include  template struct It { std::vector& vec_; int pointer_; It(std::vector& vec) : vec_{vec}, pointer_{0} {} It(std::vector& vec, int size) : vec_{vec}, pointer_{size} {} bool operator!=(const It& other) const { return !(*this == other); } bool operator==(const It& other) const { return pointer_ == other.pointer_; } It& operator++() { ++pointer_; return *this; } T& operator*() const { return vec_.at(pointer_); } }; template struct Vector { std::vector vec_; void push_back(T item) { vec_.push_back(item); }; It begin() { return It(vec_); } It end() { return It(vec_, vec_.size()); } }; int main() { Vector vec; vec.push_back(1); vec.push_back(2); vec.push_back(3); bool first = true; for (It it = vec.begin(); it != vec.end(); ++it) { if (first) //modify container once while iterating { vec.push_back(4); first = false; } std::cout << *it << '\n'; //print it (*it)++; //change it } for (It it = vec.begin(); it != vec.end(); ++it) { std::cout << *it << '\n'; //should see changed value } } 
  • Добавление типов в пространство имен std
  • Заменить вектор, используя вектор индексов
  • Каков наиболее эффективный способ удаления дубликатов и сортировки вектора?
  • Стирание элементов из вектора
  • Когда выделены векторы, они используют память в куче или стеке?
  • Является ли std :: vector копированием объектов с помощью push_back?
  • Почему «! =» Используется с iteratorами вместо «<»?
  • Нужно ли защищать доступ для чтения к контейнеру STL в многопоточной среде?
  • Поиск C ++ STL-подобного векторного classа, но с использованием хранилища стека
  • Как удалить элемент из std :: vector по индексу?
  • Как фильтровать элементы с std :: map?
  • Давайте будем гением компьютера.