Doubly-linked-list implementation in C++

Question

I am fairly new to C++ and have been trying to make a doubly-linked-list class that imitates std::list (though not all of it). I'd appreciate if someone can look at my code and let me know if I have missed anything important, and if everything seems to be implemented correctly.

Note:the end node is implemented as one past the last element.

Here is the interface:

#ifndef my_list_h
#define my_list_h
#include <cstdlib>
// forward declarations
template<class T> class my_list;
template<class Value,class Pointer,class Reference> class 
my_bidirectional_iterator;
template<class T> class my_list_iterator;
template<class T> class my_list_const_iterator;
template<class T> class node {
 node(const T& t = T()):data(t),next(0),prev(0) {}
 T data;
 node* next;
 node* prev;
 friend class my_list<T>;
 friend class my_bidirectional_iterator<node<T>,T*,T&>;
 friend class my_bidirectional_iterator<node<T>,const T*,const T&>;
};
template<class Value,class Pointer,class Reference> class my_bidirectional_iterator {
 public:
 // increment and decrement operators
 my_bidirectional_iterator operator++();
 my_bidirectional_iterator operator++(int);
 my_bidirectional_iterator operator--();
 my_bidirectional_iterator operator--(int);
 // bool comparison iterators
 bool operator==(const my_bidirectional_iterator& other) const {return pos_==other.pos_;}
 bool operator!=(const my_bidirectional_iterator& other) const {return pos_!=other.pos_;}
 // member access
 Reference operator*() const {return pos_->data;}
 Pointer operator->() const {return &(pos_->data);}
 private:
 explicit my_bidirectional_iterator(Value* p=0):pos_(p) {}
 Value* pos_;
 template<class U> friend class my_list_iterator;
 template<class U> friend class my_const_list_iterator;
 template<class U> friend class my_list;
};
template<class T> class my_list_iterator: public my_bidirectional_iterator<node<T>,T*,T&> {
 using my_bidirectional_iterator<node<T>,T*,T&>::my_bidirectional_iterator;
 friend class my_list_const_iterator<T>;
 public:
 operator my_list_const_iterator<T>() {return my_list_const_iterator<T>(this->pos_);}
};
template<class T> class my_list_const_iterator: public my_bidirectional_iterator<node<T>,const T*,const T&>
{
 friend class my_list_iterator<T>;
 using my_bidirectional_iterator<node<T>,const T*,const T&>::my_bidirectional_iterator;
};
template<class T> class my_list {
 public:
 typedef my_list_iterator<T> iterator;
 typedef my_list_const_iterator<T> const_iterator;
 typedef T value_type;
 typedef std::size_t size_type;
 // constructors
 my_list() {create();}
 explicit my_list(size_type n,const T& t=T()) {create(n,t);}
 // copy constructor
 my_list(const my_list& rhs) {create(rhs.begin(),rhs.end());}
 // assignment operator
 my_list& operator=(const my_list&);
 // destructor
 ~my_list() {clear();}
 // element access
 T& front() {return head_->data;}
 const T& front() const {return head_->data;}
 T& back() {return tail_->prev->data;}
 const T& back() const {return tail_->prev->data;}
 // iterators
 iterator begin() {return iterator(head_);}
 const_iterator begin() const {return const_iterator(head_);}
 iterator end() {return iterator(tail_);}
 const_iterator end() const {return const_iterator(tail_);}
 // capacity
 bool size() const {return size_;}
 bool empty() const {return size_==0;}
 // modifiers
 void clear();
 iterator insert(iterator,const T&);
 iterator erase(iterator);
 void push_back(const T& t) {insert(end(),t);}
 void push_front(const T& t) {insert(begin(),t);}
 void pop_back() {erase(iterator(tail_->prev));}
 void pop_front() {erase(iterator(head_));}
 void resize(size_type);
 private:
 node<T> *head_,*tail_;
 size_type size_;
 void create();
 void create(size_type, const T& t = T());
 void create(const_iterator,const_iterator);
 void insertInternal(node<T>*,const T&);
 friend class my_list_iterator<T>;
 friend class my_list_const_iterator<T>;
};
#include "my_list.hpp"
#endif

