自定义STL风格List容器迭代器无法适配STL算法的问题排查

我正在编写一个模仿STL list的自定义容器，已实现Link类（未展示）、基础功能及自定义双向迭代器。为遵循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; }
};

但当我尝试将List迭代器用于STL std::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标准？

问题根源 #

你的自定义迭代器未满足STL迭代器的关联类型要求，导致std::iterator_traits无法提取value_type等必要类型信息，进而使得依赖这些信息的STL算法（如std::find）编译失败。

根据C++标准，双向迭代器必须在其类内部定义以下关联类型：

• value_type：迭代器指向的元素类型
• reference：元素的引用类型
• pointer：元素的指针类型
• iterator_category：迭代器的分类标签（此处应为std::bidirectional_iterator_tag）
• difference_type：两个迭代器之间的距离类型（通常为std::ptrdiff_t）

此外，容器类中命名为iterator_type的类型不符合STL规范，标准容器中迭代器的分类标签应通过迭代器自身的iterator_category提供，而非容器类的该成员。

修复代码 #

修改iterator类，添加缺失的关联类型，并补充符合标准的可选操作：

template<typename Elem>
class List<Elem>::iterator {
    Link<Elem>* curr;
public:
    // STL迭代器要求的关联类型
    using value_type = Elem;
    using reference = Elem&;
    using pointer = Elem*;
    using iterator_category = std::bidirectional_iterator_tag;
    using difference_type = std::ptrdiff_t;

    iterator(Link<Elem>* p) : curr{ p } {}

    iterator& operator++() { curr = curr->succ; return *this; }
    iterator operator++(int) { auto tmp = *this; curr = curr->succ; return tmp; } // 后置++
    iterator& operator--() { curr = curr->prev; return *this; }
    iterator operator--(int) { auto tmp = *this; curr = curr->prev; return tmp; } // 后置--
    
    Elem& operator*() { return curr->val; }
    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; }
};

同时，调整容器类的类型定义以符合标准：

template <typename Elem>
class List {
public:
    using value_type = Elem;
    using pointer = Elem*;
    using reference = Elem&;
    using size_type = unsigned long;
    using difference_type = std::ptrdiff_t; // 补充容器的差值类型

    // ... 其余成员保持不变
};

补充说明 #

std::iterator_traits是STL算法获取迭代器类型信息的核心工具，它默认从迭代器类的内部定义中读取关联类型。如果迭代器没有提供这些类型，就会触发编译错误。

虽然后置++/--、operator->并非双向迭代器的强制要求，但为了让自定义迭代器完全匹配STL标准迭代器的行为，建议补充实现这些操作。

内容的提问来源于stack exchange，提问作者berkeozgur