『 C++ 入门到放弃 』- set 和 map 容器

一、set

1.1 set 容器介绍

set 属于关联容器 ( Associative Container )，其按照某种排序方式排序且存储的元素是唯一的

默认情况下 set 按照 key 进行升序排序，可以借由仿函数来变更其排序的方式

set 的底层实现是二叉搜索树，因此 set 不提供更改数据的接口，避免更新破坏二叉搜索树的特性

// Example
int main()
{set<int> s; // 空setset<int> s2 = {6, 4, 2, 8, 3, 1}; // 以一至多个数据进行初始化for (auto &e : s2){cout << e << " ";}cout << endl;return 0;
}

1.2 set 接口介绍

1.2.1 插入

插入的接口有：insert()和 emplace()

• insert : 插入已经构造好的对象 ( 可以简单理解为不会在插入的时候原地构造对象 )

  ( 对隐式类型来说，是先建构出一份对象的临时拷贝再插入)

• emplace : 直接在容器内部原地构建对象

int main()
{set<pair<char, int>> ms;ms.emplace('a', 24); // emplace 直接调用 pair 的构造函数然后插入 set// ms.insert('b', 25); // 报错，因为 insert 只能接收一个参数ms.insert(make_pair('b', 25)); // 先构建出对象，再插入 setfor (auto it = ms.begin(); it != ms.end(); ++it)cout << " " << (*it).first << " "<< (*it).second << endl;// Output : a 24 b 25return 0;
}

1.2.2 访问

set 的访问可以由迭代器来实现

int main()
{set<int> s1 = {3, 5, 4, 2, 7};auto it = s1.begin();while (it != s1.end()){cout << *it << " ";it++;}return 0;
}

1.2.3 查找

int main() {set<int> s = {1, 4, 2, 3, 5};auto it = s.find(3); // 查找 3/*如果找到，则返回指向该元素的迭代器。如果未找到，则返回std::set::end()*/auto it2 = s.count(4); // count 和 find 的差别在于， count 返回的是要查找的数据数据的个数if (it != s.end()) cout << *it;else cout << "Element not Found!";return 0;
}

1.2.4 删除

int main() {set<int> s = {1, 4, 2, 3, 5};s.erase(5);s.erase(s.begin()); // 用迭代器删除/*返回从 set 容器中删除的元素数量。对于 set ，该值始终为 1 或 0*/for (auto x: s) cout << x << " ";return 0;
}

1.2.5 其他接口

1. lower_bound() : 找到 set 中等于或大于给定值的第一个元素
2. upper_bound() : 找到 set 中第一个大于给定值的元素

int main()
{set<int> s = {5, 4, 3, 8, 6, 0, 7, 1};auto lower = s.lower_bound(3);auto upper = s.upper_bound(7);s.erase(lower, upper); // s.erase(3,8); 左闭右开 所以是删除 3~7for (auto &e : s){cout << e << " "; // 0 1 8}cout << endl;return 0;
}

1.2.6 时间复杂度

操作	时间复杂度
插入	O(log n)
删除	O(log n)
查找最大的数据	O(1)
查找最小的数据	O(1)
查找某个数据	O(log n)
遍历 set	O(n)

二、map

2.1 map 容器介绍

map 也属于关联容器，其与 set 的区别在于 map 是以 <key,value> 的形式存储

默认排序是根据 key进行升序且 key 的值不允许重复

map 的底层是使用红黑树实现，所以有修改的接口

2.2 map 接口介绍

2.2.1 插入

map 的插入方式有三种

1. insert : 只插入一次，如果后面重复插入相同的 key 不同的 value 也不会改变 value 的数据

2. operator []

   插入又分为 key 是否以存在于 map 中，若存在则改变 value ( 假如值与原本的不一样 )；

   反之则插入 <key,value> 到 map 中

3. emplace：主要还是和 insert 形成对比，直接调用构造函数构造对象，而不是先构造才能插入

// insert
int main()
{map<string, int> m = {{"a", 1}, {"b", 2}, {"c", 3}, {"d", 4}, {"e", 5}};m.insert({"f", 6});for (auto &e : m){cout << e.first << " " << e.second << endl;}cout << endl;m.insert({"a", 10}); // 插入重复的数据for (auto &e : m){cout << e.first << " " << e.second << endl;}cout << endl;return 0;
}
/*
output:
a 1
b 2
c 3
d 4
e 5
f 6a 1
b 2
c 3
d 4
e 5
f 6
*/

// operator []
int main()
{map<string, int> m = {{"a", 1}, {"b", 2}, {"c", 3}, {"d", 4}, {"e", 5}};m["f"] = 6;for (auto &e : m){cout << e.first << " " << e.second << endl;}cout << endl;m["a"] = 10;for (auto &e : m){cout << e.first << " " << e.second << endl;}cout << endl;return 0;
}
/*
a 1
b 2
c 3
d 4
e 5
f 6a 10
b 2
c 3
d 4
e 5
f 6
*/

2.2.2 访问

// 访问可以利用迭代器、[]、或at
int main() {map<int, string> m = {{1, "Geeks"},{2, "For"}, {3, "Geeks"}};cout << m[1] << endl;cout << m.at(2);return 0;
}
/*
output:
Geeks
For
*/

2.2.3 修改

// 修改可以使用[] 或 at
int main() {map<int, string> m = {{1, "Geeks"},{2, "For"}, {3, "Geeks"}};// 修改数据m[0] = "Tweaks";m.at(1) = "By";cout << m[0] << endl;cout << m.at(1);return 0;
}
/*
output:
Tweaks
By
*/

2.2.4 查找

int main() {map<int, string> m = {{1, "Geeks"},{2, "For"}, {3, "Geeks"}};// 查找key为2的数据auto it = m.find(2);/*find : 如果有找到返回这个数据的迭代器；反之返回 end()*/if (it != m.end())cout << it->first << " " << it->second;else cout << "Key not Found!";return 0;
}

2.2.5 删除

int main() {map<int, string> m = {{1, "Geeks"},{2, "For"}, {3, "Geeks"}};// 删除m.erase(2);m.erase(m.begin());// 返回从 map 容器中删除的元素数量。对于 map ，该值始终为 1 或 0for(auto i : m)// 第一个->是迭代器运算符重载，返回pair*，第二个箭头是结构指针解引用取pair数据cout << i.first << " " << i.second // 3 Geeks<< endl;return 0;
}

2.3.6 时间复杂度

操作	时间复杂度
插入元素	O（log n）
按 key 删除元素	O（log n）
按 key 访问元素	O（log n）
按 key 查找元素	O（log n）
按 key 更新元素	O（log n）
遍历	O (n)

后续会在补充 关于红黑树的知识点