Comments on LWG issue 233:
Insertion hints in associative containers

Contents

• Introduction
• Current Practice
• Proposal
  • Before, not after
  • As close as possible to hint
  • Equal range stability
  • Insert without hint
  • Efficiency Concerns
  • Prior Art
  • Summary
  • Proposed Wording
• Acknowledments

Introduction

LWG issue 233 concerns the semantics of the "hint" in the insert member of associative member containers. The current standard reads:

There are two things wrong with this requirement.

1. The complexity column implies that insertion of t right after p is the preferred location, whereas sequence containers have the semantics of insert t before p.
2. p is referred to as a hint only (for performance purposes), rather than a preferred insertion location in a multi(map/set).

The first imperfection is arguably a simple "think-o" in the original standard. It should have stated before instead of after. How else is one to suggest that an element should be inserted before the first element? And with after semantics, what does after end() mean? Whereas with before semantics, every valid iterator used as a hint into a container has a well defined meaning, and any location can be specified.

The second problem reflects a lost opportunity. Especially in the case of multimap, but also even in multiset, just because two keys are equivalent, it doesn't mean that there is no extra information in the value_type. And the order in which those elements appear within the equal_range may impart vital information to the client. For example it might be that elements later in an equal_range represent elements that were inserted at a later time than prior elements in the equal_range. And that information may be important to the client. There is no need for the client to also have to store a time stamp for this purpose if he can simply control the ordering of elements within an equal_range.

The current proposed resolution was last actively discussed in the late 2001 / early 2002 time frame. This is significant because at that time, the LWG was only fixing defects, and specifically not entertaining design improvements. It is now 2005 and the committee is entertaining improvements for C++0X. And one of the big improvements that can be made in this area is to give the clients of associative containers control over the ordering of elements within an equal_range.

For example, what should the following code output?

#include <map>
#include <string>
#include <utility>
#include <iostream>

template <class Map>
void
display(const Map& m)
{
    for (typename Map::const_iterator i = m.begin(), e = m.end(); i != e; ++i)
        std::cout << '(' << i->first << ", " << i->second << ") ";
    std::cout << '\n';
}

int main()
{
    typedef std::multimap<int, std::string> Map;
    typedef std::pair<int, std::string> value_type;
    Map m;
    m.insert(value_type(0, "zero"));
    m.insert(value_type(1, "one"));
    m.insert(value_type(2, "two"));
    display(m);
    m.insert(m.find(1), value_type(1, "ONE"));
    display(m);
}

The current standard isn't really clear, but implies:

(0, zero) (1, one) (2, two)
(0, zero) (1, one) (1, ONE) (2, two)

That is, the new element is inserted after the current "equal element". With such an implementation, there is no way to store a (0, ZERO) such that the new element becomes the first element in the sequence:

(0, zero) (1, one) (2, two)
(0, ZERO) (0, zero) (1, one) (2, two)

The current proposed resolution does not solve this problem. It simply swaps the word adjacent for after to clarify that an implementation is allowed (but not required) to first check prior to the hint. This gives library vendors leeway, but does not give the client control of equal_range ordering.

Current Practice

A brief survey of current library implementations reveals differing behavior. Though as the text in LWG issue 233 argues, all implementations can be seen as conforming on this point.

The following libraries

Dinkumware
gcc prior to version 4
Metrowerks CodeWarrior
STLport

output:

(0, zero) (1, one) (2, two)
(0, zero) (1, ONE) (1, one) (2, two)

Rogue Wave, and possibly gcc 4.0 output:

(0, zero) (1, one) (2, two)
(0, zero) (1, one) (1, ONE) (2, two)

That is, today control over equal_range ordering, if it can be obtained at all, is not portable (even across different versions of the same library). And the current (adjacent) resolution to LWG issue 233 is set to cement that fact.

Proposal

Before, not after

This paper proposes to make the output of the code example above deterministic by specifying that before semantics should be used instead of adjacent or after semantics, both for consistency with sequence containers, and so that insert before or after any element in the sequence can be specified (including before begin()).

If this proposal is accepted then the above program will portably display:

(0, zero) (1, one) (2, two)
(0, zero) (1, ONE) (1, one) (2, two)

This is new functionality, not available in C++03 (at least not portably). This paper submits that this new functionality is valuable, and costs virtually nothing in terms of code size, computational expense, or vendor effort. Clients of std::multiset and std::multimap will be able to view equal_range's as sub-sequences within the container. And will be able to control the order within those sub-sequences throughout the lifetime of the container.

