STEMHA

student

China

文章

分类

标签

105

关注我

2020-05-19

C++

10 分钟读完 (大约 1444 个字)

map常用操作

基本概念

map

map不能直接修改关键字，只能通过修改关键字的值间接修改关键字。
底层数据结构为红黑树，有序，不重复
map<K，T> 类模板定义在 map 文件头中，它定义了一个保存 T 类型对象的 map，每个 T 类型的对象都有一个关联的 K 类型的键。容器内对象的位置是通过比较键决定的。

头文件

1	# include<map>

模板

template < class Key, class T, class Pred = less<Key>, class A = allocator<T> >
class map{
    ...
    typedef pair< const Key, T > value_type;
    ...
};

经常使用的，默认是less
map<int,double,less<int> > MYMAP;      元素升序
map<int,double,greater<int> > MYMAP;   元素降序

pair初始化方法

map<int,int> q;
map<k, v> m;	    创建一个名为 m 的空 map 对象，其键和值的类型分别为 k 和 v
map<k, v> m(m2);	创建 m2 的副本 m，m 与 m2 必须有相同的键类型和值类型
map<k, v> m(b, e);	创建 map 类型的对象 m，存储迭代器 b 和 e 标记的范围内所有元素的副本。元素的类型必须能转换为 pair<const k, v>

交换

swap(map<K,V>& other)：和参数的元素进行交换，所包含对象的类型必须相同。：将当前 map 中的元素和参数 map 中的元素交换。它们需要包含相同类型的元素。也可以调用全局函数模板 swap() 来完成同样的操作。

1 2	template <class T1, class T2> void swap(map<K,V> &x)　重载1：x.swap(y) template <class T1, class T2> void swap (map<K,V>& x, map<K,V>& y) 重载2: swap(x, y)

map定义的类型

1
2
3

map<K,V>::key_type	    在 map 容器中，用做索引的键的类型
map<K,V>::mapped_type	在 map 容器中，键所关联的值的类型
map<K,V>::value_type	一个 pair 类型，它的first 元素具有 const map<K,V>::key_type 类型，而 second 元素则为 map<K,V>::mapped_type 类型

常用操作

使用下标访问 map 对象

1
2
3

map <string, int> word_count; // empty map
// insert default initialzed element with key Anna; then assign 1 to its value
word_count["Anna"] = 1;  存在则改变，不存在则加入

查找

map<int,int>q;

q.insert(pair<int,int>(1,2)); //通过pair进行插入操作
q.insert(map<int,int>::value_type (1,2));//通过value_type进行插入
q[1] = 2; //用数组方式进行插入
三者不同的是，当map存在这个关键字时数组方式会覆盖关键字的值，而insert操作无法插入。

1
2
3

m.insert(e)	e 是一个用在 m 上的 value_type 类型的值。如果键（e.first）不在 m 中，则插入一个值为 e.second 的新元素；如果该键在 m 中已存在，则保持 m 不变。该函数返回一个pair 类型对象，包含指向键为 e.first 的元素的 map 迭代器，以及一个 bool 类型的对象，表示是否插入了该元素
m.insert(beg,end)	beg 和 end 是标记元素范围的迭代器，其中的元素必须为m.value_type 类型的键－值对。对于该范围内的所有元素，如果它的键在 m 中不存在，则将该键及其关联的值插入到 m。(返回 void 类型)
m.insert(iter,e)	e 是一个用在 m 上的 value_type 类型的值。如果键（e.first）不在 m 中，则创建新元素，并以迭代器 iter 为起点搜索新元素存储的位置。(返回一个迭代器，指向 m 中具有给定键的元素)。

比较函数

1 2	q.key_comp(); 返回比较元素key的函数 q.value_comp(); 返回比较元素value的函数

大小与是否为空

1
2
3

q.size();      返回容器内元素个数
q.empty();     判断容器是否为空
q.max_size();  返回可以容纳的最大元素个数

删除

q.erase(iter); 删除迭代器iter的元素
q.erase(iter1,iter2);删除[iter1,iter2)区间内的元素
q.erase(key);  删除关键字为key的元素
q.clear();     清空容器

查找和计数

1
2

q.count(k)	返回 m 中 k 的出现次数,（map中有则返回1，否则0）
q.find(k)	如果 m 容器中存在按 k 索引的元素，则返回指向该元素的迭代器。如果不存在，则返回超出末端迭代器

使用 count 检查 map 对象中某键是否存在

1
2
3

int occurs = 0;
if (word_count.count("foobar"))
	occurs = word_count["foobar"];

迭代器

q.begin(); //返回头位置迭代器
q.end(); //返回尾位置迭代器
q.rbegin(); //返回尾部反向迭代器
q.rend(); //返回头部反向迭代器

查找迭代器

1
2
3

m.lower_bound();返回键值>=给定元素的第一个位置 返回一个迭代器
m.upper_bound();返回键值>给定元素的第一个位置 返回一个迭代器
m.equal_range();返回一个迭代器的 pair 对象。它的 first 成员等价于 m.lower_bound(k)。而 second 成员则等价于 m.upper_bound(k)

初始化为0

使用C++中的map容器定义一个mp，当你执行if语句判断mp[3]是否为1时，那么如果mp[3]以前不存在，此时mp[3]就会被无参初始化，second赋值为0。

int main(){
    vector<int> numbers;
	int n = numbers.size();

    map<int, int> m;
    int count;
    for (int i = 0; i < n; i++) {
        count = ++m[numbers[i]]; //这里原来元素是不存在的，但是却可以直接加1；
        if (count > n/2) return numbers[i];
    }
    return 0;
}

参考资料

关于map容器的元素被无参初始化
 《C++Primer》第十章-关联容器-学习笔记(1)-pair&map
C++ map是什么
 C++标准库容器类概述

# C++标准库, map

目录

链接

分类

标签云

最新文章

归档

标签