Pisanie własnego kontenera STL

120

Czy istnieją wytyczne, jak należy napisać nowy kontener, który będzie zachowywał się jak każdy STLkontener?

Avinash
źródło
7
Zobacz implementacje istniejących kontenerów standardowych i spróbuj je zrozumieć - funkcje, typy zwracane, przeciążenia operatorów, typy zagnieżdżone, zarządzanie pamięcią i wszystko inne.
Nawaz
Zwykle zaczynam od skopiowania prototypów funkcji składowych dowolnego kontenera, który jest najbliższy koncepcji tego, co robię, z msdn lub standardu. ( cplusplus.com nie ma funkcji C ++ 11, a www.sgi.com nie pasuje)
Mooing Duck
@Mooing Duck: myślisz, że MSDN jest bliżej standardu niż sgi?
Dani
3
Zdecydowanie tak. MSDN jest aktualne - SGI jest przed standardem
Puppy
9
Najlepszym źródłem informacji online (kompletność, poprawność, a zwłaszcza użyteczność) jest zdecydowanie cppreference.com. Wyjaśnia również mnóstwo funkcji językowych poza biblioteką. Jest to wiki, więc powinna zawierać mniej błędów niż cplusplus.com.
rubenvb

Odpowiedzi:

209

Oto sekwencja pseudo-pojemnik ja poskładane z § 23.2.1 \ 4 Uwaga, że iterator_categorypowinien być jeden std::input_iterator_tag, std::output_iterator_tag, std::forward_iterator_tag, std::bidirectional_iterator_tag, std::random_access_iterator_tag. Należy również pamiętać, że poniższe informacje są bardziej rygorystyczne pod względem technicznym niż jest to wymagane, ale taka jest idea. Zwróć uwagę, że zdecydowana większość „standardowych” funkcji jest technicznie opcjonalna, ze względu na niesamowity charakter iteratorów.

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

Poza tym za każdym razem, gdy tworzę kontener, testuję z klasą mniej więcej taką:

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

Twórz pojemniki z testerprzedmiotami i wywołuj każdy z nich function()podczas testowania pojemnika. Nie twórz żadnych testerobiektów globalnych . Jeśli twój kontener gdziekolwiek oszukuje, ta testerklasa to zrobi asserti będziesz wiedział, że gdzieś przypadkowo oszukiwałeś.

Mooing Duck
źródło
1
To jest interesujące. Jak działa Twój tester? Istnieje kilka błędów analizy składni, które są trywialne (brak znaku „;”), ale nie są pewne, jak działa ten weryfikator. Och, miałeś na myśli assert(tester::livecount == 0);. Mmmmm, nadal nie jestem pewien, jak działa ta platforma testera. Czy mógłbyś podać przykład?
Adrian
2
Tester ma pojedynczy niestatyczny element członkowski, który jest wskaźnikiem do samego siebie, a destruktor i składowe są sposobem na sprawdzenie, czy nie memcpywydarzyło się żadne nieprawidłowe . (test nie jest niezawodny, ale trochę łapie). livecountJest prosty wykrywacz nieszczelności, aby upewnić się, że pojemnik o nazwie równej liczby konstruktorów i destruktorów.
Mooing Duck,
OK, rozumiem, ale jak to testuje twój iterator? Przy okazji, myślę, że verifiernie miałeś na myśli varifier.
Adrian
4
@Adrian Nie, nie, piszesz swój kontener, a następnie wkładasz kilka z nich do kontenera i robisz różne rzeczy z tym kontenerem, aby sprawdzić, czy przypadkowo nie zapamiętałeś i pamiętałeś o wywołaniu wszystkich destruktorów.
Mooing Duck
1
czy mogę zasugerować odziedziczenie iteratora z std::iteratornagłówka<iterator>
sp2danny
28

Będziesz musiał przeczytać sekcję C ++ Standard dotyczącą kontenerów i wymagań, które C ++ Standard nakłada na implementacje kontenerów.

Odpowiedni rozdział w standardzie C ++ 03 to:

Sekcja 23.1 Wymagania dotyczące kontenerów

Odpowiedni rozdział w standardzie C ++ 11 to:

Sekcja 23.2 Wymagania dotyczące kontenerów

Niemal ostateczny projekt standardu C ++ 11 jest dostępny bezpłatnie tutaj .

Równie dobrze możesz przeczytać kilka doskonałych książek, które pomogą Ci zrozumieć wymagania z punktu widzenia użytkownika kontenera. Dwie doskonałe książki, które z łatwością przyszły mi do głowy, to:

Effective STL byScott Meyers &
The C ++ Standard Library: A Tutorial and Reference autorstwaNicolai Josutils

Alok Save
źródło
6

Oto bardzo uproszczona implementacja fałszywego wektora, który jest w zasadzie opakowaniem std::vectori ma swój własny (ale prawdziwy) iterator, który naśladuje iterator STL. Ponownie, iterator jest bardzo uproszczony, pomijając wiele pojęć, takich jak const_iteratorsprawdzanie poprawności itp.

Kod można uruchomić po wyjęciu z pudełka.

#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
źródło