Mastering std::vector: From Basics to Interview‑Level Implementation

Recently I attended a Pinduoduo C++ interview where the interviewer asked me to hand‑write std::vector, a challenge that tests deep C++ knowledge and problem‑solving skills.

Part1 std::vector Basics

1.1 Definition and Function

std::vector is a template class defined in <vector> that acts as a smart dynamic array container. It automatically adjusts its size at runtime, similar to a magical backpack that grows as items are added.

Implementation uses a contiguous memory block, providing fast element access like an array while managing size dynamically.

1.2 Common Application Scenarios

In data processing, std::vector can store an unknown number of items, e.g., reading integers from a file.

#include <iostream>
#include <vector>
#include <fstream>

int main() {
    std::vector<int> data;
    std::ifstream file("data.txt");
    int num;
    while (file >> num) {
        data.push_back(num);
    }
    return 0;
}

It is also used with algorithms such as std::sort.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9};
    std::sort(numbers.begin(), numbers.end());
    for (int num : numbers) {
        std::cout << num << " ";
    }
    return 0;
}

Part2 Hand‑crafting std::vector

2.1 Key Interface Implementations

(1) push_back checks capacity, doubles it if needed, copies elements to new memory, releases old memory, then inserts the new element.

(2) pop_back simply reduces size by one; memory is not released immediately.

(3) operator[] provides unchecked random access; optional bounds checking can be added in custom implementations.

2.2 Memory Management Mechanism

(1) Dynamic expansion strategy doubles capacity when needed, reducing allocation overhead.

(2) Memory release strategy memory is not shrunk on pop_back; the swap trick can release excess capacity.

#include <iostream>
#include <vector>

void releaseExtraMemory(std::vector<int>& v) {
    std::vector<int>().swap(v);
}
int main() {
    std::vector<int> v;
    for (int i = 0; i < 100; ++i) {
        v.push_back(i);
    }
    releaseExtraMemory(v);
    std::cout << "Capacity after release: " << v.capacity() << std::endl;
    return 0;
}

2.3 Iterator Implementation Points

(1) Iterators act like pointers, allowing traversal of contiguous elements efficiently.

(2) Insertion or deletion may invalidate iterators; obtain the returned iterator after such operations.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3};
    auto it = v.begin();
    v.push_back(4); // may invalidate it
    // reacquire iterator if needed
    return 0;
}

Part3 std::vector Source Code Deep Dive

3.1 Core Data Structures

_Vector_base handles low‑level memory allocation and deallocation.

_Vector_impl_data contains three pointers: _M_start, _M_finish, and _M_end_of_storage, which track the start, current end, and allocated end of the storage.

3.2 Important Member Functions

insert_aux checks capacity, expands if necessary, copies elements, inserts the new element, and updates internal pointers.

erase shifts elements left to fill the gap, moves _M_finish backward, and returns a valid iterator.

Part4 Interview Strategies and Summary

4.1 Interview Intent

Interviewers use “hand‑write std::vector” to assess deep knowledge of the C++ standard library, programming ability, and problem‑solving skills.

4.2 Answering Tips

Explain the overall design first, then detail each interface (push_back, erase, etc.), discuss memory allocation failure handling, iterator invalidation, and possible optimizations such as appropriate growth factors.

4.3 Advice for Future Candidates

Study C++ fundamentals, read books like “C++ Primer” and “Effective C++”, practice on platforms like LeetCode, and review interview experiences to improve.