E

EdwardWong

V1

2022/12/08阅读:19主题:姹紫

STL关联型容器之map容器

C++容器分为序列式容器和关联式容器,其中序列式容器(arrayvectorlistdequeforward_list)。

STL关联式容器

对于序列式容器,其存储的是C++基本数据类型(诸如intdoublefloatstring等)或使用结构体自定义类型的元素。

std::vector<int> primes{2,3,4,7,11,13,17,19};

关联式容器容器在存储元素值的同时,还会为各元素额外配备一个值(又称为),其本质也是一个C++基础数据类型或者自定义类型的元素。它的功能是在使用关联式容器的过程中,如果已知目标元素的键的值,则直接通过该键就可以找到目标元素,而无需再通过遍历整个容器的方式。

弃用序列式容器,转而选用关联式容器存储元素,往往就是看中了关联式容器可以快速查找、读取或者删除所存储的元素,同时该类型容器插入元素的效率也比序列式容器高

使用关联式容器存储的元素,都是一个一个的“键值对”( <key,value> ),这是和序列式容器最大的不同。除此之外,序列式容器中存储的元素默认都是未经过排序的,而使用关联式容器存储的元素,默认会根据各元素的键值的大小做升序排序

关联式容器所具备的特征,归咎于STL标准库在实现该类型容器时,底层选用了红黑树这种数据结构来组织和存储各个键值对。

STL关联式容器种类

C++ STL标准库提供了4种关联式容器,分为mapsetmultimapmultiset.

除此之外,C++ 11 还新增了 4 种哈希容器,即 unordered_mapunordered_multimap 以及 unordered_setunordered_multiset。严格来说,它们也属于关联式容器,但由于哈希容器底层采用的是哈希表,而不是红黑树

#include <iostream>
#include <map> //使用 map 容器,必须引入该头文件
#include <string>
using namespace std;
int main()
{
//创建一个空的 map 关联式容器,该容器中存储的键值对,其中键为 string 字符串,值也为 string 字符串类型
map<string, string> mymap;
//向 mymap 容器中添加数据
mymap["http://c.biancheng.net/c/"] = "C语言教程";
mymap["http://c.biancheng.net/python/"] = "Python教程";
mymap["http://c.biancheng.net/java/"] = "Java教程";

//使用 map 容器的迭代器,遍历 mymap 容器,并输出其中存储的各个键值对
for (map<string, string>::iterator it = mymap.begin(); it != mymap.end(); ++it) {
//输出各个元素中的键和值
cout << it->first << " => " << it->second << '\n';
}
return 0;
}

通过分析该程序的执行过程不难看出,mymap 关联式容器中的存储了以下 3 个键值对:

STL pair用法详解

注意,基于各个关联式容器存储数据的特点,只有各个键值对中的键和值全部对应相等时,才能使用 setmultiset 关联式容器存储,否则就要选用 map 或者 multimap 关联式容器

考虑到键值对并不是普通类型数据,STL标准库提供了pair类模板,其专门用来将2个普通元素firstsecond(可以是C++基本数据类型、结构体、类自定的类型)创建成一个新元素<first,second>。 使用 pair 类模板来创建“键值对”形式的元素,再合适不过。

pair 类模板定义在<utility>头文件中,所以在使用该类模板之前,需引入此头文件。另外值得一提的是,在 C++ 11 标准之前,pair 类模板中提供了以下 3 种构造函数:

#1) 默认构造函数,即创建空的 pair 对象
pair();
#2) 直接使用 2 个元素初始化成 pair 对象
pair (const first_type& a, const second_type& b);
#3) 拷贝(复制)构造函数,即借助另一个 pair 对象,创建新的 pair 对象
template<class U, class V> pair (const pair<U,V>& pr);

C++ 11标准中,在引入右值引用的基础上,pair类模板中又增添了2个构造函数:

