2023年11月12日

C++ STL容器：std::vector

std::vector 是 C++ 标准库（STL）中最常用的序列容器之一。它提供了动态大小的数组，支持随机访问，并具有良好的性能特性。在这篇教程中，我们将从基础开始，详细讲解 std::vector 的主要特性、使用方法以及背后的实现原理。

1. std::vector 简介

std::vector 是一个动态数组容器，可以自动调整其大小。它支持快速随机访问、尾部插入和删除操作，并且在内部使用连续的内存来存储数据。这使得 std::vector 的元素可以通过下标快速访问，效率很高。

2. std::vector 的主要特性

  1. 动态大小：std::vector 可以在运行时动态调整其大小。

  2. 随机访问：支持常数时间复杂度的随机访问操作（operator[] 和 at()）。

  3. 自动扩容：当需要插入更多元素时，std::vector 会自动重新分配内存。

  4. 尾部操作：支持高效的尾部插入（push_back()）和删除（pop_back()）。

3. std::vector 的基本用法

以下是 std::vector 的一些基本用法示例：

#include <iostream>#include <vector>int main() {    // 创建一个空的 vector    std::vector<int> vec;    // 向 vector 中添加元素    vec.push_back(1);    vec.push_back(2);    vec.push_back(3);    // 访问元素    std::cout << "First element: " << vec.front() << std::endl;    std::cout << "Last element: " << vec.back() << std::endl;    // 使用索引访问元素    std::cout << "Element at index 1: " << vec[1] << std::endl;    // 遍历 vector    for (size_t i = 0; i < vec.size(); ++i) {        std::cout << "Element at index " << i << ": " << vec[i] << std::endl;    }    // 删除最后一个元素    vec.pop_back();    // 清空 vector    vec.clear();    return 0;}

4. std::vector 的实现原理

std::vector 在内部使用动态数组来存储元素。以下是一个简化的 std::vector 实现示例：

#include <stdexcept>  // 用于异常处理#include <initializer_list>  // 支持列表初始化template <typename T>class vector {private:    T* _data;           // 动态数组指针    size_t _size;       // 当前元素个数    size_t _capacity;   // 分配的内存容量    // 内部函数：用于重新分配内存    void reallocate(size_t new_capacity) {        T* new_data = new T[new_capacity];        for (size_t i = 0; i < _size; ++i) {            new_data[i] = std::move(_data[i]);        }        delete[] _data;        _data = new_data;        _capacity = new_capacity;    }public:    // 构造函数：默认构造    vector() : _data(nullptr), _size(0), _capacity(0) {}    // 构造函数：带容量初始化    explicit vector(size_t capacity) : _data(new T[capacity]), _size(0), _capacity(capacity) {}    // 构造函数：列表初始化    vector(std::initializer_list<T> init_list) : _data(new T[init_list.size()]), _size(init_list.size()), _capacity(init_list.size()) {        size_t index = 0;        for (const T& value : init_list) {            _data[index++] = value;        }    }    // 析构函数    ~vector() {        delete[] _data;    }    // 返回容器中元素个数    size_t size() const {        return _size;    }    // 返回容器的容量    size_t capacity() const {        return _capacity;    }    // 是否为空    bool empty() const {        return _size == 0;    }    // 重载 [] 操作符    T& operator[](size_t index) {        if (index >= _size) {            throw std::out_of_range("Index out of range");        }        return _data[index];    }    const T& operator[](size_t index) const {        if (index >= _size) {            throw std::out_of_range("Index out of range");        }        return _data[index];    }    // 获取首元素    T& front() {        if (empty()) {            throw std::out_of_range("Vector is empty");        }        return _data[0];    }    const T& front() const {        if (empty()) {            throw std::out_of_range("Vector is empty");        }        return _data[0];    }    // 获取尾元素    T& back() {        if (empty()) {            throw std::out_of_range("Vector is empty");        }        return _data[_size - 1];    }    const T& back() const {        if (empty()) {            throw std::out_of_range("Vector is empty");        }        return _data[_size - 1];    }    // 添加元素到末尾    void push_back(const T& value) {        if (_size == _capacity) {            reallocate(_capacity == 0 ? 1 : _capacity * 2);        }        _data[_size++] = value;    }    // 删除末尾元素    void pop_back() {        if (empty()) {            throw std::out_of_range("Vector is empty");        }        --_size;    }    // 改变容量    void reserve(size_t new_capacity) {        if (new_capacity > _capacity) {            reallocate(new_capacity);        }    }    // 迭代器定义    using iterator = T*;    using const_iterator = const T*;    // 返回指向第一个元素的迭代器    iterator begin() {        return _data;    }    const_iterator begin() const {        return _data;    }    // 返回指向末尾的迭代器    iterator end() {        return _data + _size;    }    const_iterator end() const {        return _data + _size;    }    // 清空容器    void clear() {        _size = 0;    }    // 改变容器大小    void resize(size_t new_size, const T& value = T()) {        if (new_size > _capacity) {            reserve(new_size);        }        if (new_size > _size) {            for (size_t i = _size; i < new_size; ++i) {                _data[i] = value;            }        }        _size = new_size;    }};

5. 关键成员函数说明

  • 构造函数和析构函数：初始化和销毁 vector 对象。

  • push_back() 和 pop_back()：分别在 vector 末尾添加和删除元素。

  • reallocate()：当容器需要扩容时重新分配内存。

  • reserve()：调整容器的容量，确保容器可以容纳指定数量的元素。

  • resize()：调整容器的大小，可以填充新的元素。

6. 迭代器和范围基于循环

std::vector 支持范围基于的 for 循环和迭代器，使得遍历容器变得简单：

#include <vector>#include <iostream>int main() {    std::vector<int> vec = {1, 2, 3, 4, 5};    // 使用范围基于的 for 循环遍历 vector    for (const auto& elem : vec) {        std::cout << elem << " ";    }    std::cout << std::endl;    // 使用迭代器遍历 vector    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {        std::cout << *it << " ";    }    std::cout << std::endl;    return 0;}

7. at() 方法

at() 是一个成员函数，提供安全的元素访问。它会对访问的索引进行范围检查，以确保索引有效。如果索引超出范围，它会抛出一个 std::out_of_range 异常。

特点：

  • 范围检查：at() 方法会检查索引是否在有效范围内。如果索引无效，它会抛出异常，防止访问越界。

  • 异常处理：当发生越界时，at() 会抛出 std::out_of_range 异常。这可以帮助调试和避免潜在的程序崩溃。

示例：

#include <vector>#include <iostream>#include <stdexcept>  // std::out_of_rangeint main() {    std::vector<int> vec = {1, 2, 3, 4, 5};    try {        // 使用 at() 访问元素        std::cout << "Element at index 2: " << vec.at(2) << std::endl;                // 尝试访问越界元素        std::cout << "Element at index 10: " << vec.at(10) << std::endl; // 这将抛出异常    } catch (const std::out_of_range& e) {        std::cerr << "Out of range error: " << e.what() << std::endl;    }    return 0;}

8. 总结

通过迭代器和范围基于循环，std::vector 的遍历变得非常方便。

std::vector 是一个动态数组容器，支持随机访问和高效的尾部操作。

它内部使用连续的内存，提供了自动扩容的能力。