map和set的使用

序列式容器和关联式容器

c++标准库为我们提供了多种容器类型，可以大体分为两类：序列式容器和关联式容器。

序列式容器按照线性顺序储存数据，元素的位置取决与插入的时间和地点。关联式容器基于键值对存储元素，提供高效的键查找能力。关联式容器的两个元素是按照键值以某种顺序储存起来的，所以任意两个元素不能交换位置，会破化容器的结构。接下来要学习的map和set都是关联式容器。

set的使用

set介绍

set的模板参数

template <class T,//键值类型class Compare = std::less<T>,/仿函数用来控制顺序class Alloc = std::allocator<T>>
class set;

1.T就是键值的类型。

2.在默认情况下，set支持的是小于比较，可以自己写仿函数。

3.set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第三个参

set的构造和迭代器

set的构造只关注以下几个接口即可：

set支持正向和反向迭代器，遍历默认按升序，底层是二叉树，走中序；支持的迭代器也就意味着我们可以使用范围for遍历。

注意：set的普通迭代器和const迭代器都不支持修改，修改键值key会破坏树的结构。

迭代器区间构造

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>#include<set>using namespace std;
int main()
{set<int> s;s.emplace(1);s.emplace(2);s.emplace(3);s.emplace(4);s.emplace(5);s.emplace(6);s.emplace(7);s.emplace(8);s.emplace(9);s.emplace(10);s.emplace(11);//迭代器区间构造set<int>  s1(s.begin(), s.end());}

 拷贝构造

#include<iostream>#include<set>using namespace std;
int main()
{set<int> s;s.emplace(1);s.emplace(2);s.emplace(3);s.emplace(4);s.emplace(5);s.emplace(6);s.emplace(7);s.emplace(8);s.emplace(9);s.emplace(10);s.emplace(11);//迭代器区间构造set<int>  s1(s.begin(), s.end());//拷贝构造set<int>  s2(s1);
}

列表构造

#include <iostream>
#include <set>
#include <string>int main() {// 初始化整数集合std::set<int> numbers = {3, 1, 4, 1, 5, 9};  // 重复的1只会保留一个// 初始化字符串集合std::set<std::string> words{"apple", "banana", "orange"};// 输出内容std::cout << "Numbers: ";for(int n : numbers) {std::cout << n << " ";  // 自动排序输出: 1 3 4 5 9}std::cout << "\nWords: ";for(const auto& w : words) {std::cout << w << " ";  // 按字典序输出: apple banana orange}return 0;
}

列表构造的特点：

1.自动去重：有重复的元素只保留一个

2.自动排序：元素会根据比较器自动排序

3.类型安全：编译器会检查类型是否匹配

4.窄化转化检查：禁止可能导致数据丢失的隐式转换

双向迭代器

set的迭代器是双向迭代器，既能前移，又能后移。

#include <iostream>
#include <set>int main() {std::set<int> numbers = {10, 20, 30, 40, 50};// 正向遍历std::cout << "Forward: ";for(auto it = numbers.begin(); it != numbers.end(); ++it) {std::cout << *it << " ";}std::cout << "\n";// 反向遍历std::cout << "Reverse: ";for(auto rit = numbers.rbegin(); rit != numbers.rend(); ++rit) {std::cout << *rit << " ";}std::cout << "\n";// 双向移动auto it = numbers.find(30);if(it != numbers.end()) {std::cout << "Found 30\n";--it;  // 移动到前一个元素(20)std::cout << "Previous: " << *it << "\n";++++it;  // 向后移动两个位置(40)std::cout << "After two steps: " << *it << "\n";}return 0;
}

  set的增删查

pair<iterator,bool>

在c++标准库容器中（特别是map和set），pair<iterator,bool>是一种常见的返回值类型，用于表示插入操作的结果。

pair<iterator,bool>是一个模板类，包含两个成员：

1.first ：一个迭代器，指向要插入的元素（无论是否插入了新的元素）