And the implementation:

template<class Value,class Pointer,class Reference> 
my_bidirectional_iterator<Value,Pointer,Reference> my_bidirectional_iterator<Value,Pointer,Reference>::operator++()
{
 pos_ = pos_->next;
 return *this;
}
template<class Value,class Pointer,class Reference> 
my_bidirectional_iterator<Value,Pointer,Reference> 
my_bidirectional_iterator<Value,Pointer,Reference>::operator++(int)
{
 Value* prev= pos_;
 pos_ = pos_->next;
 return my_bidirectional_iterator(prev);
}
template<class Value,class Pointer,class Reference> 
my_bidirectional_iterator<Value,Pointer,Reference> 
my_bidirectional_iterator<Value,Pointer,Reference>::operator--()
{
 pos_ = pos_->prev;
 return *this;
}
template<class Value,class Pointer,class Reference> 
my_bidirectional_iterator<Value,Pointer,Reference> 
my_bidirectional_iterator<Value,Pointer,Reference>::operator--(int)
{
 Value* next= pos_;
 pos_ = pos_->prev;
 return my_bidirectional_iterator(next);
}
template<class T> my_list<T>& my_list<T>::operator=(const my_list& rhs)
{
 if (this!=&rhs)
 {
 clear();
 create(rhs.begin(),rhs.end());
 }
 return *this;
}
template<class T> void my_list<T>::clear()
{
 if (size_!=0)
 {
 node<T>* first = head_;
 while (first!=0)
 {
 node<T>* next = first->next;
 delete first;
 first = next;
 }
 }
 head_=tail_=0;
 size_=0;
}
template<class T> typename my_list<T>::iterator 
my_list<T>::insert(iterator pos,const T& t)
{
 // create new node holding the value t
 node<T>* new_node = new node<T>(t);
 // pointer to node before which t is inserted
 // if node doesn't exist make it on the fly
 node<T>* p = (pos.pos_)?(pos.pos_):(new node<T>());
 // make sure new_node is before p
 new_node->next = p;
 if (p->prev){
 new_node->prev = p->prev;
 new_node->prev->next = new_node;
 } else
 head_ = new_node;
 p->prev = new_node;
 // make sure that tail_ is set properly if we started with empty list
 if (size_==0)
 tail_ = p;
 // increase size
 ++size_;
 // return iterator pointng to new node
 return iterator(new_node);
}
template<class T> typename my_list<T>::iterator my_list<T>::erase(iterator pos)
{
 node<T> *p = pos.pos_;
 if (p->next!=0)
 p->next->prev = p->prev;
 else
 tail_ = p->prev;
 if (p->prev!=0)
 p->prev->next = p->next;
 else
 head_ = p->next;
 node<T>* n = p->next;
 delete p;
 --size_;
 return iterator(n);
}
template<class T> void my_list<T>::resize(size_type n)
{
 while (n<size_)
 pop_back();
 while (n>size)
 push_back(T());
}
template<class T> void my_list<T>::create()
{
 head_=tail_=0;
 size_ = 0;
}
template<class T> void my_list<T>::create(size_type n,const T& t)
{
 create();
 for (size_type i=0;i!=n;++i)
 push_back(t);
}
template<class T> void my_list<T>::create(const_iterator b,const_iterator e)
{
 create();
 while (b!=e)
 push_back(*b++);
}

I am using GCC 8.3.0 which, if I checked correctly, implements C++14 by default. In any case, I tried compiling with -std=c++11 and it compiles fine.

• L. F.: Which standard of C++ are you using? Is it C++17?
• L. F.: Also, it would be nice if you add some test cases so we can verify.
• John: @ L.F. I am using GCC 8.3.0 which, if I checked correctly, implements C++14 by default. In any case, I tried compiling with -std=c++11 and it compiles fine. This probably seems like a dumb question, but how can I find good test cases?
• L. F.: That's not a dumb question. In fact, finding good test cases is extremely nontrivial. First of all, make sure all members appear in the test. (This should help you find some typos like bool size().) And always test for edge cases (zero, min/max value, even/odd numbers, etc.)
• Sᴀᴍ Onᴇᴌᴀ: Welcome to Code Review! Please see What to do when someone answers. I have rolled back Rev 8 → 5

