13

The meaning of the iterator passed as a position hint to std::set::insert(iterator position, const value_type& val) and std::multiset::insert(iterator position, const value_type& val) changes between C++98 and C++ 11. Is there an easy way at compile-time to detect which is in use and use different code?

A general check on C++11 does not appear to be a good idea (1, 2), and I didn't see a suitable Boost.Config macro.

Specifically, the documentation for C++98 says:

The function optimizes its insertion time if position points to the element that will precede the inserted element.

while for C++11 it says:

The function optimizes its insertion time if position points to the element that will follow the inserted element (or to the end, if it would be the last).

This matters because the hint effects the complexity of the insertion call. If the hint is correct, the complexity is only an amortized constant. But if it's not, it's logarithmic in size.

Update

As so nicely described below by JerryCoffin, the C++98 specification is, essentially, a typo.

Community
  • 1
  • 1
Jon
  • 438
  • 3
  • 14
  • 2
    IIRC the standard was changed to match (most of) the existing implementations, so your test may not be such a good idea. At least you should check the compilers you are using. – Marc Glisse Aug 11 '14 at 19:40
  • I just verified this in the standard; I had no idea. Alas, no, there is no way to check but as Marc says you don't really need to. Assume the C++11 behaviour and you should be okay. – Lightness Races in Orbit Aug 11 '14 at 19:41
  • 1
    @Jerry: Bah, literally _just_ found that myself (well, http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#233 anyway, and [n1780](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html)). You may take the answer. – Lightness Races in Orbit Aug 11 '14 at 19:45
  • All. That is great to know (tho' now I have some other old code to fix :P ). Thanks. :) – Jon Aug 11 '14 at 19:54

1 Answers1

15

This was the subject of a defect report, LWG issue #233, and n1780.

As noted there, it was apparently a simple error in editing the C++98 standard.

Stepanov's original implementation worked according to the current specification, and as far as I know most (all?) implementations since have done the same (though there is one that looks both before and after the hinted location, so you'll get optimal behavior if you specify either one).

This also makes it possible to hint that an insertion will be at the beginning of the set, which wasn't possible under the previous specification.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • 1
    which implementation looked at before and after? That's interesting to me – Mooing Duck Aug 11 '14 at 20:37
  • @MooingDuck: I don't remember. It's mentioned in the DR, and at the time I managed to track down which one it was, but in the ~15 years since, I'm afraid I've forgotten which it was. – Jerry Coffin Aug 11 '14 at 21:11