2.second ：一个布尔值，表示是否插入成功

#include <iostream>
#include <set>
#include <string>int main() {std::set<std::string> fruitSet = {"apple", "banana", "orange"};// 尝试插入新元素auto result1 = fruitSet.insert("pear");if(result1.second) {std::cout << "成功插入: " << *result1.first << "\n";} else {std::cout << "元素已存在: " << *result1.first << "\n";}// 尝试插入已存在元素auto result2 = fruitSet.insert("apple");if(result2.second) {std::cout << "成功插入: " << *result2.first << "\n";} else {std::cout << "元素已存在: " << *result2.first << "\n";}return 0;
}

insert

迭代器区间插入

#include <iostream>
#include <set>
#include <vector>int main() {std::set<int> mySet;std::vector<int> vec = {5, 2, 8, 3, 1};// 使用迭代器区间插入mySet.insert(vec.begin(), vec.end());// 输出结果for(int num : mySet) {std::cout << num << " ";  // 输出: 1 2 3 5 8}std::cout << std::endl;return 0;
}

单个数据插入

#include <iostream>
#include <set>int main() {std::set<std::string> fruitSet;// 单个数据插入auto result1 = fruitSet.insert("apple");std::cout << "插入apple: " << (result1.second ? "成功" : "失败") << std::endl;auto result2 = fruitSet.insert("apple");std::cout << "再次插入apple: " << (result2.second ? "成功" : "失败") << std::endl;// 输出结果for(const auto& fruit : fruitSet) {std::cout << fruit << " ";  // 输出: apple}std::cout << std::endl;return 0;
}

列表插入（c++11）

#include <iostream>
#include <set>int main() {std::set<int> mySet = {10, 20};  // 初始化时使用列表// 列表插入mySet.insert({30, 15, 25, 10});  // 10已存在，不会被重复插入// 输出结果for(int num : mySet) {std::cout << num << " ";  // 输出: 10 15 20 25 30}std::cout << std::endl;return 0;
}

查找

find

声明：

// 查找val，返回val所在的迭代器，没有找到返回end()
iterator find (const value_type& val);

#include <iostream>
#include <set>
#include <string>int main() {std::set<std::string> fruitSet = { "apple", "banana", "orange" };// 尝试插入新元素auto result1 = fruitSet.insert("pear");if (result1.second) {std::cout << "成功插入: " << *result1.first << "\n";}else {std::cout << "元素已存在: " << *result1.first << "\n";}// 尝试插入已存在元素auto result2 = fruitSet.insert("apple");if (result2.second) {std::cout << "成功插入: " << *result2.first << "\n";}else {std::cout << "元素已存在: " << *result2.first << "\n";}auto a = fruitSet.find("boy");if (a == fruitSet.end()){cout << "end" << endl;}return 0;
}

count

声明：

在set中没有重复的元素，所以返回值只能是0或1

// 查找val，返回Val的个数
size_type count (const value_type& val) const;

#include <iostream>
#include <set>
#include <string>int main() {set<int> fruitSet = { 1,5,56,1,5,};if (fruitSet.count(1)){cout << "找到了" << endl;}return 0;
}

erase

删除一个迭代器位置的值

#include <iostream>
#include <set>int main() {std::set<int> mySet = { 10, 20, 30, 40, 50 };// 查找要删除的元素auto it = mySet.find(30);// 确保元素存在后再删除if (it != mySet.end()) {mySet.erase(it);  // 删除迭代器指向的元素}// 输出结果for (int num : mySet) {std::cout << num << " ";  // 输出: 10 20 40 50}std::cout << std::endl;return 0;
}

删除值val

#include <iostream>
#include <set>int main() {std::set<std::string> fruitSet = { "apple", "banana", "orange", "pear" };// 删除特定值size_t count = fruitSet.erase("banana");  // 返回删除的元素数量(0或1)std::cout << "删除了 " << count << " 个元素\n";// 尝试删除不存在的值count = fruitSet.erase("grape");std::cout << "删除了 " << count << " 个元素\n";// 输出结果for (const auto& fruit : fruitSet) {std::cout << fruit << " ";  // 输出: apple orange pear}std::cout << std::endl;return 0;
}