Answer 1

(Note: Martin York posted an answer when this answer is halfway done. The already written part will be left as is, but I try to avoid duplicating content after that. Make sure you read that answer as well!)

General

These are general suggestions:

1. First of all, please write the declaration of a template class on two lines and use more spaces — rather than:

   template<class T> class my_list;
   

   this is more readble:

   template <class T>
   class my_list;
   

2. public: and private: labels usually go one indentation level left, e.g.:

   template <class T>
   class my_list {
    using Foo = T*;
   public:
    Foo foo();
   private:
    Foo bar();
   };
   

3. Do not use 0 as a null pointer constant. Use nullptr instead. See What exactly is nullptr?.

4. Use alias-declarations rather than typedef. For example, instead of

   typedef my_list_iterator<T> iterator;
   typedef my_list_const_iterator<T> const_iterator;
   typedef T value_type;
   typedef std::size_t size_type;
   

   we prefer

   using iterator = my_list_iterator<T>;
   using const_iterator = my_list_const_iterator<T>;
   using value_type = T;
   using size_type = std::size_t;
   

   in modern C++. They are semantically equivalent, but the second form is more readable, especially with complex types (e.g., typedef void (&MyFunc)(int,int); vs. using MyFunc = void(&)(int,int);).

5. Don't squash everything together like this:

   my_list(const my_list& rhs) {create(rhs.begin(),rhs.end());}
   

   At least use spaces:

   my_list(const my_list& rhs) { create(rhs.begin(), rhs.end()); }
   

   If I were you, I would probably make it even more readable:

   my_list(const my_list& rhs)
   {
    create(rhs.begin(), rhs.end());
   }
   

6. I'm pretty sure the functionality you want to expose is my_list — all the rest is implementation detail and should not be accessed directly. You can put everything in a namespace and use a conventional "detail" namespace:

   // replace "unicorn9378" with your own name for the namespace
   namespace unicorn9378 {
    namespace detail {
    // implementation detail
    }
    // public interface
   }
   

   and then drop my_ because "me" can be anyone. Namespaces will help you with ADL (argument dependent lookup), so don't hesitate to use them even for small projects.

7. Since you are trying to imitate the standard std::list, there is some missing functionality. I suggest that you check against a reference. Some features are nontrivial to implement (e.g., allocator support) but some of them really should be implemented (e.g., move operations).

Code

So let's go through the code and find something else to improve:

---

#ifndef my_list_h
#define my_list_h

Macros are usually ALL_CAPS — use MY_LIST_H. Also, this name is short and will cause name clash. My solution is to add a random string after it — for example, MY_LIST_H_RwxhY7ucBR.

---

#include <cstdlib>

If you include this header for std::size_t, use #include <cstddef> instead. It is much cheaper and everyone knows that <cstddef> defines std::size_t.

---

// forward declarations
template<class T> class my_list;
template<class Value,class Pointer,class Reference> class 
my_bidirectional_iterator;
template<class T> class my_list_iterator;
template<class T> class my_list_const_iterator;

This really hurts my eyes. As I mentioned before, use spaces and newlines.

---

template<class T> class node {
 node(const T& t = T()):data(t),next(0),prev(0) {}
 T data;
 node* next;
 node* prev;
 friend class my_list<T>;
 friend class my_bidirectional_iterator<node<T>,T*,T&>;
 friend class my_bidirectional_iterator<node<T>,const T*,const T&>;
};

Rather than making everything private and friend everyone, just make things public — this is already implementation detail, after all. The constructor is unnecessary and introduces an unneeded copy — just leave it out. Like this:

template <class T>
struct node {
 T data;
 node* next{nullptr};
 node* prev{nullptr};
};

Then this class will be an aggregate and you will be using aggregate initialization to create nodes like this:

node<T>{value, next_ptr, prev_ptr}

---

