Immutable C++ container class

Question

Say that I have a C++ class, Container, that contains some elements of type Element. For various reasons, it is inefficient, undesirable, unnecessary, impractical, and/or impossible (1) to modify or replace the contents after construction. Something along the lines of const std::list<const Element> (2).

Container can meet many requirements of the STL's "container" and "sequence" concepts. It can provide the various types like value_type, reference, etc. It can provide a default constructor, a copy constructor, a const_iterator type, begin() const, end() const, size, empty, all the comparison operators, and maybe some of rbegin() const, rend() const, front(), back(), operator[](), and at().

However, Container can't provide insert, erase, clear, push_front, push_back, non-const front, non-const back, non-const operator[], or non-const at with the expected semantics. So it appears that Container can't qualify as a "sequence". Further, Container can't provide operator=, and swap, and it can't provide an iterator type that points to a non-const element. So, it can't even qualify as a "container".

Is there some less-capable STL concept that Container meets? Is there a "read-only container" or an "immutable container"?

If Container doesn't meet any defined level of conformance, is there value in partial conformance? Is is misleading to make it look like a "container", when it doesn't qualify? Is there a concise, unambiguous way that I can document the conformance so that I don't have to explicitly document the conforming semantics? And similarly, a way to document it so that future users know they can take advantage of read-only generic code, but don't expect mutating algorithms to work?

What do I get if I relax the problem so Container is Assignable (but its elements are not)? At that point, operator= and swap are possible, but dereferencing iterator still returns a const Element. Does Container now qualify as a "container"?

const std::list<T> has approximately the same interface as Container. Does that mean it is neither a "container" nor a "sequence"?

Footnote (1) I have use cases that cover this whole spectrum. I have a would-be-container class that adapts some read-only data, so it has to be immutable. I have a would-be-container that generates its own contents as needed, so it's mutable but you can't replace elements the way the STL requires. I yet have another would-be-container that stores its elements in a way that would make insert() so slow that it would never be useful. And finally, I have a string that stores text in UTF-8 while exposing a code-point oriented interface; a mutable implementation is possible but completely unnecessary.

Footnote (2) This is just for illustration. I'm pretty sure std::list requires an assignable element type.

Answer 1

The STL doesn't define any lesser concepts; mostly because the idea of const is usually expressed on a per-iterator or per-reference level, not on a per-class level.

You shouldn't provide iterator with unexpected semantics, only provide const_iterator. This allows client code to fail in the most logical place (with the most readable error message) if they make a mistake.

Possibly the easiest way to do it would be to encapsulate it and prevent all non-const aliases.

class example {
    std::list<sometype> stuff;
public:
    void Process(...) { ... }
    const std::list<sometype>& Results() { return stuff; }
};

Now any client code knows exactly what they can do with the return value of Results- nada that requires mutation.

Answer 2

As long as your object can provider a conforming const_iterator it doesn't have to have anything else. It should be pretty easy to implement this on your container class.

(If applicable, look at the Boost.Iterators library; it has iterator_facade and iterator_adaptor classes to help you with the nitty-gritty details)