22

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).

Tanveer Badar
  • 5,438
  • 2
  • 27
  • 32
SylvainD
  • 1,743
  • 1
  • 11
  • 27
  • 2
    The best answer I can think of is that the interface is often specified in terms of "what usage is encouraged", as well as "what can be implemented efficiently". Non-sequence containers can still be iterated over (so they need to have `begin()` and `end()`, but they are not really intended for situations where you need to pick just the first element from them. So they don't have `front()`, even though it *could* be implemented – jalf Jun 07 '13 at 10:27
  • Ok that's what I was expecting then. Thanks everyone for the answers. Also, wouldn't it be easier (as in 'reduce amount of duplicated code') to have the method defined for every container without any difference ? – SylvainD Jun 07 '13 at 10:39
  • I'm not exactly being constructive here, but: http://kera.name/articles/2010/08/it-is-not-called-the-stl-mmkay/ – wolfgang Jun 07 '13 at 10:56
  • 1
    @wolfgang I don't know about you, but I am more inclined to follow the terminology used by Herb Sutter, Bjarne Stroustrup and, most other C++ gurus and members of the standardization committee, than one SO user whose uncontrolled OCD just *has* to spill out and try to create confusion where none exists. It is very very very clear what people mean when they say "the STL". They mean "the subset of the C++ standard library which is based on the *actual* STL library". The day you can get Scott Meyers to rename his book "Effective STL" is the day I'll stop using the name – jalf Jun 07 '13 at 11:05
  • @wolfgang let's be realistic: we know perfectly well what people mean when they say "the STL", and we don't have *an alternative* name for it. So why on Earth should we ditch the perfectly good name that we have? (and you're right, this isn't constructive, and isn't even on topic. This was not a question about the terminology of the C++ standard library and the STL) – jalf Jun 07 '13 at 11:07
  • 2
    @jalf Wouldn't a simple "I disagree" have sufficed and thus have been more constructive and on-topic? – wolfgang Jun 07 '13 at 11:13
  • front() is just a syntax sugar function for *begin(). Such are only included where considered a really common use case. – Balog Pal Jun 07 '13 at 11:28
  • @jalf *"This was not a question about the terminology of the C++ standard library and the STL."* - which is probably why it wasn't an answer but a comment which don't have to be strictly on-topic but may provide *comments* on other possible problems of a question (which I myself don't want to imply the inaccurate terminology to be, though). – Christian Rau Jun 07 '13 at 12:01
  • I'm 100% with @jalf here. Call it the STL. I don't care. *everybody knows what you mean*. Do you annoyingly correct people when they call `x ? y : z` the "ternary operator?" Because that's not what that is called either, but you know what they mean. – John Dibling Jun 07 '13 at 12:07
  • 1
    http://stackoverflow.com/questions/16665103/is-there-a-design-reason-why-stdset-doesnt-have-front-and-back-member-function – NoSenseEtAl Jun 07 '13 at 12:20

5 Answers5

8

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.

Edward Strange
  • 40,307
  • 7
  • 73
  • 125
  • 25
    Personally I think there's *complete* clarity which entry `front()` should mean if it did exist. It would mean the one referred to by `begin()`, same as it does for sequences. Maps have an order, and all you need to have a "first element" is an order and to not be empty. The fact that they are trees is mostly hidden by the API. You cannot iterate a `std::map` in pre-order, post-order, or insertion order, and so you shouldn't expect `front()` to have anything to do with those things either. – Steve Jessop Jun 07 '13 at 11:17
  • 2
    "all you need to have a "first element" is an order and to not be empty" it occurs to me that mathematically speaking this is a howler on my part. Infinite sets can have an order and yet not have a least element. What I let go without saying, is that `std::map` is finite. – Steve Jessop Jun 07 '13 at 11:28
  • Perhaps it's because first and last in `map` are not stable. There's no `push_front` because that's gibberish for a balanced binary tree, maybe for the same reason `front` was omitted or because they felt the two go together. – Edward Strange Jun 07 '13 at 22:08
5

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

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

0decimal0
  • 3,884
  • 2
  • 24
  • 39
Enigma
  • 1,699
  • 10
  • 14
  • 19
    but there is an ordering in a map – yuri kilochek Jun 07 '13 at 10:18
  • 1
    they have a weak ordering. Theoretically two or more entries could be front. In some cases all entries should be front. – Enigma Jun 07 '13 at 10:27
  • `Internally, the elements in a map are always sorted by its key following a specific strict weak ordering criterion indicated by its internal comparison object (of type Compare).` But as Eddie said, maps are trees, so front() doesn't make so much sense... – Gauthier Boaglio Jun 07 '13 at 10:28
  • 4
    @Enigma No, a map always has exactly one element in front (well, except when it is empty) – jalf Jun 07 '13 at 10:31
  • exactly for this reason i was expecting `std::map::front`/`back` to exitst. Iterating a map isnt that uncommong and inside the loop you know very well which is the first and the last element, but outside you dont :( – 463035818_is_not_an_ai May 19 '18 at 11:48
2

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.

Steve Jessop
  • 273,490
  • 39
  • 460
  • 699
0

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.

teh internets is made of catz
  • 1,450
  • 2
  • 13
  • 25
-2

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

Superman
  • 3,027
  • 1
  • 15
  • 10