Yet another doubly linked list (follow-up)

Question

I've integrated the feedback from my previous question "Yet another doubly linked list ". In addition to that the list now uses the copy and swap idiom. It also has a very simple iterator to enable it to work with a ranged for loop.
So far everything works but I'm not very confident about this code. I would like some feedback specifically on whether the copy and swap idiom is employed correctly.
To keep it simple the iterator only implements the bare minimum required to traverse the list.
As more of a sidenote I'm also curious if this code is easy to read/has acceptable formatting or how to improve on those aspects.

Code:

#include <cstddef>
#include <initializer_list>
#include <iostream>
#include <utility>
template<typename T>
class DoublyLinkedList {
public:
 friend void swap(DoublyLinkedList& first, DoublyLinkedList& second) {
 using std::swap;
 swap(first.head, second.head);
 swap(first.tail, second.tail);
 swap(first.list_size, second.list_size);
 }
 DoublyLinkedList()
 : head{nullptr}
 , tail{nullptr}
 , list_size{0}
 {}
 DoublyLinkedList(std::initializer_list<T> init_list)
 : DoublyLinkedList{}
 {
 for (auto const& value : init_list) {
 push_back(value);
 }
 }
 DoublyLinkedList(DoublyLinkedList const& rhs)
 : DoublyLinkedList{}
 {
 Node* node = rhs.head;
 while (node) {
 push_back(node->data);
 node = node->next;
 }
 }
 DoublyLinkedList(DoublyLinkedList&& rhs) noexcept
 : DoublyLinkedList{}
 {
 swap(*this, rhs);
 }
 ~DoublyLinkedList() noexcept {
 clear();
 }
 DoublyLinkedList& operator=(DoublyLinkedList rhs) {
 DoublyLinkedList tmp(rhs);
 swap(*this, tmp);
 return *this;
 }
 DoublyLinkedList& operator=(DoublyLinkedList&& rhs) noexcept {
 clear();
 swap(*this, rhs);
 return *this;
 }
 bool is_empty() const {
 return head == nullptr;
 }
 int const& size() const {
 return list_size;
 }
 void clear() {
 while (head) {
 pop_front();
 }
 head = nullptr;
 tail = nullptr;
 list_size = 0;
 }
 void push_front(T const& value) {
 Node* node = new Node{head, nullptr, value};
 if (!head) {
 tail = node;
 }
 else {
 head->prev = node;
 }
 head = node;
 ++list_size;
 }
 void push_back(T const& value) {
 Node* node = new Node{nullptr, tail, value};
 if (!tail) {
 head = node;
 }
 else {
 tail->next = node;
 }
 tail = node;
 ++list_size;
 }
 void pop_front() {
 Node* node = head;
 head = head->next;
 delete node;
 if (head) {
 head->prev = nullptr;
 }
 else {
 tail = nullptr;
 }
 --list_size;
 }
 void pop_back() {
 Node* node = tail;
 tail = tail->prev;
 delete node;
 if (tail) {
 tail->next = nullptr;
 }
 else {
 head = nullptr;
 }
 --list_size;
 }
 T& front() const {
 return head->data;
 }
 T& back() const {
 return tail->data;
 }
 struct Node {
 Node(Node* next, Node* prev, T data)
 : next{next}
 , prev{prev}
 , data{data}
 {}
 Node* next;
 Node* prev;
 T data;
 };
 class DLLIterator {
 friend class DoublyLinkedList;
 public:
 DLLIterator()
 : DLLIterator{nullptr}
 {}
 DLLIterator(Node* node)
 : node{node}
 {}
 DLLIterator(DLLIterator const& rhs) = default;
 DLLIterator(DLLIterator&& rhs) noexcept = default;
 ~DLLIterator() noexcept = default;
 DLLIterator& operator=(DLLIterator const& rhs) = default;
 DLLIterator& operator=(DLLIterator&& rhs) noexcept = default;
 T& operator*() {
 return node->data;
 }
 DLLIterator& operator++() {
 node = node->next;
 return *this;
 }
 DLLIterator operator++(int) {
 DLLIterator tmp{*this};
 ++*this;
 return tmp;
 }
 DLLIterator& operator--() {
 node = node->prev;
 return *this;
 }
 DLLIterator operator--(int) {
 DLLIterator tmp{*this};
 --*this;
 return tmp;
 }
 bool operator==(DLLIterator const& rhs) {
 return node == rhs.node;
 }
 bool operator!=(DLLIterator const& rhs) {
 return !(*this == rhs);
 }
 private:
 Node* node;
 };
 DLLIterator begin() const {
 return DoublyLinkedList<T>::DLLIterator(head);
 }
 DLLIterator end() const {
 return DoublyLinkedList<T>::DLLIterator(tail->next);
 }
 void insert(DoublyLinkedList<T>::DLLIterator pos, T value) {
 if (!pos.node) {
 return;
 }
 if (pos.node == head) {
 push_front(value);
 return;
 }
 Node* new_node = new Node{pos.node, pos.node->prev, value};
 pos.node->prev = new_node;
 new_node->prev->next = new_node;
 ++list_size;
 }
 void erase(DoublyLinkedList<T>::DLLIterator pos) {
 if (!pos.node) {
 return;
 }
 if (pos.node == head) {
 pop_front();
 return;
 }
 if (pos.node == tail) {
 pop_back();
 return;
 }
 Node* delete_this = pos.node;
 pos.node->prev->next = pos.node->next;
 pos.node->next->prev = pos.node->prev;
 delete delete_this;
 --list_size;
 }
private:
 Node* head;
 Node* tail;
 std::size_t list_size;
};
int main() {
 DoublyLinkedList<int> dll{1, 2, 3};
 for (auto const& it : dll) {
 std::cout << it << "\n";
 }
}