#4) 移动构造函数
template<class U, class V> pair (pair<U,V>&& pr);
#5) 使用右值引用参数,创建 pair 对象
template<class U, class V> pair (U&& a, V&& b);
#include <iostream>
#include <utility> // pair
#include <string> // string
using namespace std;
int main() {
// 调用构造函数 1,也就是默认构造函数
pair <string, double> pair1;
// 调用第 2 种构造函数
pair <string, string> pair2("STL教程","http://c.biancheng.net/stl/");
// 调用拷贝构造函数
pair <string, string> pair3(pair2);
//调用移动构造函数
pair <string, string> pair4(make_pair("C++教程", "http://c.biancheng.net/cplus/"));
// 调用第 5 种构造函数
pair <string, string> pair5(string("Python教程"), string("http://c.biancheng.net/python/"));

cout << "pair1: " << pair1.first << " " << pair1.second << endl;
cout << "pair2: "<< pair2.first << " " << pair2.second << endl;
cout << "pair3: " << pair3.first << " " << pair3.second << endl;
cout << "pair4: " << pair4.first << " " << pair4.second << endl;
cout << "pair5: " << pair5.first << " " << pair5.second << endl;
return 0;
}

make_pair()函数也是由<utility>头文件提供的,其功能是生成一个pair对象,因此当我们将make_pair()函数的返回值(是一个临时对象)作为参数传递给pair()构造函数时,其调用的是移动构造函数,而不是拷贝构造函数

pair1.first = "Java教程";
pair1.second = "http://c.biancheng.net/java/";
cout << "new pair1: " << pair1.first << " " << pair1.second << endl;

也可以如此创建pair4对象:

pair <string, string> pair4 = make_pair("C++教程", "http://c.biancheng.net/cplus/");
cout << "pair4: " << pair4.first << " " << pair4.second << endl;

<utility>头文件中除了提供创建 pair 对象的方法之外,还为 pair 对象重载了 <<=>>===!=6 的运算符,其运算规则是:对于进行比较的 2pair 对象,先比较 pair.first 元素的大小,如果相等则继续比较 pair.second 元素的大小。

#include <iostream>
#include <utility> // pair
#include <string> // string
using namespace std;
int main() {
pair <string, int> pair1("STL教程", 20);
pair <string, int> pair2("C++教程", 20);
pair <string, int> pair3("C++教程", 30);
//pair1和pair2的key不同,value相同
if (pair1 != pair2) {
cout << "pair != pair2" << endl;
}
//pair2和pair3的key相同,value不同
if (pair2 != pair3) {
cout << "pair2 != pair3" << endl;
}
return 0;
}

pair类模板还提供一个swap()成员函数,能够互换2pair对象的键值对,其操作成功的前提是这 2pair 对象的键和值的类型要相同.

#include <iostream>
#include <utility> // pair
#include <string> // string
using namespace std;
int main() {
pair <string, int> pair1("pair", 10);
pair <string, int> pair2("pair2", 20);
//交换 pair1 和 pair2 的键值对
pair1.swap(pair2);
cout << "pair1: " << pair1.first << " " << pair1.second << endl;
cout << "pair2: " << pair2.first << " " << pair2.second << endl;
return 0;
}

STL map容器

作为关联式容器的一种,map 容器存储的都是 pair 对象,也就是用 pair 类模板创建的键值对。其中,各个键值对的键和值可以是任意数据类型,包括 C++基本数据类型(intdouble 等)、使用结构体或类自定义的类型

通常情况下,map 容器中存储的各个键值对都选用 string 字符串作为键的类型。

与此同时,在使用 map 容器存储多个键值对时,该容器会自动根据各键值对的键的大小,按照既定的规则进行排序默认情况下,map 容器选用std::less<T>排序规则(其中 T 表示键的数据类型),其会根据键的大小对所有键值对做升序排序。当然,根据实际情况的需要,我们可以手动指定 map 容器的排序规则,既可以选用 STL 标准库中提供的其它排序规则(比如std::greater<T>),也可以自定义排序规则

使用 map 容器存储的各个键值对,键的值既不能重复也不能被修改。换句话说,map 容器中存储的各个键值对不仅键的值独一无二,键的类型也会用 const 修饰.

map 容器定义在 <map> 头文件中,并位于 std 命名空间中。因此,如果想使用 map 容器,代码中应包含如下语句:

#include <map>
using namespace std;

map容器的模板定义:

template < class Key, // 指定键(key)的类型
class T, // 指定值(value)的类型
class Compare = less<Key>, // 指定排
class Alloc = allocator<pair<const Key,T>> // 指定分配器对象的类
>class map;

map 容器模板有 4 个参数,其中后 2 个参数都设有默认值。大多数场景中,我们只需要设定前 2 个参数的值,有些场景可能会用到第 3 个参数,但最后一个参数几乎不会用到。

map的创建

  1. 创建出一个空的map容器

