Ch9.4: Iterators, Left-Inclusive Ranges, and Invalidation

Overview

This section explains the left-inclusive range convention used by all fast_io containers, discusses iterator invalidation rules, and explains why you should prefer _index operations when possible.

1. Left-Inclusive Ranges

All fast_io containers use the left-inclusive (also called half-open) range convention: a range is denoted by [first, last), meaning it includes the element pointed to by first but excludes the element pointed to by last.

This convention has several advantages:

begin() to end() covers all elements.
An empty range is simply first == last.
The distance last - first equals the number of elements.


#include <fast_io_dsal/vector.h>
#include <fast_io.h>

int main() {
    ::fast_io::vector<::std::size_t> v{10zu, 20zu, 30zu, 40zu, 50zu};

    // Erase elements in range [begin()+1, begin()+3)
    // This removes elements at positions 1 and 2 (values 20 and 30)
    v.erase(v.begin() + 1, v.begin() + 3);
    // v is now {10zu, 40zu, 50zu}
}

2. Iterator Invalidation

When you modify a container, existing iterators may become invalid (pointing to freed or relocated memory). Understanding which operations invalidate which iterators is critical:

Container	Insertion invalidates	Erasure invalidates
`vector`	All iterators (reallocation may occur)	Iterator to erased element and all after it
`deque`	All iterators (insertion at either end may reallocate the block map)	Iterator to erased element; all iterators if erasing at front or back; only erased iterators if erasing in the middle
`list`	None — existing iterators remain valid	Only the iterator to the erased element
`forward_list`	None — existing iterators remain valid	Only the iterator to the erased element
`array`	N/A — fixed size, no insertion	N/A — fixed size, no erasure

Danger: After a vector::push_back(), every iterator, reference, and pointer into the vector may be invalidated because the vector might have reallocated its storage. Never cache iterators across insertions on a vector.

3. Prefer _index Operations

Because iterators can be invalidated unexpectedly, prefer the index-based operations (insert_index, erase_index, and operator[]) when working with vector and deque. They are bounds-checked and do not suffer from invalidation issues:


// Preferred: index-based
for (::std::size_t i{}; i != v.size(); ++i) {
    if (v[i] == target) {
        v.erase_index(i);
        break;
    }
}

// Dangerous: iterator-based (iterator invalidated by erase)
// for (auto it = v.begin(); it != v.end(); ++it) {
//     if (*it == target) { v.erase(it); break; }  // OK with break
// }

Key takeaways

All containers use left-inclusive [first, last) ranges.
vector and deque invalidate all iterators on insertion.
list and forward_list never invalidate existing iterators on insertion.
Never cache iterators across insertions on contiguous containers.
Prefer _index operations for safety on vector and deque.