Templated doubly-linked-list

I've been wanting to revise what I knew on templated classes so thought I'd write a doubly linked list to practice.

It works fine, so all is well and good on that front, but is there something I've missed?

Current things I am aware of:

• naming - could be a little more explicit

• functionality - i.e. handling node* pointers so I could (for example) search for and delete a node containing a certain value, without scanning through the list twice.

I do plan to fix / add this later.

Specifically, I'm looking mainly for feedback on how I've done the templating, and any RAII issues, though I will happily take any further feedback.

Note that I've used .h as the interface header and .hpp for the implementation to separate the interface and implementation (using .hpp instead of .imp or similar as it is recognised type on my system). I understand that for the template to work for all types it needs to be in the header, otherwise each type to be used needs to be defined, correct?

I've been compiling with:


g++ -std=c++11 use_dllist.cpp -Wall -Wextra -pedantic -o dll.exe

dlllist.h:

#ifndef __d_l_list__
#define __d_l_list__
#include 
templateclass d_l_listnode
{
public:
   d_l_listnode* link[2] = {0,0};  //link[0] is headwise //link[1] is tailwise.
   T data;
};

template class d_l_list
{
    d_l_listnode* end[2] = {0,0};  //end[0] is head end[1] is tail
    int node_count = 0;

    void deep_copy(d_l_list& original,d_l_list& destination);

public:
    d_l_list();
    d_l_list(d_l_list&);
    d_l_list& operator=(d_l_list&);
    ~d_l_list();
    int  add_node(T data, int index);
    int  find_node(T data);
    bool del_node(int index);
    bool is_empty();
    int  get_node_count();
    void print_list(std::string delimiter);
    void print_list_debug();
};

#include "dllist.hpp"
#endif

dllist.hpp:

```
#include

template
d_l_list::d_l_list()
{
node_count = 0;
end[0] = NULL;
end[1] = NULL;
}

template
void d_l_list::deep_copy(d_l_list& original

File extensions

Separating the interface from the implementation is great. However, the .h/.hpp split is not obvious. The most frequent file extensions used for implementation files that cannot go into .cpp files are .inl (for inline) and .tpp (for template cpp). I know that at least some code editors or IDEs recognize the extension .inl (at least Code::Blocks), but many of them can be configured to recognize additional extensions anyway. Try to use something more obvious that .hpp for the implementation file.

Names

A few remarks related to names in general:

-
Try to write your preprocessor names in FULL_CAPS_CASE so that they can be identified with a single glance and not confused with regular function, class or variable names.

-
Also, your header guard names are incorrect: names with double underscores (anywhere in the name) are reserved for the implementers. Names beginning with an underscore followed by an uppercase letter are also reserved for the implementers. A good well-formed name for you header guard would be D_L_LIST_ since single trailing underscores are fine.

-
When possible, try to use the injected class name in a cass template. It allows to write shorter code and reduces the maintenance costs: if you change the template parameter name, you won't have to edit the lines where you used the injected class name. For example, your operator= would become:

d_l_list& operator=(d_l_list&);

-
print_list is a bad name for a method since you already know that you are printing a list. A better name could be print but we will see later a more idiomatic way to print things.

const-correctness

You should really take into account the const-correctness, which means that you should add const to specify that an object won't be modified:

-
operator= should take a const d_l_list& instead of a d_l_list& to assert that it will not modify the assigned variable.

-
All the methods that do not modify the class should be marked const:

bool is_empty() const;

And there are many such methods: print_list, print_list_debug, get_node_count, is_empty and find_node.

Printing stuff

The idiomatic way to print stuff in C++ is to overload operator



• 0 as in d_l_listnode* link[2] = {0,0};.




You are using C++11. The C++11 way to represent a null pointer constant is nullptr. The two lines above could be rewritten as:



• end[0] = nullptr;






• d_l_listnode* link[2] = {nullptr,nullptr};.




In-class initializers and default construction

You used in-class initializers to default-initialize the members of d_l_list. However, you initialized them with the exact same values in the default constructor. Actually, if you use the explicitly defaulted default constructor, it will use the in-class initializers to initialize the members. Therefore, you can simply define it as such:

template
d_l_list::d_l_list()
    = default;

Use the copy-and-swap idiom

The copy-and-swap idiom is an idiom that lets you write correct and short code. In short, the copy should be written in the copy constructor of the class while the operator= should rely on the copy constructor to perform the copy. Here is what it would look like for your class:

template
d_l_list::d_l_list(const d_l_list& other)
{
  // Uninitialized members use the
  // in-class initializers here, that's
  // why I left out the initialization part

  d_l_listnode* current_node = other.end[1];
  while(current_node)
  {
    this->add_node(current_node->data, 0);
    current_node = current_node->link[0];
  }
}

template
d_l_list& d_l_list::operator=(d_l_list other)
{
  swap(*this, other);
  return *this;
}

In short, operator= performs a copy of other thanks to the copy constructor and then swaps the contents of this and other. Then, other is destructed and its contents (the original contents of this) are cleaned. The post I linked goes further into the details and is really worth reading. Anyway, using the copy-and-swap idiom is safe, efficient enough, and allows you to remove the deep_copy` method.

StackExchange Code Review Q#64974, answer score: 16