c++标准库

c++包含许多正式标准，分别为 c++98, c++03, c++11(c++0x), c++14(c++1y), c++17(c++1z), c++20(c++2a), 还有正在定制中的 c++23(c++2b).

c++版本规定了 c++ 的语法，语言特性，还规定了内置库的实现规范，即 c++ 标准库（STL）。

STL 包含了一些通用化的数据结构和算法，下面简单介绍。

序列式容器

• vector
• array
• deque
• list
• forward_list

有序关联式容器

• set
• multiset
• map
• multimap

无序关联式容器

• unordered_set
• unordered_multiset
• unordered_map
• unordered_multimap

容器适配器

• stack
• queue
• priority_queue

一些共有的方法

• =: 有赋值运算符即复制构造函数
• begin(): 指向开头元素的迭代器
• end(): 指向末尾的下一个元素的迭代器，不指向元素，但指向末尾元素的后继
• rbegin(): 表示反向，rend 类似
• cbegin(): 表示 const 迭代器，cend 类似
• size(): 容器的元素个数
• max_size(): 理论存储的最大元素个数
• empty(): i是否为空
• swap(): 交换两个容器
• clear(): 清空
• 有序容器支持比较，无序容器不支持比较

迭代器

迭代器

• 可以理解成指向容器的指针，支持自增（iter++）和解引用操（*iter）作
• 那对于无序容器来说，支持自增吗？
• 可以使用 auto 来声明
• 分类
  • input_iter, 仅支持拷贝，自增和解引用
  • output_iter, 仅支持拷贝，自增和解引用
  • forward_iter, 同时满足 input_iter 和 output_iter
  • bidirection_iter, 在 forward_iter 的基础上，支持自减
  • randomaccess_iter, 在 bidirection_iter 的基础上，支持加减运算和比较运算
• 相关函数
  • std::adcance(it, n), 将迭代器向后移动 n 步（若 n 为负数，向前移动，需要迭代器支持减操作）
  • std::next(it), 获取 it 的后继（it 不变）
  • std::next(it, n), 获取 it 的第 n 个后继（需要 it 为双向迭代器）
  • std::prev(it, n), 获取 it 的第 n 个前驱（需要 it 为双向迭代器）

vector

• 构造函数

// 1. 创建空vector; 常数复杂度
vector<int> v0;
// 1+. 这句代码可以使得向vector中插入前3个元素时，保证常数时间复杂度
v0.reserve(3);
// 2. 创建一个初始空间为3的vector，其元素的默认值是0; 线性复杂度
vector<int> v1(3);
// 3. 创建一个初始空间为3的vector，其元素的默认值是2; 线性复杂度
vector<int> v2(3, 2);
// 4. 创建一个初始空间为3的vector，其元素的默认值是1，
// 并且使用v2的空间配置器; 线性复杂度
vector<int> v3(3, 1, v2.get_allocator());
// 5. 创建一个v2的拷贝vector v4， 其内容元素和v2一样; 线性复杂度
vector<int> v4(v2);
// 6. 创建一个v4的拷贝vector v5，其内容是{v4[1], v4[2]}; 线性复杂度
vector<int> v5(v4.begin() + 1, v4.begin() + 3);
// 7. 移动v2到新创建的vector v6，不发生拷贝; 常数复杂度; 需要 C++11
vector<int> v6(std::move(v2));  // 或者 v6 = std::move(v2);

• 访问元素
  • v.at(pos), 如果越界会抛出异常
  • v[pos], 不进行越界检查
  • v.front(), 返回首元素引用
  • v.back(), 返回末尾元素引用
  • v.data(), 返回指向第一个元素的指针
• 其他方法
  • v.empty()
  • v.size()
  • v.resize(), 改变 vector 的大小，多退少补
  • v.max_size()
  • v.reserve(), 是的 vector 预留一部分空间，避免不必要的内存拷贝
  • v.capacity()
  • v.shrink_to_fit(), 使 vector 的容量与长度一致
  • v.clear()
  • v.insert(), 插入元素，可以插入多个
  • v.erase(), 擦除某个迭代器或区间的元素
  • v.push_back()
  • v.pop_back()
  • v.swap()