std::map<std::string, int>myMap;

  1. 创建map容器的同时初始化

std::map<std::string, int>myMap{ {"C语言教程",10},{"STL教程",20} };

上述myMap中由两个键值对。

map容器中存储的键值对,其本质是pair类模板创建的pair对象:

std::map<std::string, int> myMap{std::make_pair("C语言中文网",10), std::make_pair("STL 教程",20)};

  1. 利用已创建好的map容器新建一个map容器

std::map<std::string,int> newMap(myMap);

C++11标准中,还为map容器增添了移动构造函数,当有临时的map对象作为参数,传递给要初始化的map容器时,此时会调用移动构造函数。

#创建一个会返回临时 map 对象的函数
std::map<std::string,int> disMap() {
std::map<std::string, int>tempMap{ {"C语言教程",10},{"STL教程",20} };
return tempMap;
}
//调用 map 类模板的移动构造函数创建 newMap 容器
std::map<std::string, int>newMap(disMap());
  1. map类模板还支持取已建map容器中指定区域内的键值对,创建并初始化新的map容器。
std::map<std::string, int>myMap{ {"C语言教程",10},{"STL教程",20} };
std::map<std::string, int>newMap(++myMap.begin(), myMap.end());

5, 手动修改map容器的排序规则

默认情况下,map容器调用std::less<T>规则,根据容器内各键值对的键的大小,对所有键值对升序排序

std::map<std::string, int>myMap{ {"C语言教程",10},{"STL教程",20} };
std::map<std::string, int, std::less<std::string> >myMap{ {"C语言教程",10},{"STL教程",20} };

手动修改myMap容器的排序规则,使其降序排序。

std::map<std::string, int, std::greater<std::string> >myMap{ {"C语言教程",10},{"STL教程",20} };

map容器的成员函数

map容器中的map中的迭代器是指向已排好序的第一个或最后一个

#include <iostream>
#include <map> // map
#include <string> // string
using namespace std;

int main() {
//创建空 map 容器,默认根据各个键值对中键的值,对键值对做降序排序
std::map<std::string, std::string, std::greater<std::string>>myMap;
//调用 emplace() 方法,直接向 myMap 容器中指定位置构造新键值对
myMap.emplace("C语言教程","http://c.biancheng.net/c/");
myMap.emplace("Python教程", "http://c.biancheng.net/python/");
myMap.emplace("STL教程", "http://c.biancheng.net/stl/");
//输出当前 myMap 容器存储键值对的个数
cout << "myMap size==" << myMap.size() << endl;
//判断当前 myMap 容器是否为空
if (!myMap.empty()) {
//借助 myMap 容器迭代器,将该容器的键值对逐个输出
for (auto i = myMap.begin(); i != myMap.end(); ++i) {
cout << i->first << " " << i->second << endl;
}
}
return 0;
}

map容器迭代器

map容器配备的是双向迭代器,这意味者map容器只能进行++pp++--pp--*p操作,并且迭代器之间只能使用==或者!=运算符进行比较。

begin()/end()成员函数

#include <iostream>
#include <map> // pair
#include <string> // string
using namespace std;

int main() {
//创建并初始化 map 容器
std::map<std::string, std::string>myMap{ {"STL教程","http://c.biancheng.net/stl/"},{"C语言教程","http://c.biancheng.net/c/"} };

//调用 begin()/end() 组合,遍历 map 容器
for (auto iter = myMap.begin(); iter != myMap.end(); ++iter) {
cout << iter->first << " " << iter->second << endl;
}
return 0;
}

find()成员函数

除此之外,map 类模板中还提供了 find() 成员方法,它能帮我们查找指定 key 值的键值对,如果成功找到,则返回一个指向该键值对的双向迭代器;反之,其功能和 end() 方法相同。

#include <iostream>
#include <map> // pair
#include <string> // string
using namespace std;

int main() {
//创建并初始化 map 容器
std::map<std::string, std::string>myMap{ {"STL教程","http://c.biancheng.net/stl/"},
{"C语言教程","http://c.biancheng.net/c/"},
{"Java教程","http://c.biancheng.net/java/"} };
//查找键为 "Java教程" 的键值对
auto iter = myMap.find("Java教程");
//从 iter 开始,遍历 map 容器
for (; iter != myMap.end(); ++iter) {
cout << iter->first << " " << iter->second << endl;
}
return 0;
}

