C++STL
, , , , , ,

array、vector、tuple

  • array：更高级一些的“数组”；固定长度，类型必须一致；
  • vector：“向量”；可变长度，类型必须一致；
  • tuple：“元组”；固定长度，类型可以不一致；

array

  • 特点：
    • 支持随机访问，适合线性搜索；
    • 必须是在编译时确定的大小；
    • 不支持扩容；
    • 如果元素的初始化、移动等开销巨大，则会严重影响性能；
    • 值存放在栈上；
1
#include <array>
  • 定义数组时也可以直接初始化；
1
std::array<int, 10> arr_int = {1, 2, 4, 8, 16};
  • 也可以定义二维数组：直接嵌套即可；
1
std::array<std::array<int, 10>, 10> a;
  • std::array重载了[]，所以可以像传统数组一样对数组里的某个元素进行赋值；
1
2
3
4
5
6
arr_int[0] = 2;
a[0][1] = 5;

// 等同于（看下文）
arr_int.at(0) = 2;
(a.at(0)).at(1) = 5;
  • 成员方法：
    • 快速访问：操作符[]
    • 迭代器：除[]外另一种访问元素的方法
      • 只要有迭代器的容器都有（或都应该实现）的方法：返回头迭代器的方法x.begin()，返回尾后迭代器的方法x.end()
        • 为什么叫尾后迭代器：实际上指向的是最后一个元素后面的空位
        • 返回的实际上是std::array<T>::iterator类型，习惯上用auto自动推导类型
      • 迭代器支持的操作：
        • 解引用：*，访问迭代器对应的元素，例如*i
        • 比较：< <= > >= == !=，对迭代器的比较是对位置进行比较
        • 自增自减：++ --，包括前置++i和后置i++
        • 数字加减：+ x，”前移x位“；- x：”后移x位“
        • 数字加减复合赋值：+= -=
        • 迭代器作差：iter_1 - iter_2：得到两个迭代器的距离
          • 距离的数据类型：std::array<T>::difference_type
      • 常量（const）的begin和end：cbegin()是常量形式的begin()，cend()是常量形式的end()
        • 可以使用常量迭代器禁止通过迭代器修改元素
        • 常量迭代器的数据类型：std::array<T>::const_iterator
      • 反转（reversed）的begin()和end()：rbegin()指向尾元素，rend()指向头元素的前一个元素
      • 反转常量（const reversed）的begin和end：crbegin()，crend()
      • 注意：只要对元素（包括长度）进行了修改，迭代器即刻失效；
    • 位于：at()
    • 已有元素个数：size()
    • 容量：max_size()
    • 判空：empty()
    • 头尾元素：front()，back()
    • 与另一个同长度同类型的数组交换元素：xxx.swap(yyy)
    • 访问底层的C式数组：data()
    • 运算符：各种比较，== != < <= > >= <=>

vector

  • 特点：
    • 存储同一种类型的数据；
    • 可动态扩容；
    • 数据存储在堆上
  • 是C++的“默认容器（Default Container）”
    • 能够最好地展现STL中“容器”的特征（体现STL中“容器”的设计思想）；
    • 许多其他STL模板支持甚至使用vector；
1
2
3
#include <vector>

std::vector<int> test{1, 2, 3};
  • 两种初始化：
    • 构造函数（Constructor）初始化，std::vector<int> a(2, 5);
    • 初始化列表（Initializer List）初始化，std::vector<int> a{2, 5};
    • 区别与联系：只会发生在参数个数为2的情况下：
      • 初始化列表：把大括号内的每一个int当作元素，a实际上为(2, 5)
      • 构造函数初始化：由于重载顺序的问题，会匹配到如下的构造函数：2是重复次数，5是要被重复的元素，a实际上是(5, 5)
      • 其他容器也会存在类似的问题，为避免二义性尽量只在元素重复非常多次的情况下使用构造函数初始化
  • 插入和删除：分为两种方式
    • 尾部插入和删除（性能较好）：v.push_back(xxx)和v.pop_back()
    • 任意位置插入和删除（需要移动元素，性能较差）：v.insert(pos, xxx)和v.erase(pos)
      • pos的类型必须是v的迭代器；
      • insert和erase也可以对区间进行操作;
      • insert和erase方法的返回值是新的迭代器；
    • 清空所有元素：v.clear()
      • 注意：删除或清空元素不会回收已分配的空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 假设此时有两个vector
std::vector<int> a{1,2,3};
std::vector<int> b{4,5,6};

// 在指定位置插入
a.insert(a.begin(), 4);

// 在指定位置删除
a.erase(a.begin());

// 提供一个（自己的）迭代器区间，删除这段区间内的元素
a.erase(a.begin(), a.end()-1);

// 提供一个（其他变量的）迭代器区间，将其他变量的某个区间内的元素插入到当前变量中
a.insert(a.begin(), b.begin(), b.end()-1);
  • 安放元素：
    • emplace与insert/push的区别：在进行“初始化一个对象，再进行插入”的操作时，insert/push需要借助中间变量（临时变量），而emplace不需要
    • v.emplace_back(args...)：在最后安放
    • v.emplace(pos, args...)：在指定位置安放
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 假设有一个类
struct A
{
  int Id;
  std::string Name;

  A() = delete;
  A(int input_id, std::string input_name): Id(input_id), Name(input_name) {}
};

// 以这个类为数据类型定义vector
std::vector<A> data;

// push_back：使用了临时变量
data.push_back(A(10, "Test1"));

// emplace_back：不使用临时变量
data.emplace_back(11, "Test2");
  • 空间处理：分为查询、扩展和收缩三种操作
    • v.size()：查询现有元素个数
    • v.capacity()：查询无需扩容时能容纳的最大元素数（一般是2的倍数）
    • v.resize(x, y)：在原vector的最后用y填充，直至v的元素个数为x
    • v.reserve(x)：将v的内存预分配至x个元素大小

( TODO )

评论