Search code examples
c++listlinked-liststliterator

How to register a template type as a valid value_type in STL algorithms


I am trying to write a custom container imitating the STL list. I have provided a Link class (not shown), some basic functionality and a custom bidirectional iterator. Trying to conform to STL standards, I have defined Elem to be the value_type of the container. The relevant definitions are given below:

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

However, when I try to use my List iterators with STL find() algorithm:

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

I get the following error:

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>        ]

What STL standard does my definitions not conform to?

Edit: Rooky mistake, thanks Ted Lyngmo for pointing that out. If you are having trouble with conforming to STL standards in custom containers like me, following link contains a more well-put question and more general, valuable answers

Conforming to STL Standards in Custom Container Iterators


Solution

  • You need to define the types in the actual iterator class. See std::iterator_traits.

    Example:

    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;
    //...