template<class Value,class Pointer,class Reference> class my_bidirectional_iterator {
 public:
 // increment and decrement operators
 my_bidirectional_iterator operator++();
 my_bidirectional_iterator operator++(int);
 my_bidirectional_iterator operator--();
 my_bidirectional_iterator operator--(int);
 // bool comparison iterators
 bool operator==(const my_bidirectional_iterator& other) const {return pos_==other.pos_;}
 bool operator!=(const my_bidirectional_iterator& other) const {return pos_!=other.pos_;}
 // member access
 Reference operator*() const {return pos_->data;}
 Pointer operator->() const {return &(pos_->data);}
 private:
 explicit my_bidirectional_iterator(Value* p=0):pos_(p) {}
 Value* pos_;
 template<class U> friend class my_list_iterator;
 template<class U> friend class my_const_list_iterator;
 template<class U> friend class my_list;
};
template<class T> class my_list_iterator: public my_bidirectional_iterator<node<T>,T*,T&> {
 using my_bidirectional_iterator<node<T>,T*,T&>::my_bidirectional_iterator;
 friend class my_list_const_iterator<T>;
 public:
 operator my_list_const_iterator<T>() {return my_list_const_iterator<T>(this->pos_);}
};
template<class T> class my_list_const_iterator: public my_bidirectional_iterator<node<T>,const T*,const T&>
{
 friend class my_list_iterator<T>;
 using my_bidirectional_iterator<node<T>,const T*,const T&>::my_bidirectional_iterator;
};

Prefix ++ and -- should return a reference to *this.

I don't really think you need the bidirectional_iterator class — just implement the two iterator types separately, there isn't very much boilerplate code. If you insist to reduce duplicate code by extracting the common part into a base class, things will quickly get complicated — you need to use the CRTP (curiously recurring template pattern). You will have to pass the derived classes as a template parameter to the base class for the base class to return the correct types.

Also, you forgot the required types: value_type, iterator_category, etc. You can either supply them directly in the iterator classes:

template <class T>
class list_iterator {
public:
 using value_type = T;
 using reference = T&;
 using pointer = T*;
 using difference_type = std::ptrdiff_t;
 using iterator_category = std::bidirectional_iterator_tag;
 explicit list_iterator(node<T>* p = nullptr)
 :pos{p}
 {
 }
 list_iterator& operator++();
 list_iterator& operator--();
 list_iterator operator++(int);
 list_iterator operator--(int);
 bool operator==(const my_bidirectional_iterator& other) const
 {
 return pos == other.pos;
 }
 bool operator!=(const my_bidirectional_iterator& other) const
 {
 return pos != other.pos;
 }
 reference operator*() const
 {
 return pos->data;
 }
 pointer operator->() const
 {
 return &pos->data;
 }
private:
 node<T>* pos;
};
// list_const_iterator similar

or you can specialize std::iterator_traits. Note that this is a requirement of an iterator; if you don't implement these types, yours does not qualify as a real "iterator" and it will be undefined behavior to use it with the, say, standard algorithms.

(iterator_category is one of input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag, and random_access_iterator_tag, and represents the iterator category of the iterator. The algorithms can usually provide better performance for more advanced iterators, and this information is not easily available otherwise. For example, lower_bound will perform much better on random access iterators.)

---

typedef my_list_iterator<T> iterator;
typedef my_list_const_iterator<T> const_iterator;
typedef T value_type;
typedef std::size_t size_type;

Missing some of them.

---

// constructors
my_list() {create();}
explicit my_list(size_type n,const T& t=T()) {create(n,t);}

The create function is a bit unidiomatic in C++. Use member initializers (later) and make the default constructor = default. Also, the size constructor is C++03 style — elements are default constructed (i.e., value initialized) instead of copy constructed from a default constructed element since C++11:

my_list() = default; // requires member initializers
explicit my_list(size_type n)
{
 insert(end(), n); // I'll talk about this later
}

And there are many more constructors.

---

// copy constructor
my_list(const my_list& rhs) {create(rhs.begin(),rhs.end());}
// assignment operator
my_list& operator=(const my_list&);
// destructor
~my_list() {clear();}

Make a general iterator overload for insert. No need for a special create function.

---

// element access
T& front() {return head_->data;}
const T& front() const {return head_->data;}
T& back() {return tail_->prev->data;}
const T& back() const {return tail_->prev->data;}

