CODEWITHSUNDEEP
c++
Bob John
Bob John

Reputation: 3878

Copy constructor for a generic doubly-linked list

template <class T>
class list
{
public:
    //stuff
    list(const list &cctorList); //cctor
private:
    struct node
    {
       node *next;
       node *previous;
       T *info;
    }

    node *firstNode; //pointer to the first node (NULL if none)
    node *lastNode; //pointer to the last node (NULL if none)
}

I'm now trying to define list(const list &cctorList); //cctor but I'm running into trouble.

Here's what I have so far:

template <class T>
list<T>::list(const list &cctorList)
{
    node *another = new node;
    firstNode = another;
    another->previous = NULL;
    another->info = new T(*(cctorList->info));

    // ...
}

Is everything up to this point correct? Is there a way for me to recursively assign another->next? Also, is there an easier way to accomplish this using iterators?

Upvotes: 0

Views: 1006

Answers (1)

Jan Hudec
Jan Hudec

Reputation: 76246

  1. You should be using std::list. In fact, you should be using std::vector, because it is faster for most practical purposes (list is only faster if the objects are really large or really expensive to construct) and you don't need random access.

  2. new T(*(cctorList->info)); won't compile, because cctorList (list&) does not have operator-> and it does not have info member either.

  3. The copy constructor is best implemented in terms of the other, more primitive operations like push_back and iteration. So first do those and than the copy constructor becomes:

    template <class T>
list<T>::list(const list &cctorList)
{
    std::copy(begin(cctorList), end(cctorList), std::back_inserter(this));
}

    In fact I'd just template that constructor:

    template <class T, class Collection> list(const Collection &cctorList)

    (body remains the same). That works as copy constructor, but also allows copying from any other collection of any type that can be implicitly converted to T.

  4. The actual data should be held by value. I.e. the node should be defined as

    struct node
{
    node *next;
    node *previous;
    T info;
}

    you are copying the value anyway, so you don't need to do two separate allocations for node and T when one will do.

Edit: You say you want to learn concepts. But the most important concept of modern C++ is composition of algorithms. Their definitions are often trivial. Basic implementation of std::copy is just: 

template <typename InputIterator, typename OutputIterator>
OutputIterator copy(InputIterator begin, InputIterator end, OutputIterator out) {
    for(;begin != end; ++out, ++begin) *out = *begin;
}

Now this does not appear to allocate anything. The trick lies in the back_insertion_iterator. Insertion iterator is a trick to make this work without preallocating the sequences. It defines operator* using push_back on the underlying collection and ignores operator++. That satisfies "output iterator" concept, because it only guarantees to work when these two calls are strictly interleaved and makes algorithms work on many things from plain old arrays to output streams.

The other part is that while the trivial definitions are correct, they are not the actual definitions used in the library. The actual definitions in the library are optimized. E.g. usually std::copy will check whether the input iterators know their distance and if the output is insert operator to sequence with reserve operation and call it to avoid some allocations. Those are optimizations and depend on implementation details of the standard library.

You can go and write down the basic implementations of things from standard library and test they work the same if you want to understand them. But you should follow the way standard library defines things by building them up from simple helper bits like std::copy, std::swap, insertion iterator adapters and such. If you look in the standard library, most functions there are one-liners!

Edit2: Also with all the genericity the standard library provides, there are still bits criticized for not being generic enough. E.g. GotW #84: Monoliths "Unstrung" discusses which methods of std::string could be converted to generic algorithms.

Upvotes: 2

Related Questions