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:

23.2.4/6 (N3000)
iterator of an associative container is of the bidirectional iterator category. For associative containers where the value type is the same as the key type, both iterator and const_iterator are constant iterators. It is unspecified whether or not iterator and con
st_iterator are the same type.

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) as doing so would yield undefined behaviour.  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).

Example thin wrapper template classes that augment std::map and std::multimap providing std::set and std::multiset equivalents can be downloaded here (v1.2).  All that is necessary to use an element in the augmented containers it to provide a nested type called "key_type" that is convertible/constructible from the element type.

Example usage:

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, " "));
}

In the above example if std::set was used instead of lib::mutable_set add_grade could not be invoked as it is a non-const member function.  A student's grades have no bearing on how they are ordered in the set, their order (and uniqueness) is determined by their name only.

Of course the augmented containers are not a full replacement for std::set and std::multiset which should still be used when the elements do not change once added.

Updated on 14 December 2010

You can e-mail comments to the author.

Back to home page