跳转至

STL Containers⚓︎

约 1416 个字 96 行代码 预计阅读时间 8 分钟

Introduction⚓︎

C++ 的一大重要概念是容器对象(conllection objects)，它是能够存储其他任意数量对象的对象。

容器对象来自 STL（Standard Template Library，标准模板库），它是 ISO 标准下的 C++ 库的一部分，包含了各种数据结构和算法。

  • 使用 STL 的原因：

    • 节省开发时间：有现成的数据结构
    • 代码可读性更强，STL 好比大家都知道的 C++ “黑话”
    • 鲁棒性
    • 可移植的代码
    • 可维护的代码
    • 容易使用

  • STL 的组成部分：容器 (containers)、算法 (algorithms)、迭代器 (iterator)

  • STL 中最常用的三个数据结构：

    • map（映射）：支持任意键值类型
    • vector（向量）：类似 C 数组，但是可以自动扩展
    • list（列表）：双向链表

  • STL 中的顺序容器 (sequential containers)：

    • vector
    • deque(dual-end queue, /dek/)：双端队列
    • list
    • forward_list：前向列表（不介绍）
    • array
    • string

C++ 标准库 (standard library) 包括：

  • Pair 类：万物皆可配对，比如 int/int，int/char 等等
  • 容器 (container)
    • 向量：可扩展数组
    • 双端队列 (deque)：两端均可扩展的数组
    • 列表 (lists)：双向链表
    • 集合 (sets) 和映射 (maps)
  • 基本算法：排序、搜索等等
  • 在库内的所有标识符 (identifier) 都在 std 名称空间内

Vectors⚓︎

vector<type>：变长数组，每个元素的类型为 type。

例子 
#include <iostream>
#include <vector>

using namespace std;

int main() {
    // Declare a vector of ints (no need to worry about size)
    vector<int> x;

    // Add elements
    for (int a = 0; a < 1000; a++)
        x.push_back(a);

    // Have a pre-defined iterator for vector class, can use it to print out the items in vector
    vector<int>::iterator p;
    for (p = x.begin(); p < x.end(); p++)
        cout << *p << " ";

    return 0;
}
  • vector 是一种泛型类(generic class)。这种类需要指定两种类型，其中一个是容器自身的类型（这里是 vector），另一个是容器内元素的类型（上例中就是 int）
  • vector 的内部空间可按需扩大：当有更多项被放入时，它就会为这些项提供足够的空间
  • vector 会记录当前保存的项数，可以用 size 方法读取
  • vector 内部项的顺序即为项的插入顺序，因此可按相同的顺序检索

  • 基本的运算：

    • 构造函数 (constructors)：
      • vector<Elem> c;
      • vector<Elem> c1(c2);
    • 获取大小：
      • V.size()：当前容器内项数
      • V.empty()：是否为空，相比 .size() 速度更快
      • V.capacity()：在当前分配的存储空间内最多可以存放的项数
    • 迭代器：
      • I.begin()：获取第一个位置
      • I.end()：获取最后一个位置
    • 元素访问：
      • V.at(index)
        • 该方法会进行边界检查，如果越界，编译器会抛出异常，更加安全
      • V[index]
        • 注意：不能用这种方法修改元素！
        • 该方法不会做边界检查，如果越界的话，则行为不可预测，是未定义的行为 (undefined behaviour)，因此速度快，但不安全
      • V.front()：第一项
      • V.back()：最后一项
    • 添加 / 删除 / 查找：
      • V.push_back(e)
      • V.pop_back()
      • V.insert(pos, e)，其中 pos 是迭代器变量
      • V.clear()：清空向量内所有元素
      • find(first, last, item)，其中 first、last 是迭代器变量，返回的是位于 first 和 last 之间的迭代器，如果没有找到的话则返回 last
    • 其他：
      • 支持比较运算符 == != < > <= >=
      • V.swap(v2)：交换

  • 两种使用方法

    • 预分配

      vector<int> v(100);   // capacity(not size) = 100
v[80] = 1;            // okay
v[200] = 1;           // bad(can't be out of the boundry)

    • 尾增长

      vector<int> v2;
int i;
while (cin >> i)
    v.push_back(i);   // this vector can grow automatically

更多内容：std::vector

Lists⚓︎

list<type>：本质上是一个双向链表，每个元素的类型为 type。

