序列式容器和关联式容器(associative container)的差别不在"存不存得下",而在元素之间有没有结构关系:
| 序列式容器 | 关联式容器 | |
|---|---|---|
| 逻辑结构 | 线性序列,如 vector、list、deque | 非线性结构,如红黑树、哈希表 |
| 访问依据 | 元素在容器中的存储位置、下标 | 关键字 key |
| 交换两个元素 | 仍是同一个容器 | 存储结构被破坏 |
本章的 set/map 底层是红黑树,也就是一棵平衡二叉搜索树,增删查都是 O(logN);迭代器走的是中序遍历,所以遍历结果按 key 有序。set 是只有 key 的搜索场景,map 是 key/value 场景。
set 的元素本身就是键,所以迭代器只读
template<
class T,
class Compare = std::less<T>,
class Allocator = std::allocator<T>
> class set;第一个参数是元素类型,也是键的类型;第二个参数是比较器,默认 std::less<T>,要求 T 支持小于比较;第三个是空间配置器,一般不用管。set 的构造关注四种:默认构造、迭代器区间构造、拷贝构造、initializer_list 构造。
迭代器是双向迭代器,支持 ++、--、begin/end、rbegin/rend,自然也支持范围 for。它遍历的顺序是按比较器排好的升序,因为底层是二叉搜索树、迭代器走中序。只读这件事在类型里就定死了:set 的 iterator 和 const_iterator 解引用得到的都是 const T&,写 *it = 1; 会直接编译失败(MSVC 的报错是 C3892: "it": 不能给常量赋值)。原因很直接——元素本身就是排序依据,改一个值等于把树改坏。
#include <iostream>
#include <set>
#include <string>
int main()
{
std::set<int> s;
s.insert(5);
s.insert(2);
s.insert(7);
s.insert(5); // 已存在,插入失败
s.insert({2, 8, 3, 9}); // initializer_list 插入,重复的跳过
for (auto e : s)
{
std::cout << e << ' ';
}
std::cout << '\n'; // 2 3 5 7 8 9
std::set<std::string> words = {"sort", "insert", "add"};
for (const auto& w : words)
{
std::cout << w << ' ';
}
std::cout << '\n'; // add insert sort
return 0;
}std::string 的比较是字典序:逐字符按字符编码比,前缀完全相同时短的更小。课件这里写的是"比较 ascll 码大小顺序",把整串当成一个 ASCII 码值来比是不对的,"ab" 和 "b" 的大小只能逐字符定;ascll 这个拼写也应改成 ASCII。
rbegin() 到 rend() 是降序遍历。反向迭代器建立在同一棵树上,它的 ++ 实际调用底层双向迭代器的 --,所以不需要另建一份索引。
判等靠比较器,不靠 operator==
容器判断两个元素"是不是同一个键",用的不是 operator==,而是比较器认为它们既不小于也不大于。这条在自定义比较器时最容易忘:
struct Person
{
std::string name;
int age;
};
struct CmpByAge
{
bool operator()(const Person& a, const Person& b) const
{
return a.age < b.age;
}
};
std::set<Person, CmpByAge> g;
g.insert({"小明", 20});
g.insert({"小美", 20}); // 年龄相同,被当成同一个键,插入失败小美和小明年龄一样,在容器眼里就是同一个 key,第二次插入直接失败。这不是 bug,而是关联式容器的语义。想让同年龄的两个人共存,比较器里必须把真正能区分人的字段也放进去。
自己写比较器要满足严格弱序(strict weak ordering):comp(a, a) 恒为假;comp(a, b) 和 comp(b, a) 不能同时为真;并且可传递。写成 <= 就破坏了第一条,后果不是编译错误,而是插入失败、重复元素、树结构被破坏这类无法定位的现象。
单元素 insert 返回 std::pair<iterator, bool>:first 指向这个值最终所在的结点,second 只在真插入时为 true。一次插入顺手完成存在性判断,省掉一次查找:
auto ret = s.insert(5);
if (!ret.second)
{
std::cout << *ret.first << " 已经在里面\n";
}set 的增删查:接口与半开区间
| 接口 | 作用 |
|---|---|
pair<iterator,bool> insert(const value_type&) | 插入一个值;已存在则失败,second 为 false |
void insert(initializer_list<value_type>) | 插入一串,已存在的跳过 |
void insert(InputIterator first, InputIterator last) | 插入区间,已存在的跳过 |
iterator find(const value_type&) | 找到返回迭代器,否则 end() |
size_type count(const value_type&) | 返回该值的个数,set 里只会是 0 或 1 |
iterator erase(const_iterator pos) | 删一个位置,返回被删元素的下一个 |
size_type erase(const value_type&) | 删这个值,返回删除个数 |
iterator erase(const_iterator first, const_iterator last) | 删一段区间 |
iterator lower_bound(const value_type&) | 第一个 >= val 的位置 |
iterator upper_bound(const value_type&) | 第一个 > val 的位置 |
find 和算法库的 std::find 同名但代价差一个数量级:成员 find 顺着树走,O(logN);std::find 从头线性扫描,O(N)。两者都能编译、结果都对,using namespace std; 之后几乎看不出区别:
auto p1 = std::find(s.begin(), s.end(), 7); // 线性
auto p2 = s.find(7); // 走树只想知道在不在,count 比 find 直白:if (s.count(x)) 完全合法,复杂度一样是 O(logN)。
erase 删几个,取决于给的是值还是迭代器。给 key 时返回删除个数;set 里键唯一,所以看起来像"删一个",实际是同一个重载在唯一键上的表现。给迭代器时 C++11 起返回下一个位置,循环里可以这样写:
for (auto it = s.begin(); it != s.end(); )
{
if (*it % 2 == 0)
{
it = s.erase(it); // 返回下一个,不要写 it++ 后再用
}
else
{
++it;
}
}树容器的失效规则比 vector 温和:删一个结点只影响它自己,其他迭代器、引用、指针仍然有效;被删的那个当然不能再用。迭代器本身是双向的,只能 ++ 和 --,写不出 it + 1,想跳 n 步只能循环。
equal_range(v) 把 lower_bound 和 upper_bound 打包成一对迭代器。在 set/map 里这个区间最多一个元素,在 multiset/multimap 里才是它发光的地方:multimap 没有 [],取一个键的全部值只能靠它。
按值划走一段用 lower_bound 和 upper_bound,它们圈出的是半开区间 [lo, hi):
std::set<int> myset;
for (int i = 1; i < 10; ++i)
{
myset.insert(i * 10);
}
auto itlow = myset.lower_bound(30); // 第一个 >= 30
auto itup = myset.upper_bound(60); // 第一个 > 60
myset.erase(itlow, itup); // 删掉 30 40 50 60
for (auto e : myset)
{
std::cout << e << ' '; // 10 20 70 80 90
}课件在 map 的接口清单里把 lower_bound 声明了两遍,第二遍的注释写的是"返回大于 k 位置的迭代器",那一个应当是 upper_bound。同一份清单里还有一处注释自相矛盾:erase 写成"k 存在返回 0,存在返回 1",前半句应是"不存在返回 0"。
multiset 只多了一件:允许冗余
multiset 与 set 的接口基本一致,区别全来自"同一个值可以出现多次":
find返回中序里第一个该值,因为相等的元素在树里是连在一起的一段;count返回实际个数,不再只有 0/1;erase(key)删掉所有这个值,返回值是个数;insert一定成功,因为不存在"键重复"这回事。
#include <iostream>
#include <set>
int main()
{
std::multiset<int> s = {4, 2, 7, 2, 4, 8, 4, 5, 4, 9};
for (auto e : s)
{
std::cout << e << ' '; // 2 2 4 4 4 4 5 7 8 9
}
std::cout << '\n';
int x = 4;
auto pos = s.find(x);
while (pos != s.end() && *pos == x) // 从第一个 4 往后走
{
std::cout << *pos << ' ';
++pos;
}
std::cout << '\n';
std::cout << s.count(x) << '\n'; // 4
s.erase(x); // 四个 4 全部删掉
for (auto e : s)
{
std::cout << e << ' ';
}
std::cout << '\n'; // 2 2 5 7 8 9
return 0;
}想只删一个,先 find 拿到迭代器再 erase(pos)。
map 的结点里存的是键值对 pair
template<
class Key,
class T,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<const Key, T>>
> class map;成员类型的对应关系值得背下来:key_type 是 Key,mapped_type 是 T,value_type 是 std::pair<const Key, T>。日常说的"value"通常指 T(映射值),但 value_type 指的是结点里真正存的整个 pair。first 是键且带 const,second 是值;迭代器可以改 second,改不了 first。
template<class T1, class T2>
struct pair
{
T1 first;
T2 second;
pair() : first(T1()), second(T2()) {}
pair(const T1& a, const T2& b) : first(a), second(b) {}
template<class U, class V>
pair(const pair<U, V>& p) : first(p.first), second(p.second) {}
};
template<class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y)
{
return pair<T1, T2>(x, y);
}插入一个键值对有四种写法,语义完全相同:
#include <iostream>
#include <map>
#include <string>
int main()
{
std::map<std::string, std::string> dict = {
{"left", "左边"}, {"right", "右边"},
{"insert", "插入"}, {"string", "字符串"}};
std::pair<std::string, std::string> kv("first", "第一个");
dict.insert(kv);
dict.insert(std::pair<std::string, std::string>("second", "第二个"));
dict.insert(std::make_pair("sort", "排序"));
dict.insert({"auto", "自动的"}); // 最省事
dict.insert({"left", "左边,剩余"}); // key 已存在,静默失败
for (const auto& e : dict)
{
std::cout << e.first << ':' << e.second << '\n';
}
return 0;
}insert 永不覆盖已存在 key 的 value。想覆盖只能用 [] 或拿到迭代器改 second。遍历时 it->first 能写,是因为迭代器重载了 operator->,返回的是结点里那个 pair 的指针。
insert 的返回值撑起 operator[]
单元素 insert 的返回类型是 std::pair<iterator, bool>,两种结果都指向这个 key 最终所在的结点:
- key 已存在:
first是这个键的迭代器,second是false; - key 不存在:
first是新结点的迭代器,second是true。
所以插入失败时,insert 顺便当了一次查找。operator[] 要的就是这一点:
T& operator[](const key_type& k)
{
std::pair<iterator, bool> ret = insert({k, T()});
return ret.first->second;
}标准库内部的思路与这四行一致:key 不存在就插入 value_type(k, T()),存在就拿到旧结点,无论如何都返回 second 的引用。于是同一个 [] 同时具备插入、查找、修改三种语义:
std::map<std::string, std::string> d;
d.insert(std::make_pair("sort", "排序"));
std::cout << d.size() << '\n'; // 1
d["insert"]; // key 不存在:插入 {"insert", ""},size 变 2
d["left"] = "左边"; // 不存在:先插空串再赋值
d["left"] = "左边、剩余"; // 存在:纯修改
std::cout << d["left"] << '\n'; // 左边、剩余"读"的语法、"写"的语义,是 operator[] 最容易出事的地方。判断存在性用 find、count 或 C++20 的 contains;读一个"应该存在"的值用 at(),找不到会抛 std::out_of_range,也不会往表里塞东西。只有"没有就建、有就改"的场合,[] 才是最顺手的。
这里有两个 pair 不要混:结点里存的是 std::pair<const Key, T>,也就是 value_type;insert 返回的是 std::pair<iterator, bool>。前者回答"表里存了什么",后者回答"这次插入成没成功"。
map 的迭代器解引用得到 pair<const Key, T>&,写 it->first 时实际发生两次箭头:第一次是迭代器重载的 operator->,返回结点里 pair 的指针;第二次才是结构体指针取成员。所以 it->first 与 (*it).first 等价,遍历顺序只按 key 升序,value 不参与排序。
at() 与 [] 的差别要在只读场景里选对:at 找不到抛 std::out_of_range,不会往表里插;[] 在 const map 上根本不可用,因为它可能修改容器。count 在 map/set 里恒为 0 或 1,用它判断存在性比 find 少写一个 != end()。
map 的接口与 set 对称,插入收整个 value_type、查找和删除只收 key_type:
| 接口 | 作用 |
|---|---|
pair<iterator,bool> insert(const value_type&) | 插入一个键值对;key 已存在则失败 |
void insert(initializer_list<value_type>) | 插入一串 |
void insert(InputIterator first, InputIterator last) | 插入区间 |
iterator find(const key_type& k) | 找到返回迭代器,否则 end() |
size_type count(const key_type& k) const | 该 key 的个数,map 里 0 或 1 |
iterator erase(const_iterator pos) | 删一个位置,返回下一个 |
size_type erase(const key_type& k) | 删该 key,返回删除个数 |
iterator erase(const_iterator first, const_iterator last) | 删区间 |
iterator lower_bound(const key_type& k) | 第一个 >= k |
iterator upper_bound(const key_type& k) | 第一个 > k |
词频统计两种写法,差别就在 [] 省掉的那次查找:
std::map<std::string, int> countMap;
for (const std::string& str : arr)
{
auto ret = countMap.find(str);
if (ret == countMap.end())
{
countMap.insert({str, 1});
}
else
{
ret->second++;
}
}std::map<std::string, int> countMap;
for (const std::string& str : arr)
{
countMap[str]++; // 不存在插 0 再 ++,存在直接 ++
}multimap 与 map 的差异和 multiset 与 set 一样:允许 key 冗余,find 返回中序第一个,erase(key) 删所有同 key 元素。它没有 operator[],也没有 at():一个 key 对应多个 value 时,"返回哪一个"没有答案。它的 insert 也不返回 pair<iterator, bool>,因为 key 重复是允许的,插入不会失败。要拿一个 key 的全部 value,只能用 equal_range。
四道题里 set 和 map 的用法
两个数组的交集(LeetCode 349) 把两个数组塞进 set 去重,再顺序扫描两个有序序列:
class Solution {
public:
std::vector<int> intersection(std::vector<int>& nums1, std::vector<int>& nums2) {
std::set<int> s1(nums1.begin(), nums1.end());
std::set<int> s2(nums2.begin(), nums2.end());
std::vector<int> ret;
auto it1 = s1.begin();
auto it2 = s2.begin();
while (it1 != s1.end() && it2 != s2.end())
{
if (*it1 < *it2)
{
++it1;
}
else if (*it1 > *it2)
{
++it2;
}
else
{
ret.push_back(*it1);
++it1;
++it2;
}
}
return ret;
}
};环形链表 II(LeetCode 142) 不用推"相遇后再走"的证明,边遍历边记录结点地址,第一次插入失败就说明回到了环的入口:
class Solution {
public:
ListNode* detectCycle(ListNode* head) {
std::set<ListNode*> seen;
ListNode* cur = head;
while (cur)
{
auto ret = seen.insert(cur);
if (!ret.second)
{
return cur;
}
cur = cur->next;
}
return nullptr;
}
};set<ListNode*> 存的是指针,比较器默认 std::less<ListNode*> 比的是地址,与结点内容无关。同一个结点第二次出现,就是入口。代价是 O(N) 的额外空间,Floyd 判圈是 O(1);这里换来的是不必理解那个证明。
随机链表的复制(LeetCode 138) 用 map<Node*, Node*> 建立"原结点 → 拷贝结点"的映射,控制 random 时直接查表:
class Solution {
public:
Node* copyRandomList(Node* head) {
std::map<Node*, Node*> nodeMap;
Node* copyHead = nullptr;
Node* copyTail = nullptr;
for (Node* cur = head; cur; cur = cur->next)
{
Node* node = new Node(cur->val);
if (copyTail == nullptr)
{
copyHead = copyTail = node;
}
else
{
copyTail->next = node;
copyTail = node;
}
nodeMap[cur] = node; // 原结点做 key,拷贝结点做 value
}
Node* copy = copyHead;
for (Node* cur = head; cur; cur = cur->next, copy = copy->next)
{
copy->random = cur->random ? nodeMap[cur->random] : nullptr;
}
return copyHead;
}
};比"拷贝结点塞在原结点后面再拆开"省事,因为映射已经替你记下了任意结点对应的副本。
前 K 个高频单词(LeetCode 692) 先统计,再按次数降序;次数相同时要求字典序小的在前。map 的遍历顺序本身按 key 升序,所以次数相同的单词在数组里已经是字典序小的在前。用稳定排序保住这个顺序:
class Solution {
public:
struct Compare
{
bool operator()(const std::pair<std::string, int>& x,
const std::pair<std::string, int>& y) const
{
return x.second > y.second; // 次数大的排前面
}
};
std::vector<std::string> topKFrequent(std::vector<std::string>& words, int k) {
std::map<std::string, int> countMap;
for (const auto& w : words)
{
countMap[w]++;
}
std::vector<std::pair<std::string, int>> v(countMap.begin(), countMap.end());
std::stable_sort(v.begin(), v.end(), Compare());
std::vector<std::string> ret;
for (int i = 0; i < k; ++i)
{
ret.push_back(v[i].first);
}
return ret;
}
};std::sort 底层是快排,不稳定;stable_sort 保证次数相同的元素保持原有相对顺序,也就是 map 给的字典序。不想依赖稳定性,就把比较器写全:
bool operator()(const std::pair<std::string, int>& x,
const std::pair<std::string, int>& y) const
{
return x.second > y.second || (x.second == y.second && x.first < y.first);
}放进 priority_queue 时比较器要反过来写。堆是"比较器为真则 x 的优先级更低",要让次数小的先出堆,就得把"次数更小"判成"更大";次数相同时想让字典序小的先出,就要把字典序大的判成"优先级更低":
bool operator()(const std::pair<std::string, int>& x,
const std::pair<std::string, int>& y) const
{
return x.second < y.second || (x.second == y.second && x.first > y.first);
}std::priority_queue<std::pair<std::string, int>,
std::vector<std::pair<std::string, int>>,
Compare> pq(countMap.begin(), countMap.end());到这里,set 和 map 的接口差异只剩"结点存不存 value"这一条,其余全部由红黑树的同一套查找规则支撑:谁算同一个键交给比较器,谁排前面交给比较器,只有"键不能改"是容器自己拿走的。
还没有评论 — 第一条由你来留。