Écrire votre propre conteneur STL

120

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

Avinash
la source
7
Voir les implémentations des conteneurs standard existants et essayez de les comprendre - les fonctions, les types de retour, les surcharges d'opérateurs, les types imbriqués, la gestion de la mémoire et tout.
Nawaz
Je commence généralement par copier les prototypes de fonctions membres du conteneur dont le concept est le plus proche de ce que je fais, soit à partir de msdn, soit du standard. ( cplusplus.com n'a pas de fonctions C ++ 11, et www.sgi.com ne correspond pas)
Mooing Duck
@Mooing Duck: vous pensez que msdn est plus proche du standard que sgi?
Dani
3
C'est définitivement le cas. MSDN est actuel - SGI est pré-standard
Puppy
9
La meilleure référence en ligne (complète, correcte et surtout utilisable) est de loin cppreference.com. Il explique également une tonne de fonctionnalités linguistiques en dehors de la bibliothèque. Et c'est un wiki, donc il devrait contenir moins d'erreurs que cplusplus.com.
rubenvb

Réponses:

209

Voici un I pseudo-conteneur séquence Rassemblé du § 23.2.1 \ 4 Notez que le iterator_categorydevrait être l' un std::input_iterator_tag, std::output_iterator_tag, std::forward_iterator_tag, std::bidirectional_iterator_tag, std::random_access_iterator_tag. Notez également que ce qui suit est techniquement plus strict que nécessaire, mais c'est l'idée. Notez que la grande majorité des fonctions "standard" sont techniquement optionnelles, en raison de la génialité 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 crée un conteneur, je teste avec une classe plus ou moins comme celle-ci:

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

Créez des conteneurs d' testerobjets et appelez chacun d'eux function()pendant que vous testez votre conteneur. Ne créez aucun testerobjet global . Si votre conteneur triche n'importe où, ce testercours le fera assertet vous saurez que vous avez triché accidentellement quelque part.

Canard meunier
la source
1
C'est intéressant. Comment fonctionne votre testeur? Il y a plusieurs erreurs d'analyse, qui sont triviales (manquant ';') mais ne savent pas comment fonctionne ce destructeur de vérification. Oh, tu voulais dire assert(tester::livecount == 0);. Mmmmm, je ne sais toujours pas comment ce framework de testeur fonctionne. Pouvez-vous donner un exemple?
Adrian
2
Le testeur a un seul membre non statique qui est un pointeur vers lui-même, et le destructeur et les membres sont un moyen de vérifier qu'aucun invalide ne memcpys'est produit. (le test n'est pas infaillible, mais il en attrape). Le livecountest un simple détecteur de fuite, pour vous assurer que votre conteneur a appelé un nombre égal de constructeurs et de destructeurs.
Mooing Duck
Ok, je vois ça, mais comment ça teste ton itérateur? BTW, je pense que vous vouliez dire verifiernon varifier.
Adrian
4
@Adrian Non non, vous écrivez votre conteneur, puis mettez un tas de ceux-ci dans le conteneur, et faites des choses avec le conteneur, pour vérifier que vous n'avez pas accidentellement memcpy, et vous vous souvenez d'appeler tous les destructeurs.
Mooing Duck
1
puis-je suggérer d'hériter de l'itérateur de std::iteratorl'en-tête<iterator>
sp2danny
28

Vous devrez lire la section Standard C ++ sur les conteneurs et les exigences imposées par la norme C ++ pour les implémentations de conteneurs.

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

Section 23.1 Exigences relatives aux conteneurs

Le chapitre pertinent de la norme C ++ 11 est:

Section 23.2 Exigences relatives aux conteneurs

Le projet quasi-final de la norme C ++ 11 est disponible gratuitement ici .

Vous pouvez aussi lire d'excellents livres qui vous aideront à comprendre les exigences du point de vue de l'utilisateur du conteneur. Deux excellents livres qui ont facilement frappé mon esprit sont:

Effective STL parScott Meyers et la
bibliothèque standard C ++: un didacticiel et une référence parNicolai Josutils

Alok Save
la source
6

Voici une implémentation très simpliste d'un faux vecteur, qui est essentiellement un wrapper std::vectoret possède son propre (mais réel) itérateur, qui imite l'itérateur STL. Encore une fois, l'itérateur est très simpliste, sautant de nombreux concepts commeconst_iterator contrôles de validité, etc.

Le code est exécutable 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
  }
}
PoweredByRice
la source