Why no front() method on std::map (and other associative containers from the STL)?

Question

The STL reference seems to make a conceptual difference between :

• 'Sequence containers' (array vector deque forward_list list) on one hand
• 'Associative containers' (set multiset map multimap unordered_set unordered_multiset unordered_map unordered_multimap) on the other hand.

Also, it seems like we have :

• all containers implementing a begin() method returning an iterator pointing to the first element in the container.
• only the sequence containers having a front() method returning a reference to the first element in the container.

My understanding is that the front() method could easily be defined in terms of the begin() method by just dereferencing its return value.

Thus, my question is : why isn't the front() method defined for all objects defining the begin() method ? (which should be every container really)

(I guess that from a semantic point of view, it doesn't make as much sense to get the first element from a map as it does for the first element from a vector but I was wondering if there was a more valid explanation).

Answer 1

You really have to ask the standards committee on that one (comp.lang.c++.std) but my guess is that yeah, it just doesn't make as much sense. Further there's not as much clarity as to what it would mean. Do you want the root, the pre-order first, post-order first, first you inserted...? With sequences it's quite clear: front is one side, back the other. Maps are trees.

Answer 2

Front() implies an ordering; "the first in the row".

Begin() implies lets start somewhere, no matter where.

Answer 3

I speculate that:

• front() and back() would not exist in Sequence if not for the fact that the interface was originally designed with mutable sequences in mind. front() makes most sense when you think about how you'd use it in combination with push_front() and pop_front(). For immutable sequences (of which the newcomer array is the only example in the standard, unless you count const vector), front() is a shorthand for *begin() that simply is not worth getting excited about.

• Since non-sequence ordered containers don't have push_front(), it was not thought worth giving them front() either. You can add entries to map, but you can't specify where in the order to add them since that's that the key is for. This is the difference between a sequence vs. an ordered collection.

• "Hang on", you say, "vector has front() but not push_front()". I suspect that this is because vector has back() -- if you're using back() then again it's "nice" to use front() to match it.

This is just speculation, though, based on what I know about designing useful/satisfying APIs, and my observation of the container APIs. I have no knowledge of Stepanov's thinking on the matter, or of any record of its discussion in the standard committee.

Answer 4

You are right, it could be implemented quite easily. But the thing is that these containers are designed for specific usages. Having a front() member implies that the goal of the container is to have an explicit order. Of course map values are ordered, but that's more a question of performance. And of course that whatever internal structure has to start somewhere (to provide begin()), but there's just sometimes no point in providing a front()or back().

Iterators are meant to traverse the data, front() members are meant to access the first element of an explicitely ordered collection. Accessing the first member of a map makes no sense because it is associative.

Answer 5

STL is designed to be traversed using iterators. So I guess front() only makes sense for containers like list and deque.