Note that specifying before semantics does not prohibit an implementation from checking after the hint. It only means that implementations must prefer the before location. A subsequent after check could optionally be implemented at the vendor's discretion.

The specification of before semantics is a giant step forward but only gives the client partial control over the ordering within an equal_range. If the hint turns out to be wrong, the client still looses control over where within an equal_range the new element will be inserted.

As close as possible to hint

Andrew Koenig proposed in 2000 the "as close as possible to hint" rule:

The proposed resolution was that the new element should always be inserted as close to the hint as possible. So, for example, if there is a subsequence of equivalent values, then providing a.begin() as the hint means that the new element should be inserted before the subsequence even if a.begin() is far away.

This allows code to always append (or prepend) an equal range with something as simple as:

m.insert(m.end(), value_type(an_int, the_string));

or

m.insert(m.begin(), value_type(an_int, the_string));

Without this suggestion, the semantics of append (or prepend) to an equal range is somewhat more cumbersome to code:

int an_int = key;
m.insert(m.upper_bound(an_int), value_type(an_int, the_string));

If inserting a nearly sorted range into a multimap/set (and for whatever reasons you cannot use the iterator-range insert member), then Andrew's suggestion becomes more than just a more convenient interface; it becomes computationally more efficient while ensuring that equal ranges within the source remain stable as they are inserted into the multiset or multimap target.
For example:

while (inserting)
{
    ...
    int key = obtain_int();
    ...
    string value = obtain_string();
    m.insert(m.end(), value_type(key, value));
}

vs.

while (inserting)
{
    ...
    int key = obtain_int();
    ...
    string value = obtain_string();
    m.insert(m.upper_bound(key), value_type(key, value));
}

When the key's are encountered in nearly sorted order (and starting with an empty container), then the former loop has O(N) complexity while the latter loop has O(N*log(N)) complexity. If one executed the former loop in order to maintain efficiency, but without the "as close to the hint as possible" rule implemented, then for those few cases where end() turned out to be a bad suggestion, the stable order of equal ranges is no longer guaranteed. To reestablish that guarantee, you must code the more expensive loop with a call to upper_bound for each iteration. Or alternatively one could manually code one of the algorithms presented below (essentially passing responsibility for efficient code from the library vendor to the client).

Equal range stability

Once the client is able to fully specify where within an equal_range a new element is inserted, there must be some guarantee that the resulting equal_range is stable throughout the lifetime of the container. LWG issue 371 addresses this concern and provides additional motivation for requiring such stability:

As client code iterates through a multimap or multiset and selectively erases elements, if the ordering of the elements (even within an equal_range) is not stable during this process, then the client could unknowingly avoid iterating over some of the elements in a container. This would break well established idioms:

multimap<int, int> m;
...
multimap<int, int>::iterator i = m.begin();
while (i != m.end())
{
    if (pred(i))
        m.erase (i++);
    else
        ++i;
}

Fortunately binary tree algorithms are designed to preserve in-order order. Node rotations used to rebalance trees (be they AVL, red-black or whatever) do not reorder elements, even if they are equivalent. An implementation would have to go to extra expense, both in terms of code size and in terms of run time computation, in order to change the relative order of elements within an equal_range. Therefore the current status-quo is that all current implementations have the characteristic that equal_range's are stable.

Insert without hint

During the course of writing this paper several people expressed to me the desire to make the "insert without hint" function deterministic with respect to equal_range's. My first impression was "not gonna' happen." Not because it was too expensive, or too difficult, but because it would be too controversial in that it would overly restrict vendor options in implementation.

However after further reflection I have changed my mind.

The well-referenced book "Introduction To Algorithms" by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest describes binary tree options in detail, including the red-black and AVL balancing algorithms. The general (non-balanced) algorithm for inserting into a binary tree is given as:

Tree-Insert(T, z)
   y <- NIL
   x <- root[T]
   while x != NIL
      do y <- x
         if key[z] < key[x]
            then x <- left[x]
            else x <- right[x]
   p[z] <- y
   if y == NIL
      then root[T] <- z
      else if key[z] < key[y]
         then left[y] <- z
         else right[y] <- z

And the balanced-tree algorithms (whether red-black or AVL) start with this unbalanced insert and then proceed to fix up invariants in the tree structure which are broken by the insert. (Disclaimer: red-black is discussed in much more detail than AVL, but I believe the assumption above is valid).