Good.

---

// iterators
iterator begin() {return iterator(head_);}
const_iterator begin() const {return const_iterator(head_);}
iterator end() {return iterator(tail_);}
const_iterator end() const {return const_iterator(tail_);}

Good. Better if you add cbegin, cend, rbegin, etc.

---

// capacity
bool size() const {return size_;}
bool empty() const {return size_==0;}

There's a blatant typo here, can you find it?

---

// modifiers
void clear();
iterator insert(iterator,const T&);
iterator erase(iterator);

You are missing a lot of overloads — see insert and erase.

---

void push_back(const T& t) {insert(end(),t);}
void push_front(const T& t) {insert(begin(),t);}
void pop_back() {erase(iterator(tail_->prev));}
void pop_front() {erase(iterator(head_));}

Good. Also, back before front? A little weird to me.

---

void resize(size_type);

There's another overload resize(n, value).

---

private:
 node<T> *head_,*tail_;
 size_type size_;

Don't declare multiple entities in one declaration like this. It's easy to go wrong, both for the reader and the writer. Declare one entity on one line and use member initializers:

node<T>* head_{nullptr};
node<T>* tail_{nullptr};
size_type size_{0};

---

void create();
void create(size_type, const T& t = T());
void create(const_iterator,const_iterator);
void insertInternal(node<T>*,const T&);
friend class my_list_iterator<T>;
friend class my_list_const_iterator<T>;

As I said before, these create functions do not appear to be necessary — just use insert.

---

template<class Value,class Pointer,class Reference> 
my_bidirectional_iterator<Value,Pointer,Reference> my_bidirectional_iterator<Value,Pointer,Reference>::operator++()
{
 pos_ = pos_->next;
 return *this;
}

As I said before, this should return a reference. Also, use a trailing return type to save some typing. And I would implement it in the class definition directly.

---

template<class Value,class Pointer,class Reference> 
my_bidirectional_iterator<Value,Pointer,Reference> 
my_bidirectional_iterator<Value,Pointer,Reference>::operator++(int)
{
 Value* prev= pos_;
 pos_ = pos_->next;
 return my_bidirectional_iterator(prev);
}

You can use std::exchange for such things:

template <class T>
list_iterator<T>& list_iterator<T>::operator++(int)
{
 return list_iterator{std::exchange(pos, pos->next)};
}

---

template<class Value,class Pointer,class Reference> 
my_bidirectional_iterator<Value,Pointer,Reference> 
my_bidirectional_iterator<Value,Pointer,Reference>::operator--()
{
 pos_ = pos_->prev;
 return *this;
}
template<class Value,class Pointer,class Reference> 
my_bidirectional_iterator<Value,Pointer,Reference> 
my_bidirectional_iterator<Value,Pointer,Reference>::operator--(int)
{
 Value* next= pos_;
 pos_ = pos_->prev;
 return my_bidirectional_iterator(next);
}

See above.

---

template<class T> my_list<T>& my_list<T>::operator=(const my_list& rhs)
{
 if (this!=&rhs)
 {
 clear();
 create(rhs.begin(),rhs.end());
 }
 return *this;
}

No, no, no. Don't reinvent it. Use the copy and swap idiom:

template <class T>
list<T>& list<T>::operator=(list other) // pass by value
{
 swap(other);
 return *this;
}

(You need to implement swap.)

---

template<class T> void my_list<T>::clear()
{
 if (size_!=0)
 {
 node<T>* first = head_;
 while (first!=0)
 {
 node<T>* next = first->next;
 delete first;
 first = next;
 }
 }
 head_=tail_=0;
 size_=0;
}

As Martin York mentioned, the size != 0 check is redundant. And you can avoid reimplementing the iterator:

for (auto it = begin(); it != end();)
 delete (it++).pos;

---

(The code for insert and erase)

The insert and erase functions are too complex because you have to consider a lot of edge cases. They have bugs, so fix them first. If you redesign the list to use a sentinel, these functions will be simpler.

---

template<class T> void my_list<T>::resize(size_type n)
{
 while (n<size_)
 pop_back();
 while (n>size)
 push_back(T());
}

