SmallVector: insert, emplace, and erase

[jsrivaya]

Parent

Part of #5. Depends on #71, #72, #73.

Summary

Implement mid-sequence mutation operations: insert, emplace, emplace_back, erase, resize, reserve, and shrink_to_fit.

Scope

Insertion

iterator insert(const_iterator pos, const T& value);
iterator insert(const_iterator pos, T&& value);
iterator insert(const_iterator pos, size_t count, const T& value);
template <typename InputIt>
iterator insert(const_iterator pos, InputIt first, InputIt last);

template <typename... Args>
iterator emplace(const_iterator pos, Args&&... args);

template <typename... Args>
T& emplace_back(Args&&... args);  // construct in-place at end

Insert at arbitrary position requires shifting elements right — O(n). If insertion causes growth, heap transition happens first (invalidates all iterators).

Erasure

iterator erase(const_iterator pos);
iterator erase(const_iterator first, const_iterator last);

Shifts elements left — O(n). Returns iterator to element after last erased.

Capacity management

void reserve(size_t new_cap);       // ensure capacity >= new_cap, may heap-transition
void resize(size_t new_size);       // grow (default-init) or shrink (destroy)
void resize(size_t new_size, const T& value); // grow with value
void shrink_to_fit();               // if heap and size <= N, move back to inline

shrink_to_fit is the interesting one: it can transition back from heap to inline if the current size fits in N. This is the reverse of the heap transition and must move-construct elements back into inline storage and free the heap block.

Testing requirements

• Insert at begin, middle, end
• Emplace with multi-arg constructor
• Erase single and range
• reserve beyond N triggers heap transition
• shrink_to_fit moves back to inline when size <= N
• resize growing fills with default-constructed elements