删除一段迭代器区间的值

#include <iostream>
#include <set>int main() {std::set<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};// 查找区间起点和终点auto first = numbers.find(3);auto last = numbers.find(8);// 删除区间[first, last)内的元素if (first != numbers.end() && last != numbers.end()) {numbers.erase(first, last);  // 删除3到7(不包括8)}// 输出结果for (int num : numbers) {std::cout << num << " ";  // 输出: 1 2 8 9 10}std::cout << std::endl;return 0;
}

lower_bound和upper_bound

// 返回⼤于等val位置的迭代器
iterator lower_bound (const value_type& val) const;
// 返回⼤于val位置的迭代器
iterator upper_bound (const value_type& val) const;

#include <iostream>
#include <set>int main() {std::set<int> mySet = { 10, 20, 30, 40, 50 };auto a = mySet.lower_bound(20);cout << *a << endl;auto b = mySet.upper_bound(40);cout << *b << endl;return 0;
}

multiset和set的区别

multi为前缀，意为“多”。顾名思义,multiset的和set的不同在于multiset允许插入相等的元素。

如果存在多个相等的值：

count()函数可以返回元素在树中的具体数量。

erase()会删除所有所有与要删除值val相等的值

find()返回中序的第一个元素

multiset在set在其他方面完全相同

map的使用

map类的介绍

template < class Key, // 键值的类型
class T, // 与键值关联值的类型
class Compare = less<Key>, // 仿函数控制顺序
class Alloc = allocator<pair<const Key,T> > 
> class map;

与set不同的是,map储存的是一个键值对，类型为pair<const Key,T>，在前文中提到了平衡二叉搜索树的key-value场景【数据结构】二叉搜索树-CSDN博客。T就是这个value>。

map可以通过[ ]访问元素。但是这个[ ]并不是平时遇到的下标+[ ]的组合。set中重载了[]。通过键值访问元素。

#include<map>
using namespace std;int main() {map<std::string, int> wordCounts;// 使用 operator[] 插入和访问元素wordCounts["apple"] = 5;    // 插入新键值对wordCounts["banana"] = 3;   // 插入新键值对std::cout << "apple count: " << wordCounts["apple"] << std::endl;  // 输出 5std::cout << "banana count: " << wordCounts["banana"] << std::endl; // 输出 3// 访问不存在的键会自动插入std::cout << "orange count: " << wordCounts["orange"] << std::endl; // 输出 0 (int的默认值)// 修改现有值wordCounts["apple"] = 10;std::cout << "updated apple count: " << wordCounts["apple"] << std::endl; // 输出 10return 0;
}

map的构造

map的增删查

map插入的是pair键值对数据，但是查和删只用关键字Key与set完全类似，find返回迭代器，可以通过这个迭代器修改value。

insert

插入一个键值对

#include<iostream>
#include<string>
#include<map>using namespace std;int main()
{map<string, int>  mymap;auto res1 = mymap.insert({"蔡徐坤", 2});if (res1.second){cout << "插入成功" << endl;}return 0;
}

列表初始化 

#include<iostream>
#include<string>
#include<map>using namespace std;int main()
{map<string, int>  mymap;auto res1 = mymap.insert({"蔡徐坤", 2.5});if (res1.second){cout << "插入成功" << endl;}mymap.insert({ { "某某某",3 },{"某某",4} });return 0;
}

迭代器区间初始化

#include<iostream>
#include<string>
#include<map>using namespace std;int main()
{map<string, int>  mymap;auto res1 = mymap.insert({"蔡徐坤", 2.5});if (res1.second){cout << "插入成功" << endl;}mymap.insert({ { "某某某",3 },{"某某",4} });map<string, int> mymap2;mymap2.insert(mymap.begin(), mymap.end());return 0;
}

