Escrevendo seu próprio contêiner STL

120

Existem diretrizes sobre como escrever um novo contêiner que se comportará como qualquer STLcontêiner?

c++ stl c++-standard-library Avinash
fonte
7
Veja as implementações dos contêineres padrão existentes e tente entendê-las - as funções, os tipos de retorno, sobrecargas do operador, tipos aninhados, gerenciamento de memória e tudo.
Nawaz
Normalmente começo copiando os protótipos da função membro de qualquer container que seja o mais próximo em conceito do que estou fazendo, seja do msdn ou do padrão. ( cplusplus.com não possui funções C ++ 11 e www.sgi.com não corresponde) #
Mooing Duck
@ Duck Mooing: você acha que o msdn está mais próximo do padrão do que o sgi?
1176 Dani
3
Definitivamente é. MSDN é atual - SGI é pré-Standard
filhote de cachorro
9
A melhor referência online (integridade, correção e principalmente usabilidade) é de longe o cppreference.com. Ele também explica vários recursos de linguagem além da biblioteca. E é um wiki, por isso deve conter menos erros que o cplusplus.com.
rubenvb

Respostas:

209

Aqui está uma sequência pseudo-container I montado a partir de § 23.2.1 \ 4 Note que o iterator_categorydeve ser um dos std::input_iterator_tag, std::output_iterator_tag, std::forward_iterator_tag, std::bidirectional_iterator_tag, std::random_access_iterator_tag. Observe também que o abaixo é tecnicamente mais rigoroso do que o necessário, mas essa é a ideia. Observe que a grande maioria das funções "padrão" é tecnicamente opcional, devido à grandiosidade que são os iteradores.

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

Além disso, sempre que faço um contêiner, testo com uma classe mais ou menos assim:

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

Faça recipientes de testerobjetos e chame cada um deles ao function()testar seu recipiente. Não faça nenhum testerobjeto global . Se o seu contêiner enganar em qualquer lugar, essa testerclasse o fará asserte você saberá que enganou acidentalmente em algum lugar.

Mooing Duck
fonte
1
Isto é interessante. Como o seu testador funciona? Existem vários erros de análise, que são triviais (faltando ';'), mas não tenho certeza de como esse destruidor de verificação funciona. Oh, você quis dizer assert(tester::livecount == 0);. Mmmmm, ainda não tenho certeza de como essa estrutura de testador funciona. Você poderia dar um exemplo?
Adrian
2
O testador tem um único membro não estático que é um ponteiro para si mesmo, e o destruidor e os membros são uma maneira de verificar se nenhum inválido memcpyaconteceu. (teste não é infalível, mas pega alguns). O livecounté um detector de vazamento simples, para garantir que seu contêiner chame um número igual de construtores e destruidores.
Mooing Duck
Ok, entendo isso, mas como isso testa seu iterador? BTW, acho que você verifiernão quis dizer varifier.
Adrian
4
@ Adrian Não, não, você escreve seu contêiner e, em seguida, coloca um monte deles no contêiner, e faz coisas com o contêiner, para verificar se você não errou acidentalmente e se lembrou de chamar todos os destruidores.
Mooing Duck
1
pode sugiro herdar a iteração a partir std::iteratordo cabeçalho<iterator>
sp2danny
28

Você precisará ler a seção Padrão C ++ sobre Contêineres e requisitos que o Padrão C ++ impõe para implementações de contêiner.

O capítulo relevante no padrão C ++ 03 é:

Seção 23.1 Requisitos de contêiner

O capítulo relevante no padrão C ++ 11 é:

Seção 23.2 Requisitos do contêiner

O rascunho quase final do padrão C ++ 11 está disponível gratuitamente aqui .

Você também pode ler alguns livros excelentes que ajudarão a entender os requisitos de uma perspectiva do usuário do contêiner. Dois excelentes livros que me impressionaram facilmente são:

STL eficaz porScott Meyers e
The C ++ Standard Library: um tutorial e referência porNicolai Josutils

Alok Save
fonte
6

Aqui está uma implementação muito simplista de um vetor falso, que é basicamente um invólucro std::vectore possui seu próprio (mas real) iterador, que imita o iterador STL. Novamente, o iterador é muito simplista, pulando muitos conceitos const_iterator, como verificações de validade etc.

O código é executável imediatamente.

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