Self-made list in c++

Question

list.h

class Link {
public:
    string value;
    Link(const string& v, Link* p = 0, Link * s = 0):
        value(v), prev(p), succ(s) {}
    Link* insert(Link* n);              // insert n before this object
    Link* add(Link* n);                 // insert n after this object
    Link* erase();                      // remove this object from list
    Link* find(const string& s);        // find s in list
    Link* const find(const string& s) const;                       
    Link* advance(int n) ;                // get the nth successor 

    Link* next() const { return succ; }
    Link* previous() const { return prev; }

private:
    Link* prev;
    Link* succ;
};

Can you tell me why we need two versions of find()

Link* find(const string& s);        // find s in list
Link* const find(const string& s) const;    

in this self-made double-linked list and what should the main difference be between these two versions?

Answer 1

The reason you want a const and a non-const version of the same member function is so you can call them on a const and non-const object:

Link link = ...;
link.find("hello"); // calls non-const find(), returns Link*

const Link clink = ...;
clink.find("goodbye"); // calls find() const

Although, your const version returns Link* const. That is a const pointer to Link. It would make more sense to return a const Link*, a pointer to const Link:

Link* find(const std::string& );
const Link* find(const std::string& ) const;

In this way, your const Link could still find entries - just not modify them. That would maintain const-ness. It makes sense to be able to look for things in a const collection as long as you don't modify them.

Answer 2

Can you tell me why we need two versions of find()

Yes. Consider this code:

const Link x{ "x" };
auto y = x.find("x");
// y will be a Link * const, meaning you cannot change the pointer 
// address (not interesting) but you can change the object at that address.

versus:

Link x{ "x" };
auto y = x.find("x");
// y will be a Link *, meaning you can change both the pointer address
// contained in y (not interesting) and the object at that address

The const version can be called on const instances (and const references and pointers to const instances). The non-const version will only be callable on non-const instances.

Either way, the signature of the const version is incorrect: you should return a pointer to a const value, not a const pointer to a non-const value.

That is, the function should be:

Link const * const find(const string& s) const;   
//   ^^^^^   ^^^^^

or

Link const * find(const string& s) const;   
//   ^^^^^   

but not:

Link * const find(const string& s) const;   
//     ^^^^^