Ndtyjky

Take a look at this implementation of a linked list:

#include <memory>

#include <type_traits>

#include <iostream>



using namespace std;



template<typename D>

class List {

    struct Node {

        shared_ptr<D> data;

        Node* next;

        Node(shared_ptr<D> d, Node* p, Node* n) : data(d), next(n) {}

        ~Node() {

            data.reset();

            delete next;

        }

    };

    template <bool isconst = false> 

    struct iterator : public std::iterator<std::forward_iterator_tag, shared_ptr<D>> {

        typedef std::forward_iterator_tag iterator_category;

        typedef shared_ptr<D> value_type;

        typedef std::ptrdiff_t Distance;

        typedef typename conditional<isconst, const value_type&, value_type&>::type

                Reference;

        typedef typename conditional<isconst, const value_type*, value_type*>::type

                Pointer;

        typedef typename conditional<isconst, const Node*, Node*>::type

                nodeptr;

        iterator(nodeptr x = nullptr) : curr_node(x) {}

        iterator(const iterator<false>& i) : curr_node(i.curr_node) {}

        Reference operator*() const { return curr_node->data; }

        Pointer operator->() const { return &(curr_node->data); }

        template<bool A>

        friend bool operator==(const iterator<A>& a, const iterator<A>& b) {

            return a.curr_node == b.curr_node;

        }

        template<bool A>

        friend bool operator!=(const iterator<A>& a, const iterator<A>& b) {

            return !(a.curr_node == b.curr_node);

        }

        friend class List<D>;

        iterator& operator++() { 

            curr_node = curr_node->next; 

            return *this; 

        }

        private:

            nodeptr curr_node;

    };

    public:

        List() {

            head = nullptr;

        }

        int len() const {

            int ret = 0;

            for (const auto& n : *this) {

                ret++;

            }

            return ret;

        }

        ~List() {

            delete head;

        }

        std::ostream& dump(std::ostream &strm) const {

            for (const auto s : *this) {

                strm << *s << std::endl;

            }

            return strm;

        }

        iterator<false> begin() {

            return iterator<false>(head);

        }

        iterator<false> end() {

            return iterator<false>(nullptr);

        }

        iterator<true> begin() const {

            return iterator<true>(head);

        }

        iterator<true> end() const {

            return iterator<true>(nullptr);

        }

    private:

        Node* head;

};

The part giving me problems is the iterator implementation for this list. The iterator template is supposed to provide both mutable and const iterators.

This is a program which uses this implementation:

#include "List.h"

#include <iostream>



int main( int argc, const char *argv ) {

    List<int> l;



    std::cout << l.len() << std::endl;

    return 0;

}

The program compiles and runs fine if I use clang++, but the compilation fails for g++ with the following error:

In file included from t.cpp:1:

List.h: In instantiation of ‘struct List<int>::iterator<false>’:

List.h:136:5:   required from ‘int List<D>::len() const [with D = int]’

t.cpp:7:24:   required from here

List.h:64:21: error: redefinition of ‘template<bool A> bool operator==(const List<int>::iterator<isconst>&, const List<int>::iterator<isconst>&)’                                                

         friend bool operator==(const iterator<A>& a, const iterator<A>& b) {

                     ^~~~~~~~

List.h:64:21: note: ‘template<bool A> bool operator==(const List<int>::iterator<isconst>&, const List<int>::iterator<isconst>&)’ previously declared here                                        

List.h:69:21: error: redefinition of ‘template<bool A> bool operator!=(const List<int>::iterator<isconst>&, const List<int>::iterator<isconst>&)’                                                

         friend bool operator!=(const iterator<A>& a, const iterator<A>& b) {

                     ^~~~~~~~

List.h:69:21: note: ‘template<bool A> bool operator!=(const List<int>::iterator<isconst>&, const List<int>::iterator<isconst>&)’ previously declared here      

What's the cause of this error? How can I fix this?

The problem seems to be here:

template <bool isconst = false> 

struct iterator : public std::iterator<std::forward_iterator_tag, shared_ptr<D>> {

    template<bool A>

    friend bool operator==(const iterator<A>& a, const iterator<A>& b) {

        return a.curr_node == b.curr_node;

    }

This is saying: For all values of isconst (the outer template parameter), define a template function template<bool A> bool operator==.

So instantiating iterator<true> will define template<bool A> bool operator==, and then instantiating iterator<false> will define template<bool A> bool operator== again, causing a redefinition error.

Solution: Remove the inner template. Have each instantiation of iterator only define its own operator==:

template <bool isconst = false> 

struct iterator : public std::iterator<std::forward_iterator_tag, shared_ptr<D>> {



    friend bool operator==(const iterator& a, const iterator& b) {

        return a.curr_node == b.curr_node;

    }

(Here iterator automatically refers to iterator<isconst>, i.e. the current instantiation.)