mutable_set (Interface Augmentation)

In the bad old days std::set (and std::multiset) elements could be modified after being added, this is hazardous as there is no protection against breaking the std::set data structure by modifying the element in such a way that it changes its sort order.  The next version of C++ (C++0x) fixes this problem thus:

However it is still desirable to have an ordered set of elements that can be modified in such a way as to not affect their sort order.  The parts of the element that make up the element's key are the only parts that need to be immutable.  This problem can traditionally be solved in one of three ways (in decreasing order of undesirability):

1. Use const_cast

You can cast away the const from the reference given by dereferencing a std::set's iterator.  This may seem like an obvious solution to the problem however it is rather "hackerish" and gives rise to the problem of clients potentially being unaware that they can modify any part of the element via the non-const reference leading to subtle bugs if the std::set data structure becomes "broken".

2. Use mutable

You can make all the element's members that do not take part in std::set element ordering mutable, however this leads to const "setter" functions which are counter-intuitive.  If the element type is used elsewhere in a project (not in the mutable set) it may be unclear why some of the members are mutable.

3. Use std::map

You can use a std::map to store the element and have no mutability problems however if the key is not trivial then it is necessary to split the element class into two containing the key and non-key parts.  This is undesirable if the element class is used elsewhere in a project in a non-set context.

The Fourth Way .. Interface Augmentation

Using a std::map is the most desirable of the three options above however its shortcomings can be avoided by simply augmenting its interface via derivation.  Bjarne Stroustrup recommends interface augmentation in TC++PL by deriving from std::vector to provide an operator[] with arbitrary bounds (not 0 based) (25.6.1 Adjusting Interfaces).

Some people eschew the derivation of the standard library containers however there are only 3 main issues to be aware of:

1. As the container has public mutation member functions there is a need to ensure that the derived class invariant is not broken by calling these member functions.  This is only a problem if the derived class invariant consists of more than just the container's invariant and consists of state which depends on the container's state.  This should not be an issue if interface augmentation only is being performed.

2. Does such an "is-a" relationship make sense?  Is it important to know that your derived class "is-a" particular container (i.e. it is more than just an implementation detail)?  If not consider private inheritance and either wrap container member functions with new member functions or use using declarations to make particular container member functions accessible.  Again this should not be an issue if interface augmentation only is being performed.

3. A standard library container destructor is not virtual so you cannot delete the associated object via a pointer to the container (base class).  A lack of a virtual destructor does not necessarily prevent inheritance: the standard library already contains classes that are designed to be derived from but do not have a virtual destructor (e.g. std::iterator).

enum grade { A, B, C, D, E, F };

class student
{
public:
    typedef std::vector<grade> grades_t;
    typedef std::string key_type;
public:
    student(const std::string& aName) : iName(aName) {}
    const std::string& name() const { return iName; }
    const grades_t& grades() const { return iGrades; }
    void add_grade(grade aGrade) { iGrades.push_back(aGrade); }
    operator key_type() const { return key_type(iName); }
private:
    std::string iName;
    grades_t iGrades;
};

std::ostream& operator<<(std::ostream& aStream, grade aGrade)
{
    aStream << static_cast<char>(aGrade + 'A');
    return aStream;
}

std::ostream& operator<<(std::ostream& aStream, const student& aStudent)
{
    aStream << "Name: " << aStudent.name() << std::endl;
    aStream << "Grades: ";
    std::copy(aStudent.grades().begin(), aStudent.grades().end(), std::ostream_iterator<grade>(std::cout, " "));
    aStream << std::endl;
    return aStream;
}

int main()
{
    typedef lib::mutable_set<student> students;
    students s;
    s.insert(student("Mr Flibble"));
    students::iterator theStudent = s.find("Mr Flibble");
    theStudent->add_grade(B);
    theStudent->add_grade(C);
    std::copy(s.begin(), s.end(), std::ostream_iterator<student>(std::cout, " "));
}