编写自己的STL容器

Question

有关如何编写新容器以像任何STL容器一样运作的指南吗？

- Avinash

---

查看现有标准容器的实现，并尝试理解它们 - 函数、返回类型、运算符重载、嵌套类型、内存管理等等。 - Nawaz

我通常会从msdn或标准中最接近我所做的概念的容器的成员函数原型开始复制。（http://www.cplusplus.com没有C++11函数，而www.sgi.com则不匹配） - Mooing Duck

肯定是的。MSDN是当前的 - SGI是标准之前的。 - Puppy

@Dani：我（错误地）认为我在cplusplus.com上看到的东西来自SGI。我不知道SGI有多好，但是我没有看到他们有任何C++11的东西。MSDN有。 - Mooing Duck

目前最好的在线参考资料（就完整度、正确性和易用性而言）是cppreference.com。它不仅详细介绍了库，还解释了许多语言特性。而且它是一个wiki，所以应该比cplusplus.com少出错。 - rubenvb

Answer 1

这是我从§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 <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

另外，每当我创建一个容器时，我都会使用类似于以下的类进行测试：

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

创建 tester 对象的容器，并在测试容器时调用每个对象的 function() 方法。不要创建任何全局的 tester 对象。如果您的容器存在任何作弊行为，这个 tester 类将会 assert，您就会知道自己在哪里意外地作弊了。

- Mooing Duck

---

这很有趣。你的测试器是如何工作的？有几个解析错误，它们很琐碎（缺少“;”），但不确定如何验证析构函数是否起作用。哦，你是指assert(tester::livecount == 0);。嗯，我仍然不确定这个测试框架是如何工作的。你能给一个例子吗？ - Adrian

测试器有一个单一的非静态成员，它是指向自身的指针，析构函数和成员是检查没有发生无效memcpy的方法（测试不是万无一失的，但它可以捕捉到一些问题）。livecount是一个简单的泄漏检测器，用于确保您的容器调用了相同数量的构造函数和析构函数。 - Mooing Duck

不不，你编写你的容器，然后在容器中放入一堆这些东西，并对容器进行操作，以验证你没有意外地进行了memcpy操作，并记得调用所有的析构函数。 - Mooing Duck

我可以建议从头文件<iterator>中继承std::iterator的迭代器。 - sp2danny

@Trevor：我很确定这是相反的。分配器应该使用这些typedef。迭代器不应该知道或关心分配器。实际上，分配器也不应该知道迭代器。我很好奇你为什么认为需要这样做。 - Mooing Duck

Answer 2

你需要阅读C++标准中关于容器的部分，以及C++标准对容器实现的要求。

C++03标准中相关章节为：

第23.1节 容器要求

C++11标准中相关章节为：

第23.2节 容器要求

C++11标准的近期草案可以在此处免费获取。

你也可以阅读一些优秀的书籍，帮助你从使用容器的角度理解要求。两本我想到的优秀书籍是： Scott Meyers的Effective STL和Nicolai Josutils的The C++ Standard Library: A Tutorial and Reference。

- Alok Save

Answer 3

这里是一个非常简单的假向量实现，它基本上是std::vector的包装器并有自己的（但真实的）迭代器，这个迭代器模仿了STL迭代器。同样，这个迭代器非常简单，跳过了许多概念，如const_iterator，有效性检查等。

代码可直接运行。

#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