map/ multimap 容器
1. map 基本概念
简介:
- map中所有元素都是pair
- pair中第一个元素为key(键值),起到索引作用,第二个元素为value(实值)
- 所有元素都会根据元素的键值自动排序
- 对于 map 的底层原理,是通过红黑树(一种非严格意义上的平衡二叉树)来实现的,因此 map 内部所有的数据都是有序的
- map 的查询、插入、删除操作的时间复杂度都是 O (logn)。
- 此外,map 的 key 需要定义 operator <,对于一般的数据类型已被系统实现,若是用户自定义的数据类型,则要重新定义该操作符。
map和multimap区别:
- map不允许容器中有重复key值元素
- multimap允许容器中有重复key值元素
2. map 构造和赋值
构造:
map<T1, T2> mp;
//map默认构造函数:map(const map &mp);
//拷贝构造函数
赋值:
map& operator=(const map &mp);
//重载等号操作符
示例:
map<int,int>m; //默认构造
map<int, int>m2(m); // 拷贝构造
m3 = m2; // 重载等号
3. map 大小和交换
函数原型:
size();
//返回容器中元素的数目empty();
//判断容器是否为空swap(st);
//交换两个集合容器
示例:
map<int, int> m, m1;
m.insert(pair<int, int>(1, 10));
m.size();
m.empty();
m.swap(m1);
4. map 插入和删除
函数原型:
insert(elem);
//在容器中插入元素。clear();
//清除所有元素erase(pos);
//删除pos 迭代器所指的元素,返回下一个元素的迭代器。erase(beg, end);
//删除区间[beg,end)的所有元素 ,返回下一个元素的迭代器。erase(key);
//删除容器中值为key的元素。
示例:
void printMap(map<int,int>&m)
{
for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
{
cout << "key = " << it->first << " value = " << it->second << endl;
}
cout << endl;
}
void test01()
{
//插入
map<int, int> m;
//第一种插入方式
m.insert(pair<int, int>(1, 10));
//第二种插入方式
m.insert(make_pair(2, 20));
//第三种插入方式
m.insert(map<int, int>::value_type(3, 30));
//第四种插入方式
m[4] = 40;
printMap(m);
//删除 --迭代器
m.erase(m.begin());
// 使用迭代器
map<int, int>::iteration it = m.begin();
m.erase(++it);
printMap(m);
// -- 元素
m.erase(3);
printMap(m);
//清空
m.erase(m.begin(),m.end());
m.clear();
printMap(m);
}
int main() {
test01();
system("pause");
return 0;
}
5. map 查找和统计
函数原型:
find(key);
//查找key是否存在,若存在,返回该键的元素的迭代器;若不存在,返回set.end();count(key);
//统计key的元素个数
示例:
m.find(3);
m.count(3);
总结:
- 查找 --- find (返回的是迭代器)
- 统计 --- count (对于map,结果为0或者1)
6. map 容器排序
学习目标:
- map容器默认排序规则为 按照key值进行 从小到大排序,掌握如何改变排序规则
主要技术点:
- 利用仿函数,可以改变排序规则
示例:
#include <map>
class MyCompare {
public:
bool operator()(const int &v1, const int &v2) const{
return v1 > v2;
}
};
void test01()
{
//默认从小到大排序
//利用仿函数实现从大到小排序
map<int, int, MyCompare> m;
m.insert(make_pair(1, 10));
m.insert(make_pair(2, 20));
m.insert(make_pair(3, 30));
m.insert(make_pair(4, 40));
m.insert(make_pair(5, 50));
for (map<int, int, MyCompare>::iterator it = m.begin(); it != m.end(); it++) {
cout << "key:" << it->first << " value:" << it->second << endl;
}
}
int main()
{
test01();
system("pause");
return 0;
}
自定义数据类型的排序
#include<iostream>
#include<string>
#include<set>
#include <map>
using namespace std;
struct person
{
string name;
int age;
person(string name, int age)
{
this->name = name;
this->age = age;
}
bool operator < (const person& p) const
{
return this->age < p.age;
}
};
int main()
{
map<person, int> m;
// 插入数据
m.insert(make_pair(person("Alice", 30), 100));
m.insert(make_pair(person("Bob", 25), 200));
m.insert(make_pair(person("Charlie", 35), 300));
// 输出数据
for (auto it = m.begin(); it != m.end(); ++it)
{
cout << "Name: " << it->first.name << ", Age: " << it->first.age << ", Value: " << it->second << endl;
}
return 0;
}
总结:
- 利用仿函数可以指定 map 容器的排序规则
- 利用仿函数实现的自定义排序,是对键值而言,无法对 value 而言
- 对于自定义数据类型,map 必须要指定排序规则,同 set 容器
7. unordered_map
- unordered_map 和 map 类似,都是存储的 key-value 的值,可以通过 key 快速索引到 value。
- 不同的是 unordered_map 不会根据 key 的大小进行排序,存储时是根据 key 的 hash 值判断元素是否相同,即 unordered_map 内部元素是无序的。
- unordered_map 的底层是一个防冗余的哈希表(开链法避免地址冲突)。
- 哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,时间复杂度为 O(1);而代价仅仅是消耗比较多的内存。
头文件:<unordered_map>
#include<string>
#include<iostream>
#include<unordered_map>
using namespace std;
int main()
{
unordered_map<string, int> dict; // 声明unordered_map对象
// 插入数据的三种方式
dict.insert(pair<string,int>("apple",2));
dict.insert(unordered_map<string, int>::value_type("orange",3));
dict["banana"] = 6;
// 判断是否有元素
if(dict.empty())
cout<<"该字典无元素"<<endl;
else
cout<<"该字典共有"<<dict.size()<<"个元素"<<endl;
// 遍历
unordered_map<string, int>::iterator iter;
for(iter=dict.begin();iter!=dict.end();iter++)
cout<<iter->first<<ends<<iter->second<<endl;
// 查找
if(dict.count("boluo")==0)
cout<<"can't find boluo!"<<endl;
else
cout<<"find boluo!"<<endl;
if((iter=dict.find("banana"))!=dict.end())
cout<<"banana="<<iter->second<<endl;
else
cout<<"can't find boluo!"<<endl;
return 0;
}
标签:map,multimap,insert,容器,元素,key,pair
From: https://www.cnblogs.com/xingzhuz/p/18075878