Ecrire votre propre conteneur STL

Existe-t-il des directives sur la manière d’écrire un nouveau conteneur qui se comportera comme n’importe quel conteneur STL ?

Voici un pseudo-conteneur de séquence que j’ai reconstitué à partir du § 23.2.1 \ 4. Notez également que ci-dessous est techniquement plus ssortingct que nécessaire, mais c’est l’idée. Notez que la grande majorité des fonctions “standard” sont techniquement facultatives, en raison de la génialité des iterators.

 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 

Aussi, chaque fois que je fais un conteneur, je teste avec une classe plus ou moins comme ceci:

 #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; 

Créez des conteneurs d’objects tester et appelez chacun des function() pendant que vous testez votre conteneur. Ne faites pas d’objects tester globaux. Si votre conteneur sortingche quelque part, cette classe de tester assert et vous saurez que vous avez sortingché quelque part accidentellement.

Vous devrez lire la section C ++ Standard sur les conteneurs et les exigences que le standard C ++ impose pour les implémentations de conteneur.

Le chapitre pertinent de la norme C ++ 03 est le suivant:

Section 23.1 Exigences relatives au conteneur

Le chapitre pertinent du standard C ++ 11 est le suivant:

Section 23.2 Exigences relatives au conteneur

La version presque finale du standard C ++ 11 est disponible gratuitement ici .

Vous pourriez aussi lire d’excellents livres qui vous aideront à comprendre les exigences du sharepoint vue de l’utilisateur du conteneur. Deux excellents livres qui m’ont frappé facilement sont:

STL efficace par Scott Meyers &
La bibliothèque standard C ++: tutoriel et référence par Nicolai Josutils

Voici une implémentation très simpliste d’un faux vecteur, qui est essentiellement une enveloppe autour de std::vector et qui possède son propre iterator (mais réel), qui imite l’iterator STL. Encore une fois, l’iterator est très simpliste, sautant de nombreux concepts tels que const_iterator , contrôles de validité, etc.

Le code est exécutable hors de la boîte.

 #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 } }