如何在STL算法中将模板类型注册为有效的value_type

Question

我正在尝试编写一个模仿STL列表的自定义容器。我提供了一个 List 类（未显示）、一些基本功能和一个自定义双向迭代器。为了符合 STL 标准，我将 Elem 定义为容器的 value_type。相关定义如下：

template <typename Elem>
class List {
public:
    using value_type = Elem;
    using pointer = Elem*;
    using reference = Elem&;
    using iterator_type = std::bidirectional_iterator_tag;
    using size_type = unsigned long;

    List(std::initializer_list<Elem> inlist);

    class iterator;

    iterator begin() { return begin_it; }
    iterator end() { return end_it; }

    iterator insert(iterator p, const Elem& v);
    iterator erase(iterator p);

    void push_back(const Elem& v);
    void push_front(const Elem& v);
    void pop_front();
    void pop_back();

    Elem& front() { return *begin_it; }
    Elem& back() { return *end_it; }

    size_type size();

    ~List();
private:
    iterator begin_it = List<Elem>::iterator{ nullptr };
    iterator end_it = List<Elem>::iterator{ nullptr };
};

template<typename Elem>
class List<Elem>::iterator {
    Link<Elem>* curr;
public:
    iterator(Link<Elem>* p) : curr{ p } {}

    iterator& operator++() { curr = curr->succ; return *this; }
    iterator& operator--() { curr = curr->prev; return *this; }
    Elem& operator*() { return curr->val; }

    Link<Elem>* link() { return curr; }

    bool operator==(const iterator& b) const { return curr == b.curr; }
    bool operator!=(const iterator& b) const { return curr != b.curr; }
};

但是，当我尝试将列表迭代器与 STL find() 算法一起使用时：

List<double> lst = { 1.1, 3.41, 12.31, -4 };
auto found = std::find(lst.begin(), lst.end(), 3.41);

我收到以下错误：

1>C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.36.32532\include\xutility(861,56): error C2794: 'value_type': is not a member of any direct or indirect base class of 'std::iterator_traits<_InIt>'
1>        with
1>        [
1>            _InIt=List<double>::iterator
1>        ]

我的定义不符合什么STL标准？

Answer 1

您需要在实际的迭代器类中定义类型。请参阅

std::iterator_traits

。

示例：

template<typename Elem>
class List<Elem>::iterator {
    Link<Elem>* curr;
public:
    using value_type = Elem;
    using pointer = value_type *;
    using reference = value_type &;
    using iterator_category = std::bidirectional_iterator_tag;
    using difference_type = std::ptrdiff_t;
//...