编写自己的STL容器 [英] Writing your own STL Container

问题描述

有没有关于如何编写新容器的指南，它将像任何 STL 容器一样工作？

这里是一个从§23.2.1\4拼凑的序列伪容器请注意， iterator_category 应该是 std :: input_iterator_tag ， std :: output_iterator_tag ， std :: forward_iterator_tag ， std :: bidirectional_iterator_tag ， std :: random_access_iterator_tag 。另请注意，以下是技术上比要求更严格，但这是想法。请注意，绝大多数标准函数在技术上是可选的，因为迭代器的强大之处。

  template<类T，类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; 
 
类迭代器{
 public：
 typedef typename A :: difference_type difference_type; 
 typedef typename A :: value_type value_type; 
 typedef typename A :: reference reference; 
 typedef typename A ::指针指针; 
 typedef std :: random_access_iterator_tag iterator_category; //或另一个标签
 
 iterator（）; 
 iterator（const iterator&）; 
〜iterator（） 
 
迭代器& operator =（const iterator&）; 
 bool operator ==（const iterator&）const; 
 bool operator！=（const iterator&）const; 
 bool操作符<（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; //可选
 
引用运算符*（）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 A :: reference const_reference; 
 typedef typename A :: pointer const_pointer; 
 typedef std :: random_access_iterator_tag iterator_category; //或另一个标记
 
 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 
 
 const_reference operator *（）const; 
 const_pointer operator->（）const; 
 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; //可选
 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; //可选
引用（size_type）; // optional 
 const_reference at（size_type）const; // optional 
 
 template< class ... Args> 
 iterator emplace（const_iterator，Args ...）; //可选
迭代器插入（const_iterator，const T&）; // optional 
 iterator insert（const_iterator，T&&）; //可选
迭代器插入（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（）; 
 size_type max_size（）; 
 bool empty（）; 
 
 A get_allocator（）; // optional 
}; 
 template< class T，class A = std :: allocator< T> > 
 void swap（X< T，A&& amp; X< T，A& //可选
  

此外，每当我创建一个容器时， ：

  #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）;} 
} varifier; 
  

创建测试器对象的容器，每个人的 function（）当你测试你的容器。不要创建任何全局的测试器对象。如果你的容器在任何地方作弊，这个测试类会 assert ，你会知道你在某个地方意外欺骗。 p>

Are there guidelines on how one should write new container which will behave like any STL container?

解决方案

Here's a sequence pseudo-container I pieced together from § 23.2.1\4 Note that the iterator_category should be one of std::input_iterator_tag, std::output_iterator_tag,std::forward_iterator_tag,std::bidirectional_iterator_tag,std::random_access_iterator_tag. Also note that the below is technically more strict than required, but this is the idea. Note that the vast majority of the "standard" functions are technically optional, due to the awesomeness that is iterators.

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 A::reference const_reference;
        typedef typename A::pointer const_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

        const_reference operator*() const;
        const_pointer operator->() const;
        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();
    size_type max_size();
    bool empty();

    A get_allocator(); //optional
};
template <class T, class A = std::allocator<T> >
void swap(X<T,A>&, X<T,A>&); //optional

Also, whenever I make a container, I test with a class more or less like this:

#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);}
}varifier;

Make containers of tester objects, and call each one's function() as you test your container. Do not make any global tester objects. If your container cheats anywhere, this tester class will assert and you'll know that you cheated accidentally somewhere.

这篇关于编写自己的STL容器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！