lower_bound()upper_bound()

同时,map 类模板中还提供有 lower_bound(key) 和 upper_bound(key) 成员方法,它们的功能是类似的,唯一的区别在于:

  • lower_bound(key) 返回的是指向第一个键不小于 key 的键值对的迭代器;

  • upper_bound(key) 返回的是指向第一个键大于 key 的键值对的迭代器;

#include <iostream>
#include <map> // pair
#include <string> // string
using namespace std;

int main() {
//创建并初始化 map 容器
std::map<std::string, std::string>myMap{ {"STL教程","http://c.biancheng.net/stl/"},
{"C语言教程","http://c.biancheng.net/c/"},
{"Java教程","http://c.biancheng.net/java/"} };
//找到第一个键的值不小于 "Java教程" 的键值对
auto iter = myMap.lower_bound("Java教程");
cout << "lower:" << iter->first << " " << iter->second << endl;

//找到第一个键的值大于 "Java教程" 的键值对
iter = myMap.upper_bound("Java教程");
cout <<"upper:" << iter->first << " " << iter->second << endl;
return 0;
}

lower_bound(key)upper_bound(key) 更多用于 multimap 容器,在 map 容器中很少用到。

#include <iostream>
#include <utility> //pair
#include <map> // map
#include <string> // string
using namespace std;

int main() {
//创建并初始化 map 容器
std::map<string, string>myMap{ {"STL教程","http://c.biancheng.net/stl/"},
{"C语言教程","http://c.biancheng.net/c/"},
{"Java教程","http://c.biancheng.net/java/"} };
//**创建一个 pair 对象,来接收 equal_range() 的返回值**
pair <std::map<string, string>::iterator, std::map<string, string>::iterator> myPair = myMap.equal_range("C语言教程");
//通过遍历,输出 myPair 指定范围内的键值对
for (auto iter = myPair.first; iter != myPair.second; ++iter) {
cout << iter->first << " " << iter->second << endl;
}
return 0;
}

map获取键对应值的方法

重载运算符[]

map类模板对[]运算符进行了重载,可以借助下标通过键直接进行访问值。

#include <iostream>
#include <map> // map
#include <string> // string
using namespace std;

int main() {
//创建并初始化 map 容器
std::map<std::string, std::string>myMap{ {"STL教程","http://c.biancheng.net/stl/"},{"C语言教程","http://c.biancheng.net/c/"},{"Java教程","http://c.biancheng.net/java/"} };
string cValue = myMap["C语言教程"];
cout << cValue << endl;
return 0;
}

