std::vector 学习笔记

vector 是类模板，其声明如下

template<class T, class Allocator = std::allocator<T>>
class vector;

creator

constructor

默认初始化，构造一个空的容器
构造一个具有 count 个元素的 vector，并使用类型的默认值进行初始化
构造一个具有 count 个元素的 vector，并初始化每个元素为 value
通过 range [first, last) 进行初始化
拷贝构造
移动构造
通过初始化列表进行初始化

#include <iostream>
#include <vector>

int main()
{
    // 默认初始化，构造一个空的容器
    std::vector<int> vec;
    // 构造一个具有 10 个元素的 vector，并使用类型的默认值进行初始化
    std::vector<int> vec1(10);
    // 构造一个具有 10 个元素的 vector，并初始化每个元素为 3
    std::vector<int> vec2(10, 3);
    // 通过 range [first, last) 进行初始化
    std::vector<int> vec3(vec2.begin(), vec2.end());
    // 拷贝构造
    std::vector<int> vec4(vec2);
    // 移动构造
    std::vector<int> vec5(std::move(vec4));
    // 通过初始化列表进行初始化
    std::vector<int> vec6 = {0, 1, 2, 3, 4, 5, 6};
}

operator =

拷贝赋值
移动赋值
初始化列表赋值

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec1 {1, 2, 3, 4, 5};
    std::vector<int> vec2;
    std::vector<int> vec3;
    std::vector<int> vec4;

    // 通过拷贝进行赋值
    vec2 = vec1;
    // 通过移动进行赋值
    vec3 = std::move(vec1);
    // 通过初始化列表进行赋值
    vec4 = {5, 4, 3, 2, 1};
}

assign

将容器中内容替换为 count 个 value
将容器中的内容替换为 range[first, last)
将容器中的内容替换为初始化列表中内容

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec1 {1, 2, 3, 4, 5};
    // 将容器中内容替换为 5 个 6
    vec1.assign(5, 6);
    // 将容器中的内容替换为 range[first, last)
    std::vector<int> vec2 {1, 4, 9, 16, 25};
    vec1.assign(vec2.begin(), vec2.end());
    // 将容器中的内容替换为初始化列表
    vec1.assign({0, 1, 0, 1});
}

元素获取

at

可以通过 at 获取和修改数据，当 at 的索引超出范围时，会抛异常

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec {1, 2, 3, 4, 5};
    
    try
    {
        // 通过 at 进行写
        vec.at(2) = 10;
        // 通过 at 进行读
        std::cout << vec.at(2) << '\n';
        // 当超出范围时，at 会抛异常
        vec.at(6) = 6;
    } catch (const std::out_of_range& e)
    {
        std::cout << e.what() << '\n';
    }
}

operator []

可以通过 [] 获取和修改数据，当 [] 的索引超出范围时，为未定义行为

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec {1, 2, 3, 4, 5};
    // 通过 [] 进行写
    vec[2] = 10;
    // 通过 [] 进行读
    std::cout << vec[2] << '\n';
    // 当越界时，不会抛异常也不会报错，但这是未定义行为，其结果未知
    std::cout << vec[6] << '\n';
}

front

front 可以获取到 vector 的第一个元素，然后可以进行修改。对于一个空的 vector 调用 front 为未定义行为，所以在调用 front 时避免出现该情况崩溃，可以先对 vector 进行判空

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec {1, 2, 3, 4, 5};
    // 通过 front 进行写
    vec.front() = 10;
    // 通过 front 进行读
    std::cout << vec.front() << '\n';

    std::vector<int> vec1;
    if (!vec1.empty())
        std::cout << vec1.front() << '\n';
}

back

back 可以获取到 vector 的最后一个元素，然后可以进行修改。对于一个空的 vector 调用 back 为未定义行为，所以在调用 back 时避免出现该情况崩溃，可以先对 vector 进行判空

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec {1, 2, 3, 4, 5};
    // 通过 back 进行写
    vec.back() = 10;
    // 通过 back 进行读
    std::cout << vec.back() << '\n';

    std::vector<int> vec1;
    if (!vec1.empty())
        std::cout << vec1.back() << '\n';
}

