Schreiben Sie Ihren eigenen STL-Container

120

Gibt es Richtlinien, wie man einen neuen Container schreibt, der sich wie jeder STLContainer verhält ?

Avinash
quelle
7
Sehen Sie sich die Implementierungen der vorhandenen Standardcontainer an und versuchen Sie, sie zu verstehen - die Funktionen, die Rückgabetypen, Operatorüberladungen, verschachtelte Typen, die Speicherverwaltung und alles.
Nawaz
Normalerweise beginne ich damit, die Prototypen der Mitgliedsfunktionen des Containers zu kopieren, der dem Konzept am nächsten kommt, entweder von msdn oder vom Standard. ( cplusplus.com hat keine C ++ 11-Funktionen und www.sgi.com stimmt nicht überein)
Mooing Duck
@Mooing Duck: Sie denken, msdn ist näher am Standard als sgi?
Dani
3
Es ist definitiv so. MSDN ist aktuell - SGI ist Pre-Standard
Welpe
9
Die beste Online-Referenz (hinsichtlich Vollständigkeit, Richtigkeit und insbesondere Benutzerfreundlichkeit) ist bei weitem cppreference.com. Neben der Bibliothek werden auch eine Menge Sprachfunktionen erklärt. Und es ist ein Wiki, daher sollte es weniger Fehler enthalten als cplusplus.com.
Rubenvb

Antworten:

209

Hier ist eine Sequenz pseudo-Container I zusammengestückelt aus § 23.2.1 \ 4 Beachten Sie, dass die iterator_categoryeine der folgenden sein sollte std::input_iterator_tag, std::output_iterator_tag, std::forward_iterator_tag, std::bidirectional_iterator_tag, std::random_access_iterator_tag. Beachten Sie auch, dass das Folgende technisch strenger als erforderlich ist, aber dies ist die Idee. Beachten Sie, dass die überwiegende Mehrheit der "Standard" -Funktionen technisch optional ist, da es sich um Iteratoren handelt.

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

Wenn ich einen Container mache, teste ich mit einer Klasse, die mehr oder weniger so aussieht:

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

Erstellen Sie Container mit testerObjekten und rufen Sie jeden an, function()während Sie Ihren Container testen. Machen Sie keine globalen testerObjekte. Wenn Ihr Container irgendwo betrügt, wird diese testerKlasse assertund Sie werden wissen, dass Sie versehentlich irgendwo betrogen haben.

Mooing Duck
quelle
1
Das ist interessant. Wie funktioniert Ihr Tester? Es gibt mehrere Analysefehler, die trivial sind (fehlendes ';'), aber nicht sicher sind, wie dieser Überprüfungszerstörer funktioniert. Oh, du meintest assert(tester::livecount == 0);. Mmmmm, ich bin mir immer noch nicht sicher, wie dieses Tester-Framework funktioniert. Könnten Sie ein Beispiel geben?
Adrian
2
Der Tester hat ein einzelnes nicht statisches Element, das ein Zeiger auf sich selbst ist, und der Destruktor und die Mitglieder können überprüfen, ob kein ungültiges memcpyElement aufgetreten ist. (Test ist nicht narrensicher, aber es fängt einige). Dies livecountist ein einfacher Lecksucher, um sicherzustellen, dass Ihr Container eine gleiche Anzahl von Konstruktoren und Destruktoren enthält.
Mooing Duck
Ok, ich sehe das, aber wie testet das Ihren Iterator? Übrigens, ich denke du meintest es verifiernicht varifier.
Adrian
4
@Adrian Nein, nein, Sie schreiben Ihren Container und legen dann ein paar davon in den Container und machen Dinge mit dem Container, um zu überprüfen, ob Sie nicht versehentlich memcpy haben, und erinnern sich daran, alle Destruktoren aufzurufen.
Mooing Duck
1
Darf ich vorschlagen, den Iterator vom std::iteratorHeader zu erben<iterator>
sp2danny
28

Sie müssen den Abschnitt C ++ Standard über Container und Anforderungen lesen, die der C ++ Standard für Containerimplementierungen auferlegt.

Das relevante Kapitel im C ++ 03-Standard lautet:

Abschnitt 23.1 Containeranforderungen

Das relevante Kapitel im C ++ 11-Standard lautet:

Abschnitt 23.2 Containeranforderungen

Der nahezu endgültiger Entwurf des C ++ 11 - Standard ist frei verfügbar hier .

Sie können auch einige ausgezeichnete Bücher lesen, die Ihnen helfen, die Anforderungen aus der Sicht des Benutzers des Containers zu verstehen. Zwei ausgezeichnete Bücher, die mir leicht in den Sinn kamen, sind:

Effektive STL vonScott Meyers &
The C ++ Standard Library: Ein Tutorial und eine Referenz vonNicolai Josutils

Alok Speichern
quelle
6

Hier ist eine sehr vereinfachte Implementierung eines gefälschten Vektors, der im Grunde genommen ein Wrapper ist std::vectorund einen eigenen (aber echten) Iterator hat, der den STL-Iterator nachahmt. Auch hier ist der Iterator sehr simpel und überspringt viele Konzepte wie const_iteratorGültigkeitsprüfungen usw.

Code kann sofort ausgeführt werden.

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