Scary Iterators

| Home | Libraries | People | FAQ | More

## Scary Iterators

The paper N2913, titled SCARY Iterator Assignment and Initialization, proposed a requirement that a standard container's iterator types have no dependency on any type argument apart from the container's `value_type`, `difference_type`, `pointer type`, and `const_pointer` type. In particular, according to the proposal, the types of a standard container's iterators should not depend on the container's `key_compare`, `hasher`, `key_equal`, or `allocator` types.

That paper demonstrated that SCARY operations were crucial to the performant implementation of common design patterns using STL components. It showed that implementations that support SCARY operations reduce object code bloat by eliminating redundant specializations of iterator and algorithm templates.

Boost.Intrusive containers are a bit different from standard containers. In particular, they have no allocator parameter and they can be configured with additional options not present in STL-like containers. Thus Boost.Intrusive offers its own `SCARY iterator` implementation, where iterator types don't change when the container is configured with an option that does not alter the value <-> node transformation. More concretely, the following options and conditions guarantee that iterator types are unchanged:

- All containers: `size_type<>`, `constant_time_size<>`,
- `slist`: `cache_last<>`, `linear<>`,
- `unordered_[multi]set`: `hash<>`, `equal<>`, `power_2_buckets<>`, `cache_begin<>`.
- All tree-like containers (`[multi]set`, `avl_[multi]set`, `sg_[multi]set`, `bs_[multi]set`, `splay_[multi]set`, `treap_[multi]set`): `compare<>`.
- `treap_[multi]set`: `priority<>`
- `bs_[multi]set`, `sg_[multi]set`, `treap_[multi]set`, `splay_[multi]set`: They share the same iterator type when configured with the same options.