data

data 返回指向用作元素存储的底层数组的指针，对于非空容器，返回的指针等于第一个元素的地址。如果 vector size 为 0，则 data 可能会也可能不会返回空指针。

#include <iostream>
#include <vector>

void print(const int* p, std::size_t size)
{
    for (std::size_t i = 0; i < size; ++i)
    {
        std::cout << p[i] << " ";
    }
    std::cout << '\n';
}

int main()
{
    std::vector<int> vec {1, 2, 3, 4, 5};
    print(vec.data(), vec.size());
}

Iterator

begin
cbegin
end
cend
rbegin
crbegin
rend
crend

begin 指向 vector 的第一个元素，end 指向最后一个元素的下一个元素，cbegin 和 cend 表示 const 类型的迭代器，不允许其指定的元素被修改，rbegin 和 rend 表示反向迭代器

对于反向迭代器（reverse_iterator），可以通过调用 base 获取到其对应的正向迭代器，且满足 &*r == &*(i - 1)，即如果用一个指针表示一个地址，那么地址左边的元素为反向迭代器指向的元素，地址右边为正向迭代器指向的元素

images

#include <iostream>
#include <vector>
#include <assert.h>

int main()
{
    std::vector<int> vec {1, 2, 3, 4, 5};

    std::vector<int>::reverse_iterator r = vec.rbegin();
    std::vector<int>::iterator i = r.base();
    assert(&*r == &*(i - 1));
}

Capacity

empty

empty 检查容器是否为空，当 begin() == end() 时则认为是空

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> vec;
    std::cout << std::boolalpha << vec.empty() << '\n';  // true
    vec.push_back(1);
    std::cout << vec.empty() << '\n';  // false
}

size

size 获取容器中元素的个数，等效于 std::distance(begin(), end())

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec {1, 2, 3, 4};
    std::cout << vec.size() << '\n';  // 4
}

max_size

max_size 获取系统能够存放到容器中的元素最大个数。在 vector 的实现中，内存通常是成倍的申请，也就是每次内存不够用了，就会申请一个新的原来两倍的内存

#include <iostream>
#include <vector>

int main()
{
    // 插入元素时，会动态进行内存申请
    std::vector<int> vec;
    for (int i = 1; i <= 5; ++i)
    {
        vec.push_back(i);
        std::cout << i << " " << vec.capacity() << '\n';
    }
}

capacity

capacity 返回当前 vector 所申请的内存空间

reserve

将 vector 的容量增加到大于或等于指定的值。如果指定值大于当前 capcity()，则分配新的存储空间，否则该函数不执行任何操作。reverse 不会改变 vector 的 size。如果指定值大于 capacity()，则所有迭代器（包括 past-the-end 迭代器）以及对元素的所有引用都将失效。

reserve 会抛异常，当指定值大于 max_size() 时，会抛出 std::length_error，另外可能抛出 std::bad_alloc

正确使用 reserve 可以避免不必要的内存重新申请释放。

#include <iostream>
#include <vector>

int main()
{
    // 对于不保留内存插入时，会动态进行内存申请
    std::vector<int> vec;
    for (int i = 1; i <= 5; ++i)
    {
        vec.push_back(i);
        std::cout << i << " " << vec.size() << " " << vec.capacity() << '\n';
    }

    // 对于保留了内存插入时，当插入元素超过了申请的内存时，才回动态申请内存
    std::cout << "--------\n";
    std::vector<int> vec1;
    vec1.reserve(4);
    for (int i = 1; i <= 5; ++i)
    {
        vec1.push_back(i);
        std::cout << i << " " << vec1.size() << " " << vec1.capacity() << '\n';
    }
}