There are two interesting things to notice about this algorithm:

1. When inserting a new value_type, the algorithm always searches to a leaf node (to the bottom of the tree) to insert a node. Nodes are never spliced in mid-way down a tree.
2. If the tree contains an existing equal_range of z, this algorithm always appends to the upper_bound of it.

The first point highlights that to find the point of insertion one must traverse the full height of the tree. Finding an equivalent element mid way down, or even at the root, does not preclude the need to navigate down to the leaves of the tree. So even if an entire tree consists on one very long equal_range, if you're going to insert anywhere into that tree, you must still navigate from the root to the leaves, no matter what your equal_range insertion strategy.

The second point highlights that "insert without hint" and "insert at upper bound" can be the exact same operation, with the exact same cost. Indeed, inspection of the original HP implementation reveals the basic Coren/Leiserson/Rivest algorithm. Glancing at the May 1997 issue of CUJ, article "Implementing Associative Containers" by P. J. Plauger reveals the same heritage. A glance at a recent gcc implementation again confirms this trend. Finally a recent survey of current practice confirms that all current implementations of multi_map always insert at the upper bound of an equal range when using the "insert without hint" member function.

#include <map>
#include <string>
#include <iostream>
#include <utility>

template <class Map>
void
display(const Map& m)
{
    for (typename Map::const_iterator i = m.begin(), e = m.end(); i != e; ++i)
        std::cout << '(' << i->first << ", " << i->second << ") ";
    std::cout << '\n';
}

int main()
{
    typedef std::multimap<int, std::string> Map;
    typedef std::pair<int, std::string> value_type;
    Map m;
    m.insert(value_type(3, "three"));
    m.insert(value_type(3, "threE"));
    m.insert(value_type(3, "thrEe"));
    m.insert(value_type(3, "thrEE"));
    m.insert(value_type(3, "thRee"));
    m.insert(value_type(3, "thReE"));
    m.insert(value_type(3, "thREe"));
    m.insert(value_type(3, "thREE"));
    m.insert(value_type(3, "tHree"));
    m.insert(value_type(3, "tHreE"));
    m.insert(value_type(3, "tHrEe"));
    m.insert(value_type(3, "tHrEE"));
    m.insert(value_type(3, "tHRee"));
    m.insert(value_type(3, "tHReE"));
    m.insert(value_type(3, "tHREe"));
    m.insert(value_type(3, "tHREE"));
    m.insert(value_type(3, "Three"));
    m.insert(value_type(3, "ThreE"));
    m.insert(value_type(3, "ThrEe"));
    m.insert(value_type(3, "ThrEE"));
    m.insert(value_type(3, "ThRee"));
    m.insert(value_type(3, "ThReE"));
    m.insert(value_type(3, "ThREe"));
    m.insert(value_type(3, "ThREE"));
    m.insert(value_type(3, "THree"));
    m.insert(value_type(3, "THreE"));
    m.insert(value_type(3, "THrEe"));
    m.insert(value_type(3, "THrEE"));
    m.insert(value_type(3, "THRee"));
    m.insert(value_type(3, "THReE"));
    m.insert(value_type(3, "THREe"));
    m.insert(value_type(3, "THREE"));
    display(m);
}

The following implementations:

Dinkumware
gcc
Metrowerks CodeWarrior
Rogue Wave
STLport

output:

(3, three) (3, threE) (3, thrEe) (3, thrEE) (3, thRee) (3, thReE) (3, thREe) (3, thREE)
(3, tHree) (3, tHreE) (3, tHrEe) (3, tHrEE) (3, tHRee) (3, tHReE) (3, tHREe) (3, tHREE)
(3, Three) (3, ThreE) (3, ThrEe) (3, ThrEE) (3, ThRee) (3, ThReE) (3, ThREe) (3, ThREE)
(3, THree) (3, THreE) (3, THrEe) (3, THrEE) (3, THRee) (3, THReE) (3, THREe) (3, THREE)

That is, all existing implementations implement "insert without hint" as "insert at upper bound."

Therefore this paper proposes to standardize existing practice to the benefit of clients by guaranteeing that the "insert without hint" functions of the associative containers append to any existing equal_range in the container.

Efficiency Concerns

One understandable reaction to the "as close to the hint as possible" suggestion was a concern that it would cause undue inefficiency either computationally, or in code size. However, this concern turned out to be unwarranted. The suggestion can be simply and efficiently implemented with the following algorithm (on the left) which makes use of the existing lower_bound and upper_bound logic. The existing "ignore hint if wrong" algorithm is presented on the right for comparison. The number of comparisons required to decide if the hint is valid is also listed for each algorithm.