只有当 map 容器中确实存有包含该指定键的键值对,借助重载的 [ ] 运算符才能成功获取该键对应的值;反之,若当前 map 容器中没有包含该指定键的键值对,则此时使用 [ ] 运算符将不再是访问容器中的元素,而变成了向该 map 容器中增添一个键值对。其中,该键值对的键为 [ ] 运算符中指定的键,其对应的值取决于 map 容器规定键值对中值的数据类型,如果是基本数据类型,则值为 0;如果是 string 类型,其值为 "",即空字符串(即使用该类型的默认值作为键值对的值.

#include <iostream>
#include <map> // map
#include <string> // string
using namespace std;
int main() {
//创建空 map 容器
std::map<std::string, int>myMap;
int cValue = myMap["C语言教程"];
for (auto i = myMap.begin(); i != myMap.end(); ++i) {
cout << i->first << " "<< i->second << endl;
}
return 0;
}

可以通过[]map容器添加新的键值对:

#include <iostream>
#include <map> // map
#include <string> // string
using namespace std;

int main() {
//创建空 map 容器
std::map<string, string>myMap;
myMap["STL教程"]="http://c.biancheng.net/java/";
myMap["Python教程"] = "http://c.biancheng.net/python/";
myMap["STL教程"] = "http://c.biancheng.net/stl/";
for (auto i = myMap.begin(); i != myMap.end(); ++i) {
cout << i->first << " " << i->second << endl;
}
return 0;
}

在上述代码中,第二次出现的myMap["STL教程"]会修改第一次myMap["STL 教程"]="http://c.biancheng.net/java/"的值。

at()成员函数

at() 成员方法也需要根据指定的键,才能从容器中找到该键对应的值;不同之处在于,如果在当前容器中查找失败,该方法不会向容器中添加新的键值对,而是直接抛出 out_of_range 异常。

#include <iostream>
#include <map> // map
#include <string> // string
using namespace std;

int main() {
//创建并初始化 map 容器
std::map<std::string, std::string>myMap{ {"STL教程","http://c.biancheng.net/stl/"},
{"C语言教程","http://c.biancheng.net/c/"},
{"Java教程","http://c.biancheng.net/java/"} };

cout << myMap.at("C语言教程") << endl;
//下面一行代码会引发 out_of_range 异常
//cout << myMap.at("Python教程") << endl;
return 0;
}

find()成员函数

#include <iostream>
#include <map> // map
#include <string> // string
using namespace std;

int main() {
//创建并初始化 map 容器
std::map<std::string, std::string>myMap{ {"STL教程","http://c.biancheng.net/stl/"},
{"C语言教程","http://c.biancheng.net/c/"},
{"Java教程","http://c.biancheng.net/java/"} };

map< std::string, std::string >::iterator myIter = myMap.find("C语言教程");
cout << myIter->first << " " << myIter->second << endl;
return 0;
}

使用iterator迭代器遍历的方法

#include <iostream>
#include <map> // map
#include <string> // string
using namespace std;

int main() {
//创建并初始化 map 容器
std::map<std::string, std::string>myMap{ {"STL教程","http://c.biancheng.net/stl/"},
{"C语言教程","http://c.biancheng.net/c/"},
{"Java教程","http://c.biancheng.net/java/"} };

for (auto iter = myMap.begin(); iter != myMap.end(); ++iter) {
//调用 string 类的 compare() 方法,找到一个键和指定字符串相同的键值对
if (!iter->first.compare("C语言教程")) {
cout << iter->first << " " << iter->second << endl;
}
}
return 0;
}

map插入数据的方式

使用重载运算符[]

C++ STL map 类模板中对[ ]运算符进行了重载,即根据使用场景的不同,借助[ ]运算符可以实现不同的操作。

#include <iostream>
#include <map> //map
#include <string> //string
using namespace std;
int main()
{
std::map<string, string> mymap{ {"STL教程","http://c.biancheng.net/java/"} };
//获取已存储键值对中,指定键对应的值
cout << mymap["STL教程"] << endl;

//向 map 容器添加新键值对
mymap["Python教程"] = "http://c.biancheng.net/python/";

//修改 map 容器已存储键值对中,指定键对应的值
mymap["STL教程"] = "http://c.biancheng.net/stl/";

for (auto iter = mymap.begin(); iter != mymap.end(); ++iter) {
cout << iter->first << " " << iter->second << endl;
}

return 0;
}

使用insert()成员函数

除了使用 [ ] 运算符实现向 map 容器中添加新键值对外,map 类模板中还提供有 insert() 成员方法,该方法专门用来向 map 容器中插入新的键值对。

当使用 insert() 方法向 map 容器的指定位置插入新键值对时,其底层会先将新键值对插入到容器的指定位置,如果其破坏了 map 容器的有序性,该容器会对新键值对的位置进行调整。

  1. 无需指定插入位置,直接将键值对添加到 map 容器中
//1、引用传递一个键值对
pair<iterator,bool> insert (const value_type& val);
//2、以右值引用的方式传递键值对
template <class P>
pair<iterator,bool> insert (P&& val);

其中,val 参数表示键值对变量,同时该方法会返回一个 pair 对象,其中 pair.first 表示一个迭代器,pair.second 为一个 bool 类型变量

  • 如果成功插入 val,则该迭代器指向新插入的 valbool 值为 true

  • 如果插入 val 失败,则表明当前 map 容器中存有和 val 的键相同的键值对(用 p 表示),此时返回的迭代器指向 pbool 值为 false

#include <iostream>
#include <map> //map
#include <string> //string
using namespace std;
int main()
{
//创建一个空 map 容器
std::map<string, string> mymap;

//创建一个真实存在的键值对变量
std::pair<string, string> STL = { "STL教程","http://c.biancheng.net/stl/" };

//创建一个接收 insert() 方法返回值的 pair 对象
std::pair<std::map<string, string>::iterator, bool> ret;

//插入 STL,由于 STL 并不是临时变量,因此会以第一种方式传参
ret = mymap.insert(STL);
cout << "ret.iter = <{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;

//以右值引用的方式传递临时的键值对变量
ret = mymap.insert({ "C语言教程","http://c.biancheng.net/c/" });
cout << "ret.iter = <{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;

//插入失败样例
ret = mymap.insert({ "STL教程","http://c.biancheng.net/java/" });
cout << "ret.iter = <{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;
return 0;
}

从执行结果中不难看出,程序中共执行了 3 次插入操作,其中成功了 2 次,失败了 1 次:

  • 对于插入成功的 insert() 方法,其返回的 pair 对象中包含一个指向新插入键值对的迭代器和值为 1bool 变量

  • 对于插入失败的 insert() 方法,同样会返回一个 pair 对象,其中包含一个指向 map 容器中键为 "STL教程" 的键值对和值为 0bool 变量。

ret = mymap.insert({ "C语言教程","http://c.biancheng.net/c/" });
//调用 pair 类模板的构造函数
ret = mymap.insert(pair<string,string>{ "C语言教程","http://c.biancheng.net/c/" });
//调用 make_pair() 函数
ret = mymap.insert(make_pair("C语言教程", "http://c.biancheng.net/c/"));
  1. insert() 方法还支持向 map 容器的指定位置插入新键值对,该方法的语法格式如下:
//以普通引用的方式传递 val 参数
iterator insert (const_iterator position, const value_type& val);
//以右值引用的方式传递 val 键值对参数
template <class P>
iterator insert (const_iterator position, P&& val);

这里insert函数返回的不是pair<iterator,bool>类型,而是返回迭代器类型

  • 如果插入成功,insert() 方法会返回一个指向 map 容器中已插入键值对的迭代器;
  • 如果插入失败,insert() 方法同样会返回一个迭代器,该迭代器指向 map 容器中和 val 具有相同键的那个键值对。
#include <iostream>
#include <map> //map
#include <string> //string
using namespace std;
int main()
{
//创建一个空 map 容器
std::map<string, string> mymap;

//创建一个真实存在的键值对变量
std::pair<string, string> STL = { "STL教程","http://c.biancheng.net/stl/" };
//指定要插入的位置
std::map<string, string>::iterator it = mymap.begin();
//向 it 位置以普通引用的方式插入 STL
auto iter1 = mymap.insert(it, STL);
cout << iter1->first << " " << iter1->second << endl;

//向 it 位置以右值引用的方式插入临时键值对
auto iter2 = mymap.insert(it, std::pair<string, string>("C语言教程", "http://c.biancheng.net/c/"));
cout << iter2->first << " " << iter2->second << endl;

//插入失败样例
auto iter3 = mymap.insert(it, std::pair<string, string>("STL教程", "http://c.biancheng.net/java/"));
cout << iter3->first << " " << iter3->second << endl;
return 0;
}
  1. insert()方法支持向当前map容器插入其他map容器指定区域内的所有键值对。

template<class InputIterator> void insert(InputIterator first, InputIterator last);

其中 firstlast 都是迭代器,它们的组合<first,last>可以表示某 map 容器中的指定区域。

#include <iostream>
#include <map> //map
#include <string> //string
using namespace std;
int main()
{
//创建并初始化 map 容器
std::map<std::string, std::string>mymap{ {"STL教程","http://c.biancheng.net/stl/"},
{"C语言教程","http://c.biancheng.net/c/"},
{"Java教程","http://c.biancheng.net/java/"} };
//创建一个空 map 容器
std::map<std::string, std::string>copymap;
//指定插入区域
std::map<string, string>::iterator first = ++mymap.begin();
std::map<string, string>::iterator last = mymap.end();
//将<first,last>区域内的键值对插入到 copymap 中
copymap.insert(first, last);
//遍历输出 copymap 容器中的键值对
for (auto iter = copymap.begin(); iter != copymap.end(); ++iter) {
cout << iter->first << " " << iter->second << endl;
}
return 0;
}
  1. insert()方法还允许一次向map容器中插入多个键值对 void insert({val1,val2,...}) 其中,val1都表示是键值对变量
#include <iostream>
#include <map> //map
#include <string> //string
using namespace std;
int main()
{
//创建空的 map 容器
std::map<std::string, std::string>mymap;
//向 mymap 容器中添加 3 个键值对
mymap.insert({ {"STL教程", "http://c.biancheng.net/stl/"},
{ "C语言教程","http://c.biancheng.net/c/" },
{ "Java教程","http://c.biancheng.net/java/" } });

for (auto iter = mymap.begin(); iter != mymap.end(); ++iter) {
cout << iter->first << " " << iter->second << endl;
}
return 0;
}

STL map operator[]和insert()效率对比

#include <iostream>
#include <map> //map
#include <string> //string
using namespace std;
int main()
{
std::map<string, string> mymap;
//借用 operator[] 添加新键值对
mymap["STL教程"] = "http://c.biancheng.net/java/";
cout << "old mymap:" << mymap["STL教程"] << endl;
//借用 operator[] 更新某个键对应的值
mymap["STL教程"] = "http://c.biancheng.net/stl/";
cout << "new mymap:" << mymap["STL教程"] << endl;

//借用insert()添加新键值对
std::pair<string, string> STL = { "Java教程","http://c.biancheng.net/python/" };
std::pair<std::map<string, string>::iterator, bool> ret;
ret = mymap.insert(STL);
cout << "old ret.iter = <{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;
//借用 insert() 更新键值对
mymap.insert(STL).first->second = "http://c.biancheng.net/java/";
cout << "new ret.iter = <" << ret.first->first << ", " << ret.first->second << ">" << endl;
return 0;
}

当实现“向 map 容器中添加新键值对元素”的操作时,insert() 成员方法的执行效率更高;而在实现“更新 map 容器指定键值对的值”的操作时,operator[ ] 的效率更高。

map中的emplace()emplace_hint()方法

insert() 方法相比,emplace()emplace_hint() 方法的使用要简单很多,因为它们各自只有一种语法格式

emplace()方法

template<class...Args>
pair<iterator,bool> emplace(Args &&...args)

参数 (Args&&... args) 指的是,这里只需要将创建新键值对所需的数据作为参数直接传入即可,此方法可以自行利用这些数据构建出指定的键值对。该方法的返回值也是一个 pair 对象,其中 pair.first 为一个迭代器,pair.second 为一个 bool 类型变量.

  • 当该方法将键值对成功插入到 map 容器中时,其返回的迭代器指向该新插入的键值对,同时 bool 变量的值为 true

  • 当插入失败时,则表明 map 容器中存在具有相同键的键值对,此时返回的迭代器指向此具有相同键的键值对,同时 bool 变量的值为 false.

#include <iostream>
#include <map> //map
#include <string> //string
using namespace std;

int main()
{
//创建并初始化 map 容器
std::map<string, string>mymap;
//插入键值对
pair<map<string, string>::iterator, bool> ret = mymap.emplace("STL教程", "http://c.biancheng.net/stl/");
cout << "1、ret.iter = <{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;
//插入新键值对
ret = mymap.emplace("C语言教程", "http://c.biancheng.net/c/");
cout << "2、ret.iter = <{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;

//失败插入的样例
ret = mymap.emplace("STL教程", "http://c.biancheng.net/java/");
cout << "3、ret.iter = <{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;
return 0;
}

emplace_hint()方法

emplace_hint() 方法的功能和 emplace() 类似,其语法格式如下:

  • 该方法不仅要传入创建键值对所需要的数据,还需要传入一个迭代器作为第一个参数,指明要插入的位置新键值对键会插入到该迭代器指向的键值对的前面);
#include <iostream>
#include <map> //map
#include <string> //string
using namespace std;

int main()
{
//创建并初始化 map 容器
std::map<string, string>mymap;
//指定在 map 容器插入键值对
map<string, string>::iterator iter = mymap.emplace_hint(mymap.begin(),"STL教程", "http://c.biancheng.net/stl/");
cout << iter->first << " " << iter->second << endl;

iter = mymap.emplace_hint(mymap.begin(), "C语言教程", "http://c.biancheng.net/c/");
cout << iter->first << " " << iter->second << endl;

//插入失败样例
iter = mymap.emplace_hint(mymap.begin(), "STL教程", "http://c.biancheng.net/java/");
cout << iter->first << " " << iter->second << endl;
return 0;
}

map容器插入函数的效率

emplace()emplace_hint()函数的执行效率比insert()函数高,原因在于:

  • 使用 insert()map 容器中插入键值对的过程是,先创建该键值对,然后再将该键值对复制或者移动到 map 容器中的指定位置

  • 使用 emplace()emplace_hint() 插入键值对的过程是,直接在 map 容器中的指定位置构造该键值对。

分类:

后端

标签:

数据结构与算法

作者介绍

E
EdwardWong
V1