/* output
1 1 1
2 2 2
3 3 4
4 4 4
5 5 8
--------
1 1 4
2 2 4
3 3 4
4 4 4
5 5 8
*/

shrink_to_fit

shrink_to_fit 删除未使用的空间。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec;
    vec.reserve(8);
    vec.push_back(5);
    std::cout << vec.capacity() << '\n'; // 8
    vec.shrink_to_fit();
    std::cout << vec.capacity() << '\n'; // 1
}

Modifiers

clear

清除容器中的所有元素，当执行 clear 后，容器中 size 变为 0，capacity 保持不变

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec {1, 2, 3};
    std::cout << vec.size() << " " << vec.capacity() << '\n'; // 3 3
    vec.clear();
    std::cout << vec.size() << " " << vec.capacity() << '\n'; // 0 3
}

insert

在指定的 pos 前插入指定值 value，并返回指向插入值的 iterator
在指定的 pos 前插入 count 个指定值 value，并返回指向插入的第一个元素的 iterator
在指定的 pos 前插入 [first, last)，并返回指向插入的第一个元素的 iterator
在指定的 pos 前插入初始化列表，并返回指向插入的第一个元素的 iterator

#include <iostream>
#include <vector>

template <typename T>
void print(const std::vector<T> &v) {
  std::cout << "[";
  char comma[3] = {'\0', ' ', '\0'};
  for (auto item : v)
  {
    std::cout << comma << item;
    comma[0] = ',';
  }
  std::cout << "]\n";
}

int main()
{
    std::vector<int> vec {1, 2, 3};
    print(vec);
    // 在 vec.begin() 前插入 4
    vec.insert(vec.begin(), 4); // 4, 1, 2, 3
    print(vec);
    // 在第 2 个元素前插入 3 个 5
    vec.insert(vec.begin() + 2, 3, 5); // 4, 1, 5, 5, 5, 2, 3
    print(vec);
    // 插入 range[first, last)
    std::vector<int> tmp {6, 7, 8};
    auto iter = vec.insert(vec.begin(), tmp.begin(), tmp.end()); // 6, 7, 8, 4, 1, 5, 5, 5, 2, 3
    print(vec);
    // 插入初始化列表
    vec.insert(iter, {9, 0}); // 9, 0, 6, 7, 8, 4, 1, 5, 5, 5, 2, 3
    print(vec);
}

emplace

在 pos 前插入一个元素，通过传入的参数来初始化元素对象。当指定位置不存在元素时，则直接在该位置的内存原地创建一个对象，当该位置有元素存在时，则先在其他地方创建一个元素，然后 move 到该位置

#include <iostream>
#include <vector>

template <typename T>
void print(const std::vector<T> &v) {
  std::cout << "[";
  char comma[3] = {'\0', ' ', '\0'};
  for (auto item : v)
  {
    std::cout << comma << item;
    comma[0] = ',';
  }
  std::cout << "]\n";
}

struct Animal
{
    Animal(int a, std::string n)
        : age(a), name(std::move(n)){}

    int32_t age;
    std::string name;
};

std::ostream& operator<<(std::ostream& out, const Animal& animal)
{
    out << "(" << animal.age << ", " << animal.name << ")";
    return out;
}

int main()
{
    std::vector<Animal> vec;
    vec.emplace(vec.begin(), 1, "Cat");
    print(vec); // [(1, Cat)]
    auto iter = vec.emplace(vec.begin() + 1, 2, "Dog");
    print(vec); // [(1, Cat), (2, Dog)]
    vec.emplace(iter, 1, "Bird");
    print(vec); // [(1, Cat), (1, Bird), (2, Dog)]
}

erase

删除指定位置 pos 的元素，返回被删除元素的下一个元素位置 iterator
删除指定 range[first, last) 元素，返回最后一个被删除的元素的下一个元素位置 iterator

#include <iostream>
#include <vector>

template <typename T>
void print(const std::vector<T> &v) {
  std::cout << "[";
  char comma[3] = {'\0', ' ', '\0'};
  for (auto item : v)
  {
    std::cout << comma << item;
    comma[0] = ',';
  }
  std::cout << "]\n";
}