queue 双端队列

• 构造函数

  // 1. 定义一个int类型的空双端队列 v0
  deque<int> v0;
  // 2. 定义一个int类型的双端队列 v1，并设置初始大小为10; 线性复杂度
  deque<int> v1(10);
  // 3. 定义一个int类型的双端队列 v2，并初始化为10个1; 线性复杂度
  deque<int> v2(10, 1);
  // 4. 复制已有的双端队列 v1; 线性复杂度
  deque<int> v3(v1);
  // 5. 创建一个v2的拷贝deque v4，其内容是v4[0]至v4[2]; 线性复杂度
  deque<int> v4(v2.begin(), v2.begin() + 3);
  // 6. 移动v2到新创建的deque v5，不发生拷贝; 常数复杂度; 需要 C++11
  deque<int> v5(std::move(v2));
  

• 方法
  • q.push_front()
  • q.pop_front()
  • q.push_back()
  • q.pop_back()

list 双向列表

• 方法
  • l.front()
  • l.back()
  • l.splice()
  • l.remove()
  • l.sort()
  • l.unique()
  • l.merge()

forward_list 单向列表

可以降低开销，有些场景比双向列表更合适

set

通常使用红黑树实现，是的搜索，移除和查询都有对数复杂度

• 方法
  • insert(x), 当容器没有等价元素时，插入
  • erase(x), 删除所有值为 x 的元素，返回删除元素个数
  • erase(pos), 删除迭代器为 pos 的元素，要求迭代器合法
  • erase(first, last), 删除迭代器在 first 和 last 之间的元素
  • clear()
  • count(x)
  • find(x), 返回 x 对应的迭代器，否则返回 end()
  • lower_bound(x), 返回首个不小于 x 的迭代器，否则返回 end()
  • upper_bound(x), 返回首个大于 x 的迭代器，否则返回 end()
  • empty()
  • size()
• 遍历
  • 使用 begin 或者 end 迭代器进行遍历
  • 查找到某个元素，然后进行操作

set<int> s;
typedef set<int>::iterator si;
for (si it = s.begin(); it != s.end(); it++) cout << *it << endl;

set<int> s;
for (auto x : s) cout << x << endl;

// 现存可用的元素
set<int> available;
// 需要大于等于的值
int x;

// 查找最小的大于等于x的元素
set<int>::iterator it = available.lower_bound(x);
if (it == available.end()) {
  // 不存在这样的元素，则进行相应操作……
} else {
  // 找到了这样的元素，将其从现存可用元素中移除
  available.erase(it);
  // 进行相应操作……
}

struct cmp {
    bool operator()(int a, int b) { 
        return a > b; 
    }
};
set<int, cmp> s;

map

有序键值对，同时对搜索、移除和删除具有对数复杂度，同时用红黑树实现

map<key,T> mymap

• 方法
  • 直接使用下标进行查询或插入
    • mymap[“c++”] = 1;
  • 使用 insert 插入
    • mymap.insert(pair<string,int>(“python”,2));
  • 删除
    • erase(key)
    • erase(pos), 删除对应迭代器的元素
    • erase(first, last), 删除[first,last)范围的元素
    • clear()
  • count(x)
  • find(x)
  • lower_bound(x)
  • upper_bound(x)
• 遍历

  for (auto itr = m.begin(); itr != m.end(); ++itr) { 
        cout << itr->first << " " << itr->second;
    } 
  

stack

栈，先进后出

• 方法
  • top()
  • push(x)
  • pop()
  • size()
  • empty()

queue

队列，先进先出

• 方法
  • front()
  • push()
  • pop()
  • size()
  • empty()

priority_queue

优先队列

// 包含在 #include<queue> 
auto cmp = [](const std::pair<int, int> &l, const std::pair<int, int> &r) {
    return l.second < r.second;
};
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >,decltype(cmp)>
    pq(cmp);

std::priority_queue<int, std::deque<int>, std::greater<int> > q3;
std::priority_queue<int, std::deque<int>, std::less<int> > q4;

• 方法
  • top(), 访问堆顶元素
  • empty()
  • size()
  • push()
  • pop()