Paresta's Blog

初始化#

• c(c1)拷贝c1
• c(n, t)加入n个值为t的元素
• c(b, e)加入迭代器b到e的元素的拷贝
• c{a, b, c, ...}用初始化列表赋值
• c.assign()可按初始化方式为容器赋值. 以初始化列表赋值使用c.assign({1,2,...})

关系运算符#

当且仅当容器类型相同时可比较

逐个对应位置元素比较, 相同时比较下一个, 直到不同时元素较小者容器较小

c1 == c2, 当且仅当c1.size() == c2.size()且所有对应位置元素相等

插入#

c.insert(it, ...)接收迭代器, 插入到迭代器对应的位置之前, 返回第一个插入的元素位置的迭代器

可选c.insert(it, val), c.insert(it, n, val), c.insert(it, first, last), c.insert(it, {1, 2, ...})

末尾插入多个值时使用c.insert(c.end(), ...)

c.emplace(args)用参数构造并插入元素

c.push_back() c.push_front()部分容器支持

swap(a, b)交换容器内容

iter_swap(it1, it2)交换两个迭代器指向的元素

访问#

访问元素前先检查c.empty()

任意访问得到元素的引用

c.at(index)在下标越界时抛出异常, 从而确保下标合法

c.front() c.back()部分容器支持

不改变元素时使用cbegin(),cend(), 为底层const

删除#

c.erase()接收迭代器, 返回指向删除的最后一个元素的下一个位置的迭代器

c.clear()清空容器, 返回void

c.pop_back() c.pop_front()部分容器支持

增删vector,string,deque的元素会导致迭代器/引用/指针失效

string特殊操作#

• string s(s2, pos, len)用字符串的一部分构造另一个字符串, len可选
• s.substr(pos, len) 得到子串, len可选
• 字符串的insert() erase()可接收下标作为pos, insert(pos, s2)可插入s2字符串
• s.append(args)在末尾插入
• s.replace(pos, len, args) 替换字符. pos为下标, len为删除的长度
• s.replace(first, last, args) 迭代器版本
• s.find(s1, pos)查找子串或字符, pos可选. 查找不到返回string::npos
• s.rfind(s1, pos)从右侧查找, pos以左
• s.find_first_of(args) s.find_last_of(args) s.find_first_not_of(args)查找args中的 (或不在args中的) 任意字符第一次 (或最后一次) 出现的位置
• s.compare(s1)比较字符串, 等于时返回0, 大于时返回正数, 小于时返回负数
• to_string() stoi()等用于转换

vector.reserve(n)预先分配n大小的空间

priority_queue#

优先队列, 即堆

内置类型默认为最大堆priority_queue<int> max_pq;

内置类型最小堆:

1
#include <vector>
2
#include <functional>
3
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq; // 必须指定实现容器

自定义比较器:

1
struct Compare {
2
    bool operator()(type a, type b) const {
3
        return a < b; // 返回true表示交换a, b顺序(a在b后, 与comp恰好相反)
4
    }
5
}
6
priority_queue<int, vector<int>, Compare> pq;

重载类<运算符:

1
struct Type {
2
    std::string name;
3
    int priority;
4

5
    bool operator<(const Type& other) const {
6
    return priority < other.priority; // 写法与自定义比较器相同
7
    }
8
};

只读#

find(first, last, val)查找val对应元素, 返回指向元素位置的迭代器, 若不存在则返回last

find_if(first, last, pred) 查找第一个使pred为true的元素, 返回指向其迭代器, 若不存在则返回last

find_if_not(first, last, pred)

accumulate(first, last, init)在<numeric>中. 对序列元素求和, 累加到init值上. 使用init类型定义的+运算, 返回值为init类型. 序列元素的类型必须匹配或能转换为init类型

equal(first1, last1, first2)用==判断两个序列是否相等, 返回bool. 元素类型无需相同

更改#

fill(first, last, val)将范围中的每个元素设置为val