forward_list<type> 表示的是一个单向链表。

与向量类似：

  • 构造函数
  • 能使用比较运算符比较列表
  • 能够访问列表的首尾元素：x.front()、x.back()

列表相关的方法：

x.push_back(item)
x.push_front(item)
x.pop_back()
x.pop_front()
x.erase(pos1, pos2)
x.count()
x.reverse(size)
x.resize()

列表元素大小不确定，因此：

  • 使用迭代器对列表遍历时，只能使用 == 或 != 比较运算符
  • C++ 无法为列表预留空间，所以列表没有 capacity() 方法

选择合适的顺序容器

  • 除非有别的理由，通常使用 vector
    • vector 的排序速度很快
  • 如果程序里有很多小的元素，且对空间要求较高的话，不要使用 list 或 forward_list
  • 如果程序要求对元素的随机访问，那么就用 vector 或 deque
    • vector 是动态分配的数组，而 deque 是一块块连接起来的 (linked-blocks) 数组，因此后者的访问时间更长
  • 如果程序需要在容器中间插入元素，那么使用 list 或 forward_list
  • 如果程序仅需要再首尾两端插入元素，无需在中间插入元素，那么就用 deque

更多内容：std::list

price; price["snapple"] = 0.75; price["coke"] = 0.50; string item; double total=0;

Maps⚓︎

  • 映射(maps) 是一种关联容器，用于存储由键(keys) 及其映射值构成的元素，以特定顺序排列
  • 键常用于排序或识别唯一的元素，映射值存储对应键的内容
  • 可用 [] 运算符，通过键来访问映射值
    • 注意：如果访问不存在的键，就会创建一个新的键
  • 映射像二叉搜索树那样实现
例子 
#include <map>
#include <string>

map<string, float> 
while (cin >> item)
    total += price[item];

map<long, int> root;
root[4] = 2;
root[1000000] = 1000;
long l;
cin >> l;
// .count(key) 方法用于检查是否存在键 key
if (root.count(l))
    cout << root[l]
else 
    cout << "Not perfect square";

// Create a map of three (string, int) pairs
std::map<std::string, int> m{{"CPU", 10}, {"GPU", 15}, {"RAM", 20}};

print_map("1) Initial map: ", m);

m["CPU"] = 25; // update an existing value
m["SSD"] = 30; // insert a new value
print_map("2) Updated map: ", m);

// Using operator[] with non-existent key always performs an insert
std::cout << "3) m[UPS] = " << m["UPS"] << '\n';
print_map("4) Updated map: ", m);

m.erase("GPU");
print_map("5) After erase: ", m);

m.clear();
std::cout << std::boolalpha << "6) Map is empty: " << m.empty() << '\n';

更多内容：std::map

Iterators⚓︎

  • 声明：list<int>::iterator li;

  • 获取容器首部：

    list<int> L;
li = L.begin();

  • 获取容器尾部：li = L.end();

  • 递增（使用 ++ 运算符）
  • 解引用 (dereference)：*li = 10;
  • 可作为函数参数

  • for-each 循环：迭代数组，向量或其他数据集中的元素，将当前元素值赋给在循环内部声明的迭代器变量

    for(type variable_name : array/bector_name) {
    loop statements
    ...
}
    例子 
    #include<iostream>
using namespace std;
int main() {
    int arr[] = {1,2,3,4,5};        // array initialization
    cout<<"The elements are: ";

    for(int i : arr) {
        cout << i << " ";
    }

    return 0;
}

    • 映射的迭代：获取键值对

      map<string, string> entries;
for (auto& entry : entries) {
    dates.push_back(entry.first + ":" + entry.second);
}

    • 优点：

      • 消除可能的错误，使代码更加可读
      • 容易实现
      • 无需预先初始化迭代器
    • 缺点：
      • 不能直接访问元素索引
      • 不能逆序遍历元素
      • 遍历时不允许跳过其中的某些元素

更多内容：std::iterator

Typedef⚓︎

有些类型名过于冗长，为编写代码带来了不便。此时可用 typedef 为类型名重新命名，以简化名称。

例子 
map<string, list<string>> phonebook;
map<string, list<string>>::iterator finger;

typedef map<string,list<string>> PB;
PB phonebook;
PB::iterator finger;

更多内容：typedef specifier

评论区

如果大家有什么问题或想法，欢迎在下方留言~