int main()
{
    std::vector<int> vec{1, 2, 3, 4, 5, 6, 7, 8, 9};
    auto iter = vec.erase(vec.begin());
    print(vec); // [2, 3, 4, 5, 6, 7, 8, 9]
    std::cout << std::distance(vec.begin(), iter) << " " << *iter << '\n'; // 0 2
    iter = vec.erase(vec.begin() + 2, vec.begin() + 4);
    print(vec); // [2, 3, 6, 7, 8, 9]
    std::cout << std::distance(vec.begin(), iter) << " " << *iter << '\n'; // 2 6
}

push_back

在容器最后通过拷贝或移动的方式添加元素

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec;
    for (size_t i = 0; i < 5; ++i)
    {
        vec.push_back(i);
    }
}

emplace_back

在容器最后通过原地创建元素的方式添加元素，参数为构造元素的参数

#include <iostream>
#include <vector>

struct Animal
{
    Animal(int a, std::string n)
        : age(a), name(std::move(n)) {}

    std::ostream &operator<<(std::ostream &out)
    {
        out << "(" << age << ", " << name << ")";
        return out;
    }

    int32_t age;
    std::string name;
};

std::ostream &operator<<(std::ostream &out, const Animal &animal)
{
    out << "(" << animal.age << ", " << animal.name << ")";
    return out;
}

int main()
{
    std::vector<Animal> vec;
    vec.emplace_back(1, "Cat");
    vec.emplace_back(2, "Dog");
}

pop_back

删除容器中的最后一个元素

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec { 0, 1, 2, 3, 4 };
    vec.pop_back(); // 0, 1, 2, 3
    vec.pop_back(); // 0, 1, 2
}

resize

resize 调整容器大小使得包含 count 个元素，如果当前 size 大于 count，则容器删除多余的元素，如果 size 小于 count，且如果不指定值，则使用类型的默认值，指定值则增加的元素值为该值

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec { 0, 1, 2, 3, 4 };
    vec.resize(8); // 0, 1, 2, 3, 4, 0, 0, 0
    std::cout << vec.size() << " " << vec.capacity() << '\n'; // 8 10
    vec.resize(3); // 0, 1, 2
    std::cout << vec.size() << " " << vec.capacity() << '\n'; // 3 10
    vec.resize(8, 6); // 0, 1, 2, 6, 6, 6, 6, 6
    std::cout << vec.size() << " " << vec.capacity() << '\n'; // 8 10
}

swap

swap 交换两个容器的内容

#include <iostream>
#include <vector>

int main() {
  std::vector<int> vec{0, 1, 2, 3, 4};
  std::vector<int> vec1{5, 6, 7, 8, 9};
  vec.swap(vec1);
  // vec: 5, 6, 7, 8, 9
  // vec1: 0, 1, 2, 3, 4
}

non-member function

std::swap(std::vector)

std::swap 对于 vector 的偏特化实现

#include <iostream>
#include <vector>

int main() {
  std::vector<int> vec{0, 1, 2, 3, 4};
  std::vector<int> vec1{5, 6, 7, 8, 9};
  std::swap(vec, vec1);
  // vec: 5, 6, 7, 8, 9
  // vec1: 0, 1, 2, 3, 4
}

erase(std::vector) && erase_if(std::vector) [c++ 20]

从容器中删除所有与 value 相同的元素，返回删除的元素个数

#include <iostream>
#include <vector>

int main() {
  std::vector<int> vec{0, 1, 2, 3, 4, 5, 4, 3, 2, 1};
  auto count = std::erase(vec, 3); // 0, 1, 2, 4, 5, 4, 2, 1
  std::cout << count << '\n'; // 2

  count = std::erase_if(vec, [](int x){ return x % 2 == 0; }); // 1, 5, 1
  std::cout << count << '\n'; // 5
}