11. Deque vs Vector
In a matching engine, pointer stability and cache locality dominate tail latency. Choosing among std::string, std::vector, and std::deque affects reallocation, contiguity, and invalidation behavior. Analyze these trade-offs in the hot path below.
#include <vector>
#include <deque>
int main(){
std::vector<int> v; v.push_back(1); int* p = v.data();
v.push_back(2); int a = *p;
std::deque<int> d; d.push_back(1); int* q = &d[0];
d.push_front(0); int b = *q;
}
Part 1.
Is reading a and b well-defined, and what values do they hold? Propose minimal changes to make both accesses safe and predictable under latency constraints.
Part 2.
(1) When does vector invalidate pointers, and how can reserve mitigate it?
(2) Are deque elements contiguous? How does that affect bulk copy and SIMD usage?
(3) Compare iterator and reference invalidation for vector vs deque on push/pop.
(4) How does small string optimization affect string::c_str() pointer stability?
(5) reserve vs resize on vector: behavioral differences and latency implications?
Answer
Answer (Part 1)
a is undefined behavior: the second push_back may reallocate, invalidating p. b is well-defined; deque insertions at ends invalidate iterators but typically not references/pointers to existing elements, so *q remains the old value (1). To make both safe: pre-reserve (v.reserve(2)) before taking data() or take p after the final growth; with deque, keep using a pointer/reference to the element but do not rely on contiguity or iterator stability.
Answer (Part 2)
(1) vector invalidates on reallocation or growth beyond capacity; reserve ensures capacity, preserving pointers until further growth.
(2) deque is non-contiguous. This blocks single-span memcpy/SIMD; use vector or gather/scatter strategies instead.
(3) vector growth may invalidate all pointers/references on reallocation. deque end-inserts invalidate iterators but usually keep references/pointers valid.
(4) SSO stores small data inline; c_str() remains valid until mutation. Any write or growth can relocate, invalidating the pointer.
(5) reserve changes capacity only; resize changes size, value-initializing new elements. reserve avoids zeroing costs and reduces reallocations.