目录
在初阶阶段,我们已经接触过STL中的部分容器,比如:vector、list、deque。forward_list(C++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面 存储的是元素本身。那什么是关联式容器?它与序列式容器有什么区别?
关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是<key, value>结构的 键值对,在数据检索时比序列式容器效率更高
用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代 表键值,value表示与key对应的信息。比如:现在要建立一个英汉互译的字典,那该字典中必然 有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该应 该单词,在词典中就可以找到与其对应的中文含义
template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair() : first(T1()), second(T2())
{}
pair(const T1& a, const T2& b) : first(a), second(b)
{}
};
根据应用场景的不桶,STL总共实现了两种不同结构的管理式容器:树型结构与哈希结构。树型结构的关联式容器主要有四种:map、set、multimap、multiset。这四种容器的共同点是:使用平衡搜索树(即红黑树)作为其底层结果,容器中的元素是一个有序的序列。下面一依次介绍每一个容器
3.1 set
注意:
构造函数:
(1):构造空的set (2):用[first, last)区间中的元素构造set (3):set的拷贝构造
迭代器:
容量:
对元素修改:
在set中插入元素x,实际插入的是<x, x>构成的键值对,如果插入成功,返回<该元素在set中的 位置,true>,如果插入失败,说明x在set中已经存在,返回<x在set中的位置,false>
(1):删除set中position位置上的元素 (2):删除set中值为x的元素,返回删除的元素的个数 (3):删除set中[first, last)区间中的元素
交换set中的元素
将set中的元素清空
返回set中值为x的元素的位置
返回set中值为x的元素的个数
在C++中,set
是基于红黑树实现的一个关联容器,它存储有序的不重复元素。这意味着 set
内部元素默认是按照升序排列的,且每个元素值都是唯一的。
set
提供了两个非常有用的成员函数,lower_bound
和 upper_bound
,它们用于在有序容器中查找特定元素范围的迭代器。
lower_bound
lower_bound
函数返回一个指向当前set
中不小于给定值的第一个元素的迭代器。如果给定值在set
中不存在,它将返回指向下一个更大的元素的迭代器;如果给定值大于set
中的任何元素,它将返回指向set
末尾的迭代器。
换句话说,lower_bound
返回的是指向set
中第一个不小于(即大于等于)给定值的元素的迭代器
用法示例:
std::set<int> s;
s.insert(1);
s.insert(3);
s.insert(5);
auto it_lower = s.lower_bound(3); // it_lower 现在指向元素 3
auto it_lower2 = s.lower_bound(4); // it_lower2 现在指向元素 5
upper_bound
upper_bound
函数返回一个指向当前set
中大于给定值的第一个元素的迭代器。如果所有的元素都小于给定值,它将返回指向set
末尾的迭代器。
upper_bound
返回的是指向set
中第一个大于给定值的元素的迭代器。
用法示例:
std::set<int> s;
s.insert(1);
s.insert(3);
s.insert(5);
auto it_upper = s.upper_bound(3); // it_upper 现在指向元素 5
auto it_upper2 = s.upper_bound(5); // it_upper2 现在指向 set 的末尾
注意点
lower_bound
和 upper_bound
如果给定值不存在于set
中,它们不会向 set
添加元素。multiset
和 map
,multimap
等关联容器,其行为是类似的。const
迭代器,取决于容器实例是否是const
)。set
背后的数据结构是红黑树,它是一种自平衡的二叉搜索树。在处理范围查询或是在有序集合中寻找下界或上界时,lower_bound
和 upper_bound
函数非常有用
大部分都与map相同,这里只看特殊的:
这里的key是不能修改的,用pair键值对存储
这里insert插入的是一个键值对,我们来使用一下:
void test_map1()
{
map<string, string> dict;
pair<string, string> kv1("banana", "香蕉");
dict.insert(kv1);
dict.insert(pair<string, string>("left", "左边"));
dict.insert(make_pair("apple", "苹果"));
dict.insert({ "right" ,"右边" });
}
方法1: 使用pair对象直接插入
std::pair<std::string, std::string> kv1("banana", "香蕉");
dict.insert(kv1);
这里,首先创建了一个名为kv1
的pair
对象,包含键“banana”和值“香蕉”。然后使用insert
方法将其插入到dict
中
方法2: 使用构造函数构造pair直接插入
dict.insert(std::pair<std::string, std::string>("left", "左边"));
这里直接使用std::pair
的构造函数创建了一个匿名的pair
对象,并将它插入到dict
中。这个pair
对象包含键“left”和值“左边”。
方法3: 使用make_pair创建pair直接插入
dict.insert(std::make_pair("apple", "苹果"));
在此,std::make_pair
函数模板被用来创建一个匿名的pair
对象,并直接插入到dict
中。这个pair
对象包含键“apple”和值“苹果”。make_pair
有助于减少冗长的类型名称,因为模板类型参数会被自动推导
make_pair返回值为pair类型 第四种插入方式:
dict.insert({ "right" ,"右边" });
不是初始化列表(initializer list)的标准用法,这里是构造函数的隐式类型转换。这种方式实际上利用了std::pair
的构造函数,它能接收两个参数并将它们转换为一个pair
对象。因为std::map
的insert
方法重载接收一个std::pair<const KeyType, ValueType>
类型的对象,编译器可以通过构造函数隐式类型转换,从提供的两个值创建一个pair
对象。
map初始化列表使用:
map<string, string>dict2 = { {"banana", "香蕉"},{"left", "左边"} };
我们遍历上面的dict:
错误方法:
auto it = dict.begin();
while (it != dict.end())
{
cout << *it << " ";
++it;
}
cout << endl;
迭代器指向的是一对键值对,而不仅仅是单个值。这些键值对在 map 内部被存储为 std::pair<const KeyType, ValueType>
类型的对象。因此,当尝试打印迭代器指向的元素时,需要专门引用键(first 成员)和值(second 成员),而不能直接打印迭代器
key不能修改,value可以修改
const迭代器都不能修改
这里的迭代器和链表的迭代器很像,这里我们遍历如下:
while (it != dict.end())
{
//std::cout << (*it).first << ": " << (*it).second << " ";
std::cout << it->first << ": " << it->second << " ";
++it;
}
void test_map2()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };
map<string, int> countMap;
for (auto& e : arr)
{
countMap[e]++;
//auto it = countMap.find(e);
//if (it != countMap.end())
//{
// it->second++;
//}
//else
//{
// //const pair<string, int>& val = { e, 1 };
// countMap.insert({ e, 1 });
//}
}
for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}
通过表达式countMap[e]++自增相应字符串键对应的值。如果e作为键在map中还不存在,map会使用默认构造函数创建一个对应的int值(初始值为0),然后执行++操作将其的值增加到1。如果键已存在,则其对应的值会被自增
operator[]
std::map
的operator[]
是一个非常实用的成员函数,它允许你通过键值来访问映射中的元素。这个操作符的行为取决于给定的键是否存在于映射中。
当你使用类似mapObj[key]
的表达式时,会发生以下情况:
键存在于容器中:该函数会返回一个引用,指向与给定键相匹配的映射值。
例如:
std::map<int, std::string> m;
m[1] = "one";
std::string val = m[1]; // 返回 "one"
键不存在于容器中:该函数将会插入一个新元素,键为k
,并使用映射类型的默认构造函数来初始化它的值。随后函数返回一个引用,指向这个新插入元素的映射值。
例如:
std::map<int, std::string> m;
m[2]; // 插入键为2的新元素,其值初始化为std::string的默认值(空字符串)
std::string val = m[2]; // 返回空字符串
在这个示例中,如果m
中不存在键2
的元素,那么会创建一个新的std::string
对象(其值为默认构造的空字符串),并将其与键2
关联。这个新元素会被插入到map
中。
operator[]
非常方便,因为它允许在一个操作中读取或者插入元素值。但有一点需要注意,它会默默地插入新元素,如果你不想在映射中添加任何新元素(只访问已有元素),那么应该使用at
成员函数,它在键不存在时会抛出std::out_of_range
异常。
最后的行文解释了如何将operator[]
实现为一系列操作的组合:
(*((this->insert(make_pair(k,mapped_type()))).first)).second
这行代码展示了如果没有使用operator[]
时,插入一个新元素并获取其值所需执行的操作:
make_pair(k,mapped_type())
创建一个新的键值对。this->insert()
将这个键值对插入到映射中,如果键已存在,insert
什么也不做并返回现有元素。insert
返回一个pair
,其中first
是一个迭代器,指向映射中元素的位置,而second
是一个布尔值,指示插入是否成功。(*iterator).second
或iterator->second
来访问元素的值。实际上,operator[]
内部会进行一些优化来避免不必要的元素创建,但上述代码段提供了逻辑上等效于operator[]
所做工作的概念性说明
对于 std::map
的 insert
方法,当你尝试插入一个新元素时(例如使用一个键值对作为参数),它的返回值确实是一个 pair
。这个 pair
中的 first
成员是一个迭代器,它指向映射中具有特定键的元素的位置,无论这个元素是否是刚刚被插入的新元素还是已经存在的元素。second
成员是一个布尔值,它表示元素是否被插入成功。
如果尝试插入的元素的键已经存在于映射中,则新元素不会被插入,second
将会是 false
,而 first
会指向那个已经存在的元素。如果键不存在,则新元素将被插入,此时 second
为 true
,而 first
指向这个新揳入的元素。
这是 insert
方法的精髓所在:它不会覆盖已有的键值对,而是只在键尚未存在时才插入新元素。
举个例子:
std::map<int, std::string> m;
// 尝试插入元素 {1, "one"}
std::pair<std::map<int, std::string>::iterator, bool> result = m.insert({1, "one"});
if (result.second) {
// 插入成功,result.first 指向新插入的元素
} else {
// 插入失败,result.first 指向现存相同键的元素
}
在这里,result.first
是指向映射中具有键 1
的元素的迭代器,而 result.second
说明了元素 {1, "one"}
是否成功插入到映射中。如果键 1
之前不存在于 m
中,那么 result.second
会是 true
。
这里两个pair不一样
operator[]的原理是:
可以用count快速判断元素在不在
multiset
是一个集合容器,它类似于set
,但在multiset
中相同的元素可以出现多次。multiset
中的元素按照特定顺序排列,默认情况下是使用元素类型的 <
运算符来进行升序排列。
特性:
operator[]
)。例子:
#include <iostream>
#include <set>
int main() {
std::multiset<int> ms;
ms.insert(1);
ms.insert(1); // 同样的元素可以被插入多次
ms.insert(2);
for (auto elem : ms) {
std::cout << elem << " "; // 输出: 1 1 2
}
return 0;
}
multimap
类似于 map
,但一个键可以关联多个值。就像 multiset
允许多个相同的元素一样,multimap
允许多个不同的键值对拥有相同的键。
特性:
const
,对于值,可以通过迭代器间接修改).例子:
#include <iostream>
#include <map>
int main() {
std::multimap<int, std::string> mm;
mm.insert(std::make_pair(1, "apple"));
mm.insert(std::make_pair(1, "banana")); // 同一个键对应不同的值
mm.insert(std::make_pair(2, "cherry"));
for (auto& kv : mm) {
std::cout << kv.first << " => " << kv.second << "\n"; // 输出: 1 => apple
// 1 => banana
// 2 => cherry
}
return 0;
}
在使用 multiset
和 multimap
时,重要的是记住,它们会根据元素的键自动排序,但是你不能期望通过某一个键快速访问到单独的一个元素,因为可能存在多个具有相同键的元素。在查找、删除或插入具有特定键的元素时,可能会涉及到多个元素。这意味着,当你执行操作例如 equal_range
时,可能会返回一个元素的范围,而不是单个元素
equal_range
是 C++ 标准模板库(STL)中关联容器(例如 set
、multiset
、map
和 multimap
)的成员函数,用于获取容器中与给定键相等的元素范围。它返回一个包含两个迭代器的 pair
,这对迭代器分别代表键等于给定键的元素序列的开始和结束
当在普通的(非multi)容器中使用 equal_range
时,返回的范围包含零个或一个元素。而在允许键重复的 multiset
和 multimap
容器中,返回的范围可能包含多个元素。
equal_range
的返回值是一个 pair
:
first
成员是一个迭代器,指向第一个不小于给定的键的元素,或者如果给定的键不存在于容器中,则是指向给定键的上界second
成员是一个迭代器,指向第一个大于给定的键的元素,或者如果给定的键不存在于容器中,则是指向给定键的上界如果不存在与给定键相等的元素,则两个迭代器都会等于 upper_bound
对应的迭代器,这意味着它们都会指向同一个位置,表示一个空范围。
这是 equal_range
使用的一个简单示例:
std::multimap<int, std::string> mm;
mm.insert(std::make_pair(1, "apple"));
mm.insert(std::make_pair(1, "banana"));
mm.insert(std::make_pair(2, "cherry"));
// 查找键为1的元素的范围
auto range = mm.equal_range(1);
for (auto it = range.first; it != range.second; ++it) {
std::cout << it->first << " => " << it->second << '\n';
}
在这个示例中,equal_range(1)
会找到所有键为 1
的元素,并返回一个包含两个迭代器的 pair
,这些迭代器标记着范围的开始和结束。然后可以使用这个范围来遍历所有键为 1
的元素,这里将打印出:
1 => apple
1 => banana
总之,equal_range
很有用,特别是在处理有重复键的关联容器时,它提供了一种方法来同时访问所有具有特定键的元素
看个例题:
题目链接:692. 前K个高频单词 题目描述:
class Solution {
public:
class comp{
public:
bool operator()(pair<string,int> p1,pair<string,int> p2)
{
return (p1.second>p2.second)||(p1.second==p2.second&&p1.first<p2.first);
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> m1;
for(auto& word : words) {
m1[word]++;
}
vector<pair<string,int>> v1(m1.begin(),m1.end());
sort(v1.begin(),v1.end(),comp());
vector<string> v2;
for(int i=0;i<k;i++)
{
v2.push_back(v1[i].first);
}
return v2;
}
};
定义了一个名为
comp` 的比较类,用来确定两个单词的排序顺序:首先是按照频率从高到低排序,如果频率相同,则按字典序从小到大排序。
在 topKFrequent
函数中:
std::map
来统计每个单词的出现次数。std::map
中的元素复制到一个 vector
中,使得每个映射转变成一个 pair<string,int>
对象,并存储于 vector v1
中std::sort
对这个 vector
进行排序,排序标准为自定义的 comp
比较器。这会使频率最高的单词排在前面,并且在频率相同的情况下字典序小的单词排在前面vector
中提取前 k
个单词,并将它们放入新的 vector v2
中k
个最频繁单词的 vector v2