fill_n(it, n, val)将从*it开始的n个元素设置为val, 不检查越界问题

copy(first1, last1, first2)将序列1复制到序列2 (清空原序列2), 返回序列2指向最后一个复制的元素的下一个位置的迭代器. 序列2必须至少已经有last1 - first1个元素

• 可使用back_inserter

replace(first, last, old, new) 将序列中old元素替换为new

replace_copy(first, last, res_first, old, new) 替换后传入res (清空原res), res必须至少已经有last - first个元素

for_each(first, last, fn)对范围内的所有元素调用fn. 如需修改元素, 应传入引用值, 返回值无效

transform(first, last, first2, fn)对范围内的所有元素调用fn并将返回值放入另一个位置, 即通过return修改值. first == first2时, 相当于改变原容器

重排#

sort(first, last, comp) 按comp函数排序, 默认升序

• bool comp(type a, type b) 返回true时不交换a, b顺序(a在b前), 否则交换
• comp需满足严格弱序, 即反自反性, 反对称性, 传递性
• comp默认使用<functional>中定义的less<T>
  • 可以传入greater<T>表示降序
  • 依赖于T定义的<运算符

stable_sort(first, last, comp)排序时保持相等元素的原有顺序

reverse(first, last)反转容器

remove(first, last, val)将所有值等于val的元素移动到末尾, 返回指向第一个val元素的迭代器

• 之后调用c.erase(it, end)删除

(C++20)erase(c, val)直接删除容器中所有值等于val的元素

unique(first, last) 将连续的重复元素保留一个, 其余放到末尾冗余区域. 返回指向第一个冗余元素的迭代器

• 之后调用c.erase(it, end)删除重复元素
• 如需全局去重, 需先排序

partition(first, last, pred) 将序列分组, 使pred为true的元素排在第一部分, 否则排在第二部分. 返回指向第二部分第一元素的迭代器

stable_partition(first, last, pred) 相同分组的元素保持原有顺序

链表算法#

用于list和forward_list

• l.merge(l2)对有序链表归并, 升序. 无返回值, l为归并后结果
• l.merge(l2, comp)自定义排序归并
• l.remove(val) l.remove_if(pred)直接移除, 不需要erase()
• l.reverse()翻转
• l.sort() l.sort(comp)
• l.unique() l.unique(pred)直接去重, 不需要erase()
• l.splice(it, l2)将l2中所有元素移动到it指向位置之前, 并从l2中删除
  • l.splice(it, l2, it2)将it2指向的元素移动到it之前
  • 另有fl.splice_after()用于forward_list

种类#

• back_inserter: 使用push_back()
• front_inserter: 使用push_front(), 因此插入序列反转
• inserter: 使用insert(), inserter(c, it)第二个参数传入一个迭代器, 插入到该迭代器之前, 因此插入序列顺序不变

常用于存入新容器的操作 (copy(), transform())

使用方法: back_insertor(c)返回c的迭代器

• iostream迭代器

  • istream_iterator<T> in(is): 从is中读取类型为T的值. 不填(is)时返回EOF

    • *in, ++in可以正常使用

    • 输入时使用while(is != eof)

    • 1
      istream_iterator<int> in(cin), eof;
      2
      vector<int> vec(in, eof);

      直接从cin输入构造vector, 或直接用于泛型算法

  • ostream_iterator<T> out(os, d): 将类型为T的值输出到os中, d为C风格字符串(字面常量或字符数组), 每次输出后打印d

    • out = k时输出
    • *out, ++out返回out
    • for (auto e : vec) out = e;输出容器
    • copy(vec.begin(), vec.end(), out)也可打印

• 反向迭代器: c.rbegin(), c.rend()

  • 依然用++表示正向 (向前)
  • it.base()返回正向迭代器, 指向it的右一个位置
    • 以保证[rbegin(), it)与[it.base(), end())指向相同范围 (反向)
  • sort(c.rbegin(), c.rend())可以直接递减排列
  • find()等查找类算法可以从右查找
    • 返回的迭代器依然是反向迭代器, 通过base()转换
  • 拷贝类算法可以拟序输出

