Design an Ordered Vector with Move Semantics and Analyze Its Memory Layout

## Interview Prompt Design a C++ ordered-vector container whose public behavior resembles `std::vector` for iteration and `emplace_back`, but which keeps elements sorted. Explain insertion, reallocation, perfect forwarding, exception safety, and move semantics. Then compare array-of-structures and structure-of-arrays layouts for a workload that scans only a subset of fields. ### Constraints & Assumptions - The element type may be move-only and its move operation may throw. - Ordering uses a supplied strict weak ordering comparator. - Contiguous iteration is desirable, so arbitrary insertion can move many elements. - The layout comparison must consider actual access patterns and vectorization. ### Clarifying Questions to Ask - Does `emplace_back` mean append then restore order, or construct directly at the sorted position? - What iterator invalidation guarantees are required? - Which fields are accessed together in the hot loop? ### What a Strong Answer Covers - Binary search for position paired with an honest O(n) shift cost. - Allocator-aware construction, destruction, growth, and strong/basic exception guarantees. - Correct copy deletion or conditional support and efficient move construction/assignment. - Comparator requirements, duplicate handling, and iterator invalidation. - AoS locality for whole records versus SoA locality and SIMD benefits for selected fields. ### Follow-up Questions - When would a tree or flat set be a better abstraction? - How can a throwing move constructor limit the exception guarantee during growth? - What benchmark would decide between AoS and SoA for this workload?