size is the name of a function and cannot be compared to a variable of type size_type. Typo?

Conclusion

This may seem like a lot of problems, but since you are fairly new to C++, I think this is good enough. I'd say your code is quite nice in general. In the future, remember that you have to instantiate all template functions (including member functions of class templates) to test them because of two-phase lookup, so make sure that every function is included your tests. This should avoid the typo problems. Also, since this is a linked list, an obvious edge case is zero, so test every function on an empty list to see if they work correctly. Good work!

• John: Wow thanks. I implemented most of the changes but I have a couple of questions: 1)Why should I use aliases instead of typedef? Is it just a convention or is there a deeper reason? 2)Will look into the namespace idea. However note this is not to be used as a library, it's more for me to understand better linked lists and to code in C++.
• John: 3)I'm not sure I understand what's the issue with the constructor of node<T>. I need to create a node holding T when I implement push_back anyway. What's the difference with just creating an empty node and then editing the value of data? 4)I don't see why I should implement two classes when I can make a more general template and inherit from both? 5)I didn't use the value_type that's why I didn't implement it. I'm not sure what the iterator_category does. I mean I can sort of imagine but I don't fully understand how it works that's why I left it out...
• L. F.: @John You are welcome. Re 1) Aliases are preferred to typedef because they are more general (support templates) and they are more easily comprehensible (assignment syntax). They are equivalent. 2) A namespace can help you avoid name clash, so don't hesitate to use it even in small projects!
• L. F.: @John 3) You will be using aggregate initialization. 4) In more complex cases, that's a good idea, but in this case it will cause a ton of conversion problems. If you insist, you need to look up CRTP (curiously recurring template pattern). You need to pass the derived class as a template parameter so that the base class can return the correct type. I'd say that's more work than just implementing them separately :)
• L. F.: @John 5) If you didn't use value_type, other users of the iterator will do. If you don't implement it, your iterator doesn't meet the full requirements of an "iterator." And iterator_category see en.cppreference.com/w/cpp/iterator#Iterator_categories. I will update my answer to include some of these clarifications :)

Answer 2

General things

Please use two lines for template class declarations:

