Stability and insertion with hint in ordered associative containers with equivalent keys

| Home | Libraries | People | FAQ | More

## Stability and insertion with hint in ordered associative containers with equivalent keys

Boost.Intrusive ordered associative containers with equivalent keys offer stability guarantees, following C++ standard library's defect #233 resolution, explained in document Comments on LWG issue 233: Insertion hints in associative containers. This means that:

- A Insert without hint member function always insert at the upper bound of an equal range.
- A Insert with hint member function inserts the new value before the hint if hint's and new node's keys are equivalent.
- Implements Andrew Koenig as close as possible to hint proposal. A new element is always be inserted as close to the hint as possible. So, for example, if there is a subsequence of equivalent values, `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(), new_node);` or `m.insert(m.begin(), new_node);`