La rédaction de votre propre Conteneur STL

Sont là des lignes directrices sur la façon dont on devrait écrire un nouveau conteneur qui se comportent comme n'importe STL conteneur?

  • Voir les implémentations de la norme actuelle, les conteneurs, et d'essayer de les comprendre - les fonctions, les types de retour, la surcharge de l'opérateur, les types imbriqués, gestion de la mémoire et de tous.
  • D'habitude, je commence par la copie de la fonction de membre de prototypes de n'importe quel conteneur le plus proche dans le concept de ce que je fais, que ce soit à partir de msdn ou la norme. (cplusplus.com n'a pas de C++11 fonctions, et www.sgi.com ne correspond pas)
  • Canard: vous pensez msdn est plus proche de la norme de sig?
  • Il est certainement. MSDN est en cours - SIG est la pré-Norme
  • J' (à tort) estime que le stuff que j'avais vu chez cplusplus.com a partir de SGI. Je ne sais pas comment bon SGI est, mais ils n'ont pas de C++11 choses que je vois. MSDN n'.
  • Voir la complexité des garanties pour les différents types de conteneurs. stackoverflow.com/questions/181693/...
  • cplusplus.com est manifestement erronée,il y avait un fil autour d'ici,qui a souligné les erreurs,vous souhaitez peut-être à la recherche pour elle.
  • Le meilleur en ligne de référence (par rapport à l'exhaustivité, l'exactitude et surtout de la convivialité) est de loin cppreference.com. Il explique également une tonne de fonctionnalités de langage en dehors de la bibliothèque. Et c'est un wiki, donc il doit contenir moins d'erreurs que cplusplus.com.

InformationsquelleAutor Avinash | 2011-10-13
  1. 199

    Voici une séquence pseudo-conteneur, j'reconstitué à partir d' § 23.2.1\4 de Noter que la iterator_category devrait être l'un des std::input_iterator_tag, std::output_iterator_tag,std::forward_iterator_tag,std::bidirectional_iterator_tag,std::random_access_iterator_tag. Notez également que le dessous est techniquement plus stricte que nécessaire, mais c'est l'idée. Notez que la grande majorité de la "norme" fonctions sont techniquement en option, en raison de l'awesomeness qui est des itérateurs.

    template <class T, class A = std::allocator<T> >
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<iterator> reverse_iterator; //optional
typedef std::reverse_iterator<const_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<class ...Args>
void emplace_front(Args&&...); //optional
template<class ...Args>
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<class ...Args>
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<class iter>
iterator insert(const_iterator, iter, iter); //optional
iterator insert(const_iterator, std::initializer_list<T>); //optional
iterator erase(const_iterator); //optional
iterator erase(const_iterator, const_iterator); //optional
void clear(); //optional
template<class iter>
void assign(iter, iter); //optional
void assign(std::initializer_list<T>); //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 <class T, class A = std::allocator<T> >
void swap(X<T,A>&, X<T,A>&); //optional

    Aussi, chaque fois que je fais un récipient, j'ai test avec une classe plus ou moins comme ceci:

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

    À la fabrication des récipients de tester objets, et d'appeler chacun function() que vous testez votre conteneur. Ne pas faire à l'échelle mondiale tester objets. Si votre conteneur des tricheurs partout, ce tester classe assert et vous saurez que vous avez triché accidentellement quelque part.

    • Ce qui est intéressant. Comment est-ce que votre testeur de travail? Il y a plusieurs erreurs d'analyse, qui sont triviales (manquant ';') mais vous ne savez pas comment vérifier que le destructeur des œuvres. Oh, vous voulez assert(tester::livecount == 0);. Mmmmm, pas encore sûr de savoir comment ce testeur cadre de travaux. Pourriez-vous nous donner un exemple?
    • Le testeur a un seul membre non statique qui est un pointeur à lui-même, et le destructeur et les membres sont un moyen de vérifier qu'aucun invalide memcpy qui s'est passé. (test n'est pas infaillible, mais il attrape quelques-uns). Le livecount est un simple détecteur de fuites, assurez-vous que votre conteneur appelé un nombre égal de constructeurs et destructeurs.
    • Ok, je vois, mais comment est-ce que le test de votre itérateur? BTW, je pense que vous vouliez dire verifier pas varifier.
    • Non, non, vous écrivez votre conteneur, puis mettre un tas de ces dans le conteneur, et de faire les choses avec le conteneur, afin de vérifier que vous n'avez pas accidentellement memcpy, et rememebered pour appeler tous les destructeurs.
    • Ah, je vois. Du sens. Merci. 🙂
    • puis-je suggérer d'hériter de l'itérateur de std::iterator de l'en-tête <iterator>
    • Je pense que size, max_size, empty, et get_allocator devrait être const.
    • Fait, merci.
    • Aussi je crois que les typedefs sur le const_iterator doit utiliser const_reference et const_pointer hors de allocator. J'ai été en utilisant le présent de mettre en place un STL style container... le travail fantastique de par la manière dont!
    • Je suis assez sûr que c'est à l'envers. L'allocation doit être à l'aide de ces typedefs. L'itérateur ne sais pas ou se soucient allocateurs. En fait, allocateurs ne devriez pas savoir sur les itérateurs soit. Je suis curieux de savoir pourquoi vous dites que c'est nécessaire.
    • Je vais juste hors de votre exemple, à l'intérieur de la const_iterator vous avez écrit: typedef typename A::reference const_reference;. C'est problématique parce qu'il fait toutes les const_reference retour d'un non-const de référence. Il devrait au moins être typedef typename A::const_reference const_reference;... droit? Je ne sais rien à propos de savoir si ou non typedef devrais même pas être là... c'est dans votre exemple.
    • En regardant de plus près, vous avez raison. reference et pointer ont été à la fois mal nommée-et à tort const qualifié. Fixe.

    InformationsquelleAutor Mooing Duck
  2. 26

    Vous aurez besoin de lire la Norme C++ section sur les Conteneurs et les exigences de la Norme C++ impose pour les implémentations de conteneur.

    Le chapitre correspondant du C++03 standard est:

    De L'Article 23.1 Du Conteneur

    Le chapitre correspondant du C++11 standard est:

    De L'Article 23.2 Du Conteneur

    Le proche-version finale du projet de C++11 standard est disponible gratuitement ici.

    Vous pourriez aussi bien, de lire quelques excellents livres qui vous aideront à comprendre les exigences d'un point de vue de l'utilisateur du conteneur. Deux excellents livres qui a frappé mon esprit sont facilement:

    Efficace STL par Scott Meyers &

    Le C++ Standard Library: Un Tutoriel et de Référence par Nicolai Josutils

    InformationsquelleAutor Alok Save
  3. 4

    Voici un très simpliste de la mise en œuvre d'un faux vecteur, qui est en fait un wrapper autour de std::vector et dispose de son propre (mais réel) itérateur, qui imite la STL itérateur. Encore une fois, l'itérateur est très simpliste, sautant sur de nombreux concepts comme const_iterator, contrôles de validité etc.

    Code est praticable hors de la boîte.

    #include <iostream>
#include <string>
#include <vector>
template<typename T>
struct It
{
std::vector<T>& vec_;
int pointer_;
It(std::vector<T>& vec) : vec_{vec}, pointer_{0} {}
It(std::vector<T>& vec, int size) : vec_{vec}, pointer_{size} {}
bool operator!=(const It<T>& other) const
{
return !(*this == other);
}
bool operator==(const It<T>& other) const
{
return pointer_ == other.pointer_;
}
It& operator++()
{
++pointer_;            
return *this;
}
T& operator*() const
{
return vec_.at(pointer_);   
}
};
template<typename T>
struct Vector
{
std::vector<T> vec_;
void push_back(T item)
{
vec_.push_back(item);
};
It<T> begin()
{
return It<T>(vec_);
}
It<T> end()
{
return It<T>(vec_, vec_.size());
}
};
int main()
{
Vector<int> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
bool first = true;
for (It<int> 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<int> it = vec.begin(); it != vec.end(); ++it)
{
std::cout << *it << '\n'; //should see changed value
}
}
    InformationsquelleAutor PoweredByRice