To insert x at p:
   if p == end || x <= *p
      if p == begin || x >= *(p-1)
         insert x before p
      else
         insert x before upper_bound(x)
   else
      insert x before lower_bound(x)

To insert x at p:
   if (p == end   || x <= *p) &&
      (p == begin || x >= *(p-1))
      insert x before p
   else
      insert x without hint

The logic for the two algorithms is very similar, requiring exactly the same tests. The only difference is the use of lower_bound or upper_bound to guide insertion instead of "insert without hint" when x > *p or when x < *(p-1) respectively.

For those implementations wanting to include an after check, the above algorithms can be slightly modified to accommodate. Note that this extra check will only affect complexity, and not the relative order within an equal_range (for the left hand algorithm). Once the after position is in need of checking, the algorithm on the left is going to place x at lower_bound(x), and the only question that remains is whether it will be done with constant or Log(N) complexity.

To insert x at p:
   if p == end || x <= *p
      if p == begin || x >= *(p-1)
         insert x before p
      else
         insert x before upper_bound(x)
   else if p+1 == end || x <= *(p+1)
      insert x after p
   else
      insert x before lower_bound(x)

To insert x at p:
   if p == end || x <= *p
      if p == begin || x >= *(p-1)
         insert x before p
      else
         insert x without hint
   else if p+1 == end || x <= *(p+1)
      insert x after p
   else
      insert x without hint

In either case (with or without the after check), the "insert as close to hint as possible" algorithm is not significantly more complicated nor any less efficient than the "ignore hint if wrong" algorithm (same number of calls to the comparison operator and same complexity in each case).

The differences between the algorithms with and without the "as close as possible to hint" rule are independent of the type of tree. That is, there is nothing red-black specific that is being proposed. The only change in the algorithms is the use of (insert at) lower_bound and upper_bound in place of "insert without hint".

There may still be a concern that "insert without hint" can be cheaper than "insert before upper_bound" or "insert before lower_bound". However the previous section in this paper argues that with respect to all current implementations "insert without hint" and "insert before upper_bound" are exactly the same thing. Furthermore the Coren/Leiserson/Rivest algorithm for inserting (at upper bound) can be trivially modified to insert at the lower bound instead:

Tree-Insert(T, z)
   y <- NIL
   x <- root[T]
   while x != NIL
      do y <- x
         if key[z] <= key[x]
            then x <- left[x]
            else x <- right[x]
   p[z] <- y
   if y == NIL
      then root[T] <- z
      else if key[z] <= key[y]
         then left[y] <- z
         else right[y] <- z

Therefore this paper asserts that there is absolutely no extra computational expense proposed herein.

Note: The "as close as possible to hint" rule has no effect on the algorithms used to insert into containers with unique keys. When x does not yet exist in a container, lower_bound, upper_bound and "insert without hint" all refer to the same location. And when x does already exist in a unique-key container, no insertion is performed.

Prior Art

Metrowerks has implemented this proposal (with the additional after check) since 2001.

Summary

This proposal seeks deterministic and functional behavior which gives clients complete control over the element order within an equal_range of a multiset or multimap, in some cases providing a significant computational savings, and in no case burdening the client with additional expense. Such control may enable clients to use these standard facilities in more situations, and in more efficient ways.

Proposed Wording

23.1.2 - Associative containers

Paragraph 7:

Paragraph 8:

-8- The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements. The relative ordering of elements in the container is stable throughout the lifetime of the container, even within an equal_range, unless explicitly changed by the client with erase and insert.

Acknowledments

Thanks to Andrew Koenig for submitting LWG issue 233 in the first place, and for originally suggesting the "as close to hint as possible" feature. Thanks also to John Potter who showed how the "insert as close to hint as possible" rule is not nearly as complicated or expensive as I had first feared.

Thanks to Alberto Barbati, Jerry Coffin, Beman Dawes, Raoul Gough, Russell Hind, Christopher Jefferson, Bronek Kozicki, Daniel Krügler, Branimir Maksimovic, Guy Middleton, Nicola Musatti, John Potter, Larry I Smith and Maxim Yegorushkin for helping with the survey of current practice.

This paper acknowledges the work of the prior LWG issue 192 which was pretty much right on target, just ahead of its time.