template<class T> class my_list {
// Do this
template<class T>
class my_list
{ // In nearly all other cases I am fine with the
 // { being on the same line. But class and function
 // declarations you just need the little bit of extra
 // white space.

I worry about you not using braces {} after if/while/for expressions.

Code Review

I would make the node class a private member of the list.

template<class T> class node {

There is no need to create a globally accessable type that must be maintained if you don't need to. Hide implementation details so they don't need to be maintained.

---

If you put it (node) inside list and also iterator is a class inside list. Then you can simply make node a structure. Then all this friendship becomes redundant.

 friend class my_list<T>;
 friend class my_bidirectional_iterator<node<T>,T*,T&>;
 friend class my_bidirectional_iterator<node<T>,const T*,const T&>;

---

Pre-(Increment/Decrement) usually return references.

 my_bidirectional_iterator operator++();
 my_bidirectional_iterator operator--();
 // I would have done this.
 my_bidirectional_iterator& operator++();
 my_bidirectional_iterator& operator--();

---

It is a requirement of bi-directional iterators that they are default constructible.

 private:
 explicit my_bidirectional_iterator(Value* p=0):pos_(p) {}

Making this private and not having a default constructor does not allow this. As this becomes your default constructor.

---

This is old school

 typedef my_list_iterator<T> iterator;

More modern:

 using iterator = my_list_iterator<T>;

---

 // constructors
 // copy constructor
 // assignment operator
 // destructor

No move Move Constructor or Move Assignemtn?

 my_list(my_list&& move);
 my_list& operator=(my_list&& move);

---

 // iterators
 iterator begin();
 iterator end();
 const_iterator begin() const; // These can be marked cost.
 const_iterator end() const; // So they can be used from a const context.

There are a couple more you are missing.

 // Ability to force const_iterators even in a non const context.
 const_iterator cbegin() const;
 const_iterator cend() const;
 // The reverse versions of all the above.
 std::reverse<iterator> rbegin();
 std::reverse<iterator> rend();
 std::reverse<const_iterator> rbegin() const;
 std::reverse<const_iterator> rend() const;
 std::reverse<const_iterator> crbegin() const;
 std::reverse<const_iterator> crend() const;

---

Similar to move construction of the list. You should be able to move data into the list.

 iterator insert(iterator,T const&);
 iterator insert(iterator,T&&); // The move version.
 // if you are brave you can also try the emplace
 template<typename... Args>
 iterator emplace(Args...&& val);

---

Some for push_X() as for insert.

 void push_back(const T& t) {insert(end(),t);}
 void push_front(const T& t) {insert(begin(),t);}

---

The check for (this!=&rhs) is a false optimization. Its actually a pesimization of the normal path.

First Note. Yes we should handle self assignment. But we should note it is exceedingly rare and barely ever happens. In most normal code this will never happen. So you are effectively making the normal path slightly less effecient.

template<class T> my_list<T>& my_list<T>::operator=(const my_list& rhs)
{
 if (this!=&rhs)
 {
 clear();
 create(rhs.begin(),rhs.end());
 }
 return *this;
}

This is so common that this is a C++ idiom. It is called the Copy and Swap Idiom (it will turn up when you google it).

my_list<T>& my_list<T>::operator=(my_list const& rhs)
{
 my_list copy(rhs);
 copy.swap(*this);
 return *this;
}

In this case we always make a copy. Which you have to do anyway in normal circumstances. But there is no branch (so no CPU pipeline stalls) and no expression test. It also defines the copy assignment in terms of the copy constructor so you only need to get that correct.

---

Uneeded test for zero size. It just makes the code more complicated and achieves nothing.

template<class T> void my_list<T>::clear()
{
 if (size_!=0)
 {
 node<T>* first = head_;
 while (first!=0)
 {
 node<T>* next = first->next;
 delete first;
 first = next;
 }
 }
 head_=tail_=0;
 size_=0;
}

Also you should not use 0 as a pointer value. Use nullptr it is type safe and makes the code easier to read as you are being explicit about using pointers.

---

Yes there is a bug in this.

my_list<T>::insert(iterator pos,const T& t)

There are potentially two calls to new but only one element is added to the list so you are leaking p sometimes.

Also if pos does not have a node is it not the end of the list so you should be adding it to the `tail not the head?

You also need a special case for the empty list.

---

Comment inline

template<class T> typename my_list<T>::iterator my_list<T>::erase(iterator pos)
{
 node<T> *p = pos.pos_;
 // I suppose it is illegal to erase the end iterator.
 if (p->next!=0)
 p->next->prev = p->prev;
 else {
 tail_ = p->prev;
 // Don't we also need to remove the next item from the list.
 tail->next = nullptr
 }
 if (p->prev!=0)
 p->prev->next = p->next;
 else
 head_ = p->next;
 // If you delete the last node don't you have to reset tail as well?

---

I am not sure I would have a create.

template<class T> void my_list<T>::create()
{
 head_=tail_=0;
 size_ = 0;
}

I would have a default constructor set these to nullptr and 0 respectively. Then you can chain the default constructor from the copy/move constructor.

 my_list()
 : head(nullptr)
 , tail(nullptr)
 , size(0)
 {}
 explicit my_list(size_type n,const T& t=T())
 : my_list()
 {
 resize(n, T);
 }
 my_list(const my_list& rhs)
 :mylist()
 {
 for (size_type i=0;i!=n;++i)
 push_back(t);
 }

• L. F.: I don't really like the idea of making node, iterator, etc. member classes. I would also implement them as free classes. In particular, this will cause template instantiation problems if you add, say, allocator support.
• Loki Astari: @L.F. Can you explain more (maybe a gist) I am not sure why adding allocator support would make private classes would be a problem.
• L. F.: For example, list<T, A> and list<T, B> will instantiate two node classes. This can be a problem if you use many different kinds of allocators
• Loki Astari: @L.F. Ahh as you mean you can splice the list together? Hold I don't think that matters. Unless the allocaters are the same you can't splice list (nodes internal or external).
• L. F.: No, I mean that would cause unnecessary template instantiation. We don't want to instantiate list<T, A>::node and list<T, B>::node separately.