find

#include<iostream>
#include<string>
#include<map>using namespace std;int main()
{map<string, int>  mymap;auto res1 = mymap.insert({"蔡徐坤", 2.5});if (res1.second){cout << "插入成功" << endl;}mymap.insert({ { "某某某",3 },{"某某",4} });map<string, int> mymap2;mymap2.insert(mymap.begin(), mymap.end());auto a = mymap.find("蔡徐坤");if (a != mymap.end()){cout << "找到了" << endl;}return 0;
}

count

map也不能允许相同的key值存在

#include<iostream>
#include<string>
#include<map>using namespace std;int main()
{map<string, int>  mymap;auto res1 = mymap.insert({"蔡徐坤", 2.5});if (res1.second){cout << "插入成功" << endl;}mymap.insert({ { "某某某",3 },{"某某",4} });map<string, int> mymap2;mymap2.insert(mymap.begin(), mymap.end());//auto a = mymap.find("蔡徐坤");//if (a != mymap.end())//{//	cout << "找到了" << endl;//}mymap.insert({ "蔡徐坤",5 });auto it = mymap.count("蔡徐坤");cout << it << endl;return 0;
}

erase

删除一个迭代器位置的值

#include<iostream>
#include<string>
#include<map>using namespace std;int main()
{map<string, int>  mymap;auto res1 = mymap.insert({ "蔡徐坤", 2.5 });if (res1.second){cout << "插入成功" << endl;}mymap.insert({ { "某某某",3 },{"某某",4} });map<string, int> mymap2;mymap2.insert(mymap.begin(), mymap.end());auto a = mymap.begin();mymap.erase(a);return 0;
}

删除k

#include<iostream>
#include<string>
#include<map>using namespace std;int main()
{map<string, int>  mymap;auto res1 = mymap.insert({ "蔡徐坤", 2.5 });if (res1.second){cout << "插入成功" << endl;}mymap.insert({ { "某某某",3 },{"某某",4} });map<string, int> mymap2;mymap2.insert(mymap.begin(), mymap.end());mymap.erase("蔡徐坤");return 0;
}

删除一段迭代器区间

#include<iostream>
#include<string>
#include<map>using namespace std;int main()
{map<string, int>  mymap;auto res1 = mymap.insert({ "蔡徐坤", 2.5 });if (res1.second){cout << "插入成功" << endl;}mymap.insert({ { "某某某",3 },{"某某",4} });map<string, int> mymap2;mymap2.insert(mymap.begin(), mymap.end());mymap.erase(mymap.begin(),mymap.end()--);return 0;
}

lower_bound和upper_bound

和set类似

map的数据修改

直接用[ ]修改

#include <iostream>
#include <map>
#include <string>int main() {std::map<std::string, int> ages = {{"Alice", 25},{"Bob", 30},{"Charlie", 35}};// 修改已存在的键的值ages["Bob"] = 31;  // 将Bob的年龄从30改为31return 0;
}

find()+迭代器修改

#include <iostream>
#include <map>
#include <string>int main() {std::map<std::string, int> ages = {{"Alice", 25},{"Bob", 30},{"Charlie", 35}};// 查找并修改auto it = ages.find("Bob");if (it != ages.end()) {it->second = 31;  // 安全修改}// 尝试修改不存在的键it = ages.find("David");if (it == ages.end()) {std::cout << "David not found in the map" << std::endl;}return 0;
}

at()方法修改（c++11）

#include <iostream>
#include <map>
#include <string>
#include <stdexcept>int main() {std::map<std::string, int> ages = {{"Alice", 25},{"Bob", 30},{"Charlie", 35}};try {// 修改已存在的键ages.at("Bob") = 31;// 尝试修改不存在的键会抛出异常// ages.at("David") = 40;  // 会抛出std::out_of_range}catch (const std::out_of_range& e) {std::cerr << "Error: " << e.what() << std::endl;}return 0;
}

multimap和map差异

同set和multiset。