Answer 1

1. Use auto freely. Almost Always auto is a good idea to reduce repetition and avoid costly mismatches.

2. Node is an implementation-detail, and should thus be private.

3. DLLIterator has the wrong connotation. Anyone not thinking of dynamically linked libraries there?

4. Well, your iterator-interface is badly broken. You pretend to have bidirectional iterators (which would allow you to easily provide reverse-iterators too), but your end-iterator is the null iterator, so cannot be decremented.

   In addition, the obfuscation in .end() results in UB if the list is empty.

   How to fix that? Simple, by moving the pointers from Node into a base-class, and having a member of that type instead of two loose pointers in the list-class, so there always is a full circle:

   template <class T>
   class DoublyLinkedList {
    struct NodeBase {
    NodeBase* next;
    NodeBase* prev;
    };
    struct Node : NodeBase {
    T data;
    };
    NodeBase base { &base, &base };
    std::size_t n = 0;
    ...
   };
   

   While it will make moveing and swapping a bit more complicated, it will make other members more elegant by removing special cases.

5. None of your members are marked noexcept or constexpr. Add that where appropriate.

6. You don't support constructing from an iterator-range. Fix that, and you can then make the copy-ctor and initializer_list-ctor delegate to that.

7. It's curious to implement the dtor in terms of .clear(), instead of the other way around. Oh well, it's unlikely to be significant.

8. Your implementation of operator= is very surprising in all kinds of ways.

   1. If you have one getting its argument by value (whether the caller moves or copies into the argument), that is customarily the only one.
   2. Your implementation of operator=(DoublyLinkedList) does a copy inside its body. So, why pass by value, instead of constant reference?
   3. Your move-assignment-operator clears the target before swapping. While that is acceptable from a correctness standpoint, it's inefficient. Remember that moving should be efficient.

9. .is_empty() is foreign to C++. It should be empty().

10. .size() should return by value. An int (or better std::size_t) is trivially copied, using a constant reference just makes errors more likely. Luckily, it should be inlined and thus the potential inefficiency fixed.

11. There should be emplacing variants of .push_back() and .push_front().

12. There should be move-variants of .push_back() and .push_front(). As all of them can delegate to the emplacing variants, that should not be too verbose.

13. .front() and .back() should respect the const-ness of the container. And there should be variants for non-const use.

14. .insert() and .erase() should not silently do nothing when used with null iterators. Abort, or better ignore the situation and let it blow up by itself.

About the test in main():

15. v is more appropriate for an element than it.

16. It's potentially slightly more efficient to stream a single char instead of a length-1 string-literal.

