当前位置：首页 > news >正文

STL容器——std::vector

news 2026/3/27 3:46:25

std::vector是一个封装动态数组的序列容器，提供连续的内存存储和动态大小调整能力。

核心实现原理

template<typename T, typename Allocator = std::allocator<T>> class vector { private: // 三指针实现（最常见） T* _M_start; // 指向数组起始位置 T* _M_finish; // 指向最后一个元素的下一个位置 T* _M_end_of_storage; // 指向分配内存的末尾 Allocator _M_allocator; // 分配器（通常为空基类优化） public: size_type size() const noexcept { return _M_finish - _M_start; } size_type capacity() const noexcept { return _M_end_of_storage - _M_start; } bool empty() const noexcept { return _M_start == _M_finish; } };

空间占用

// 在 64 位系统上： sizeof(std::vector<int>) = 24 字节 // 3 个指针 × 8 字节 = 24 字节 // 分配器通常通过空基类优化（EBO）不占用空间

vector占用的是堆内存还是栈内存

内存分布

std::vector的内存分为两部分：对象本身（栈内存）和动态数组（堆内存）

void function() { std::vector<int> vec; //vector对象本身在栈上（24字节） vec.push_back(1); // 元素存储在堆上 vec.push_back(2); vec.push_back(3); }

但是当使用new去生成vector对象时，此时vector对象本身和数组元素全在堆上

void bar() { std::vector<int>* v2 = new std::vector<int>{1, 2, 3}; // v2 指针在栈上（8 字节） // vector 对象在堆上（24 字节） // 元素数组在堆上（12 字节） delete v2; }

内存分配时机

std::vector<int> vec; // 此时：_M_start = _M_finish = _M_end_of_storage = nullptr // 堆内存：0 字节 vec.reserve(10); // 此时：分配堆内存：10 × 4 = 40 字节 // size = 0, capacity = 10 vec.push_back(1); // 构造第一个元素，size = 1, capacity = 10

动态扩容机制如何实现

扩容触发条件

当 size == capacity 时，执行 push_back()、insert()等操作会触发扩容。

扩容流程

template<typename T> void vector<T>::_M_realloc_insert(iterator pos, const T& value) { // 1. 计算新容量 const size_type old_size = size(); const size_type new_capacity = _M_compute_new_capacity(old_size); // 2. 分配新内存 T* new_start = _M_allocator.allocate(new_capacity); T* new_finish = new_start; try { // 3. 移动/拷贝原有元素到新内存 new_finish = std::uninitialized_copy( std::make_move_iterator(_M_start), std::make_move_iterator(pos), new_start ); // 4. 构造新元素 _M_allocator.construct(new_finish, value); ++new_finish; // 5. 移动/拷贝剩余元素 new_finish = std::uninitialized_copy( std::make_move_iterator(pos), std::make_move_iterator(_M_finish), new_finish ); // 6. 销毁旧元素 std::destroy(_M_start, _M_finish); // 7. 释放旧内存 _M_allocator.deallocate(_M_start, capacity()); // 8. 更新指针 _M_start = new_start; _M_finish = new_finish; _M_end_of_storage = new_start + new_capacity; } catch (...) { // 异常安全：清理已分配的资源 std::destroy(new_start, new_finish); _M_allocator.deallocate(new_start, new_capacity); throw; } }

扩容因子

| 实现 | 扩容因子 | 优点 | 缺点 | |------|---------|------|------| | **GCC** | 2.0 | 简单高效，位运算优化 | 内存利用率较低 | | **MSVC** | 1.5 | 更好的内存利用率 | 计算稍复杂 |

迭代器失效

vector 的迭代器本质上是指针，当底层内存重新分配或元素位置改变时，迭代器可能失效。

扩容导致失效

扩容时重新分配内存，旧指针不再指向有效内存

std::vector<int> vec = {1, 2, 3, 4, 5}; auto it = vec.begin(); auto end = vec.end(); vec.push_back(6); // 可能触发扩容 // 危险！it 和 end 可能已失效 // *it; // 未定义行为 // for (; it != end; ++it) { } // 未定义行为

插入操作导致失效

如果未扩容：插入点之前的迭代器有效，插入点及之后的迭代器失效；如果扩容：所有迭代器全部失效

std::vector<int> vec = {1, 2, 3, 4, 5}; auto it1 = vec.begin(); auto it2 = vec.begin() + 2; // 指向 3 auto it3 = vec.end(); vec.insert(vec.begin() + 1, 99); // 在位置 1 插入 // 如果未扩容：插入点之前的迭代器有效，插入点及之后的迭代器失效 // 如果扩容：所有迭代器全部失效

删除操作导致的失效

删除点及之后的迭代器全部失效，删除点之前的迭代器有效

std::vector<int> vec = {1, 2, 3, 4, 5}; auto it1 = vec.begin(); auto it2 = vec.begin() + 2; // 指向 3 auto it3 = vec.begin() + 4; // 指向 5 vec.erase(vec.begin() + 2); // 删除位置 2 的元素（3） //删除点及之后的迭代器全部失效，删除点之前的迭代器有效

pop_back()的失效

end()迭代器和指向最后一个元素的迭代器失效

std::vector<int> vec = {1, 2, 3, 4, 5}; auto it = vec.end(); auto last = vec.end() - 1; // 指向最后一个元素 vec.pop_back(); // it 失效（end 位置改变） // last 失效（指向的元素被删除）

clear()的失效

所有迭代器失效

std::vector<int> vec = {1, 2, 3, 4, 5}; auto it = vec.begin(); vec.clear(); // 删除所有元素 // it 失效（所有元素被销毁） // capacity 不变，但所有迭代器失效

resize()的失效

std::vector<int> vec = {1, 2, 3, 4, 5}; auto it = vec.begin(); vec.resize(10); // 扩大 // 如果未扩容：原有迭代器有效 // 如果扩容：所有迭代器失效 vec.resize(3); // 缩小 // 指向被删除元素的迭代器失效 // end() 迭代器失效

emplace_back vs push_back

两者都是vector类的成员函数，用于在vector 的末尾添加元素。它们之间的主要区别在于添加元素的方式：

1、push_back:接受一个已存在的对象作为参数，进行拷贝或移动，将其添加到 vector 的末尾。这会触发一次拷贝或移动构造函数的调用，具体取决于传递的对象是否可移动。

2、emplace_back:接受构造函数的参数，直接在vector 的内存空间中调用该对象的构造函数，避免了额外的拷贝或移动操作。这可以提高效率，特别是在处理复杂对象时。

class Widget { int id; std::string name; public: Widget(int i, std::string n) : id(i), name(std::move(n)) { std::cout << "Constructor\n"; } Widget(const Widget& other) : id(other.id), name(other.name) { std::cout << "Copy constructor\n"; } Widget(Widget&& other) noexcept : id(other.id), name(std::move(other.name)) { std::cout << "Move constructor\n"; } }; std::vector<Widget> vec; // push_back：需要先构造临时对象，再移动 vec.push_back(Widget(1, "Alice")); // 输出：Constructor, Move constructor // 步骤：1. 构造临时对象 2. 移动到 vector // emplace_back：直接在 vector 内存中构造 vec.emplace_back(2, "Bob"); // 输出：Constructor // 步骤：1. 直接在 vector 内构造（完美转发参数）

shrink_to_fit 的内存处理机制

shrink_to_fit() 是一个非绑定请求，用于减少 capacity() 以匹配 size()，释放未使用的内存。

示例：shrink_to_fit 的内存变化

std::vector<int> vec; vec.reserve(1000); // capacity = 1000, size = 0 for (int i = 0; i < 100; ++i) { vec.push_back(i); // size = 100, capacity = 1000 } // 浪费：900 × 4 = 3600 字节 std::cout << "Before shrink_to_fit:\n"; std::cout << "size = " << vec.size() << "\n"; // 100 std::cout << "capacity = " << vec.capacity() << "\n"; // 1000 vec.shrink_to_fit(); std::cout << "After shrink_to_fit:\n"; std::cout << "size = " << vec.size() << "\n"; // 100 std::cout << "capacity = " << vec.capacity() << "\n"; // 100

vector内部迭代器类型

vector 提供多种迭代器类型：

template<typename T, typename Allocator = std::allocator<T>> class vector { public: // 类型定义 using value_type = T; using pointer = T*; using const_pointer = const T*; using reference = T&; using const_reference = const T&; // 迭代器类型 using iterator = T*; // 随机访问迭代器 using const_iterator = const T*; // 常量随机访问迭代器 using reverse_iterator = std::reverse_iterator<iterator>; using const_reverse_iterator = std::reverse_iterator<const_iterator>; using difference_type = std::ptrdiff_t; using size_type = std::size_t; };

具体实现：

template<typename T> class vector { public: // 迭代器就是原始指针 using iterator = T*; using const_iterator = const T*; // 基本迭代器操作 iterator begin() noexcept { return _M_start; // 直接返回指针 } iterator end() noexcept { return _M_finish; // 直接返回指针 } const_iterator begin() const noexcept { return _M_start; } const_iterator end() const noexcept { return _M_finish; } const_iterator cbegin() const noexcept { return _M_start; } const_iterator cend() const noexcept { return _M_finish; } // 反向迭代器 reverse_iterator rbegin() noexcept { return reverse_iterator(end()); } reverse_iterator rend() noexcept { return reverse_iterator(begin()); } };

vector 的迭代器是随机访问迭代器，支持所有迭代器操作

// vector 的迭代器类别 static_assert(std::is_same_v< std::iterator_traits<std::vector<int>::iterator>::iterator_category, std::random_access_iterator_tag >); // 迭代器类别层次： // std::output_iterator_tag // std::input_iterator_tag // std::forward_iterator_tag (单向) // std::bidirectional_iterator_tag (双向) // std::random_access_iterator_tag (随机访问) <- vector // std::contiguous_iterator_tag (C++20: 连续存储) <- vector

与 C 数组的互操作性设计

data()函数

vector 提供 data() 成员函数，返回指向底层数组的指针。

std::vector<int> vec = {1, 2, 3, 4, 5}; int* ptr = vec.data(); // 可以像 C 数组一样访问 for (size_t i = 0; i < vec.size(); ++i) { std::cout << ptr[i] << " "; }

与 C 数组的转换

// C 数组 -> vector int c_array[] = {1, 2, 3, 4, 5}; size_t size = sizeof(c_array) / sizeof(c_array[0]); // 方法 1：使用迭代器 std::vector<int> vec1(std::begin(c_array), std::end(c_array)); // 方法 2：使用指针和大小 std::vector<int> vec2(c_array, c_array + size); // 方法 3：使用 assign std::vector<int> vec3; vec3.assign(c_array, c_array + size); // vector -> C 数组 std::vector<int> vec = {1, 2, 3, 4, 5}; // 方法 1：拷贝到已有数组 int c_array2[5]; std::copy(vec.begin(), vec.end(), c_array2); // 方法 2：使用 memcpy（仅平凡类型） std::memcpy(c_array2, vec.data(), vec.size() * sizeof(int)); // 方法 3：直接使用 vec.data()（无需拷贝） // process_c_array(vec.data(), vec.size());