迭代器分类:

操作#

• std.move(it, n)定义在<iterator>中, 返回将迭代器递增指定步数的新迭代器, 不修改原迭代器
• std.prev(it, n)定义在<iterator>中, 递减指定步数, 用于双向迭代器

关键字#

关键字不可更改

有序容器关键字的类型需可<比较, 比较函数满足严格弱序

1. 定义<方法
2. 传入自定义方法, 初始化方式为: map<type1, type2, decltype(func)*> myMap(func);其中func为自定义比较函数

无序容器关键字的类型需可哈希和可==比较

1. ==重载方式相同
2. 传入哈希函数, 初始化方式为:

1
size_t hasher(const type2& elem) {
2
    return hash<int>()(elem.id()); // 内置的hash函数
3
}
4
unordered_map<type1, type2, decltype(hasher)*> myMap(hasher); // 假设在类中已重载==. 也可以同时传入自定义==函数

<pair>#

定义在<utility>中

初始化: pair<T1, T2> p{v1, v2}

访问: p.first, p.second

(C++17) 结构化绑定auto [fst, snd] = pair赋值fst, snd

当first和second分别相等时, p1 == p2

在函数中返回时, 可使用return {v1, v2}

关键字/值类型#

• key_type 关键字类型
• mapped_type map中值类型
• value_type
  • 对于set, 与key_type相同
  • 对于map, 为pair<const key_type, mapped_type>

初始化#

set s{1, 2, 3}, map m{{1, 2}, {3, 4}, {5, 6}}

set(c.begin(), c.end())

非multi容器中重复关键字的元素会自动舍去

map不能自动推断泛型类型

插入#

• c.insert(value) 添加单一元素
  • 为非multi类型时, 只有关键字不存在时才会插入. 返回一个pair, first为指向插入元素或已存在元素的迭代器, second为指示插入是否成功的bool值.
  • 为multi类型时总会插入成功, 返回指向新元素的迭代器
• c.emplace(args)
• c.insert(first, last)迭代器插入, 返回void
• c.insert(init_list)返回void
• c.insert(pos, value) pos指示从何处开始搜索新元素应该存储的位置, 返回一个迭代器
• c[k] = val 在map中, 对k进行值初始化, 并将val赋值
  • 只写c[k]时, 只进行值初始化

有序容器按比较函数升序存储

multi类型中相同关键字元素连续存储

访问#

c[key]

• 只有非multi字典可用
• 若关键字为key元素存在, 返回对应值; 若不存在, 添加该关键字元素, 进行值初始化, 返回值
• 返回为左值, 可以直接进行写入(如++my_map[1])
• const类型和const函数内map不能使用[], 需用at()

c.at(key)若不含key元素, 抛出异常

c.find(key)查找对应关键字的元素, 返回迭代器. 若不存在, 返回c.end()

c.count(key)返回对应关键字的元素数量

• 用于查询元素是否存在时, if(c.count(key))比if(c.find(key) != c.end())更快

(C++20) set.contains(key)查找set中元素是否存在

迭代器指向value_type. set的迭代器始终只读, map的迭代器不可修改first值

(C++17) for (auto& [fst, snd] : map)结构化绑定遍历

c.equal_range(key)在multi容器中, 返回一个迭代器的pair, 指向关键字等于key的元素的范围. 若key不存在, 均指向c.end()

在multimap中查找同一关键字的所有元素:

1
for (auto [it, end] = m.equal_range(key); it != end; ++it)
2
  cout << it->second << endl;

删除#

c.erase(key)删除所有关键字为key的元素, 返回size_type大小为删除元素数量

c.erase(it)与c.erase(first, last)返回指向最后一个删除的元素的下一个位置的迭代器