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:

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_t;
    students_t students;
    students.insert(student("Mr Flibble"));
    students_t::iterator theStudent = students.find("Mr Flibble");
    theStudent->add_grade(B);
    theStudent->add_grade(C);
    std::copy(students.begin(), students.end(), std::ostream_iterator<student>(std::cout, " "));
}