跳转至

STL Container⚓︎

约 1039 个字 97 行代码 预计阅读时间 6 分钟

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

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

容器对象 (conllection objects)：能够存储其他任意数量的对象的对象。

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

  • 使用 STL 的原因：

    • 节省开发时间：有现成的数据结构
    • 代码可读性：适用于更多有意义的东西？
    • 鲁棒性：STL 数据结构自动成长？
    • 可移植的代码
    • 可维护的代码
    • 容易

  • STL 的组成部分：

    • 容器
    • 算法
    • 迭代器 (iterator)

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

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

  • 所有的顺序容器 (sequential containers)：

    • vector
    • deque
    • list
    • forward_list
    • array
    • string

Vectors⚓︎

例子 
#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()：是否为空
      • == != < > <= >=
      • V.swap(v2)：交换
    • 迭代器
      • I.begin()：获取第一个位置
      • I.end()：获取最后一个位置
    • 元素访问
      • V.at(index)
      • V[index]
        • 注意：不能用这种方法修改元素！
      • V.front()：第一项
      • V.back()：最后一项
    • 添加 / 删除 / 查找
      • V.push_back(e)
      • V.pop_back()
      • V.insert(pos, e)
      • V.clear()
      • V.find(first, last, item)

  • 两种使用方法

    • 预分配

      vector<int> v(100);
v[80] = 1;            // okay
v[200] = 1;           // bad

    • 尾增长

      vector<int> v2;
int i;
while (cin >> i)
    v.push_back(i);

Lists⚓︎

与向量类似：

  • 构造函数
  • 能使用比较运算符比较列表

  • 能够访问列表的首尾元素：x.front()、x.back()

  • 能向列表增删项

    x.push_back(item)
x.push_front(item)
x.pop_back()
x.pop_front()
x.erase(pos1, pos2)

  • 列表计数：x.count()

如何选择合适的顺序容器
  • 除非有别的理由，通常使用 vector
  • 如果程序里有很多小的元素，且对空间要求较高的话，不要使用 list 或 forward_list
  • 如果程序要求对元素的随机访问，那么就用 vector 或 deque
  • 如果程序需要在容器中间插入元素，那么使用 list 或 forward_list
  • 如果程序仅需要再首尾两端插入元素，无需在中间插入元素，那么就用 deque

Maps⚓︎

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

map<string, float> price;
price["snapple"] = 0.75;
price["coke"] = 0.50;
string item;
double total=0;
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';

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);
}

    • 优点：

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

Typedef⚓︎

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

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

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

评论区

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