• yuri: 5. None of your members are marked noexcept or constexpr. Add that where appropriate. If I knew where it was appropriate to add those I would have done so already. Are there any preferred texts to help learn about when these keywords are applicable?
• Deduplicator: Well, mark every (member- / free) function / ctor which cannot throw unconditionally noexcept (conditional noexcept is a bit more difficult). Mark functions and ctors useful for creating compile-time-constant-expressions constexpr (probably only the default-ctors for your example).
• yuri: Regarding 8.2. Your implementation of operator=(DoublyLinkedList) does a copy inside its body. So, why pass by value, instead of constant reference? it was recommended in that SO answer I linked about the copy and swap idiom
• yuri: Would it be correct if you remove DoublyLinkedList tmp(rhs); and change the swap to swap(*this, rhs); ?
• Deduplicator: @yuri: Yes, either pass by constant reference, or cut out the extra copy and probably the alternative passing by rvalue-reference.

Answer 2

There's no need to make Node public, put class definition in private area of DoublyLinkedList.

Currently, it lacks member typedefs, like value_type or iterator (and lacks a const_iterator at all).

DLLIterator lacks typedefs for std::iterator_traits.

DoublyLinkedList& operator=(DoublyLinkedList rhs) {
 DoublyLinkedList tmp(rhs);

Here, why do you perform two value copies?

DoublyLinkedList& operator=(DoublyLinkedList&& rhs) noexcept {
 clear();

You don't need to call clear() here (rhs's destructor will call it once again, only to find out that both head and tail are already null).

void clear() {
 while (head) {
 pop_front();
 }
 head = nullptr;
 tail = nullptr;

Those two assignments are excess, they are done in pop_front.

 Node(Node* next, Node* prev, T data)
 : next{next}
 , prev{prev}
 , data{data}
 {}

Is this constructor really necessary? If you remove it, nodes still can be initialized as Node{next, prev, data}.

 DLLIterator(DLLIterator const& rhs) = default;
 DLLIterator(DLLIterator&& rhs) noexcept = default;
 ~DLLIterator() noexcept = default;
 DLLIterator& operator=(DLLIterator const& rhs) = default;
 DLLIterator& operator=(DLLIterator&& rhs) noexcept = default;

Const-ref versions are probably non-throwing as well, object's state is but a single pointer.

DLLIterator end() const {
 return DoublyLinkedList<T>::DLLIterator(tail->next);
}

This version results in UB on an empty container, and for a non-empty container tail->next is always null, so return DLLIterator(nullptr); is better.

There's one serious consideration here, though: is end() is always an iterator that points to null, you have to define reverse_iterator and rbegin() separately (completely symmetrical to iterator and begin()).

DoublyLinkedList<T>::DLLIterator

This is the same as DLLIterator so the qualification can be removed everywhere.

void insert
void erase

These methods are probably more useful if they return something, for instance, an iterator to the element inserted/past the element erased.

• yuri: If you make Node private then you need to forward declare it but it will still result in errors like ` error: invalid use of incomplete type` hence why I declared it before the Iterator.
• wooooooooosh: Any number of access specifiers may appear within a class, in any order.
• bipll: @yuri Simply put private: BEFORE Node definition and public: RIGHT AFTER it.

Answer 3

Your swap function does nothing more than call swap on every member. So don’t write it! template< class T > void swap( T& a, T& b ); will work just fine. The template is constrained to T being move-constructable and move-assignable.

That is, in C++17 swap is generated for you in terms of move construction and move assignment.

So don’t write swap. Write the move ctor and move assignment operator as primitives and swap calls them; you wrote it the other way around.

---

To make an iterator, use Boost.Iterator either adaptor or facade probably) and it will be easy with minimal code, rather than broken and incomplete.

---

Instead of the default constructor’s init list, use inline initializers on the data members. Then you don’t need to defer to that common form in the other constructors, either!

Node* head = nullptr;
Node* tail = nullptr;
std::size_t list_size = 0;

---

The standard guidelines C.149 indicates that your use of a naked new and delete should be flagged.

Have you considered using unique_ptr or otherwise tightly wrapping the pointer with a class that has a destructor?

• yuri: Are inline initializers preferred over init list now? Which one is better style?
• JDługosz: inline initializer is better style when it applies universally, such as pointers = nullptr. In this case, you will not need to repeat the three initializers on every constructor, which you do now by delegating to the default constructor. So it's better because you don’t need to do more work!

Answer 4

pop_front() and pop_back() result in UB if list is empty because you are dereferencing pointer without checking for nullptr.

• yuri: Same as the STL list from which I copied this behavior
• wooooooooosh: I am talking about your implementation. this line: head = head->next; What happens if head is nullptr?