首页 > 其他分享 >map/multimap容器

map/multimap容器

时间:2024-03-15 17:37:32浏览次数:21  
标签:map multimap insert 容器 元素 key pair

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

相关文章

  • vector容器
    vector功能:vector数据结构和数组非常相似,也称为单端数组vector与普通数组区别:不同之处在于数组是静态空间,而vector可以动态扩展动态扩展:并不是在原空间之后续接新空间,而是找更大的内存空间,然后将原数据拷贝新空间,释放原空间vector容器的迭代器是支持随机访问的迭......
  • queue 和 stack 容器
    queue容器1.queue基本概念**概念:先进先出队列中只有队头和队尾才可以被外界使用,因此队列不允许有遍历行为2.queue常用接口构造函数:queue<T>que;//queue采用模板类实现,queue对象的默认构造形式queue(constqueue&que);//拷贝构造函数赋值操作:queue&operator=......
  • deque容器
    deque1.deque容器基本概念功能:双端数组,可以对头端进行插入删除操作头文件:<deque>deque与vector区别:vector对于头部的插入删除效率低,数据量越大,效率越低deque相对而言,对头部的插入删除速度回比vector快vector访问元素时的速度会比deque快,这和两者内部实现有关deque......
  • list容器
    list1.list基本概念功能:将数据进行链式存储链表(list)是一种物理存储单元上非连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接实现的链表的组成:链表由一系列结点组成结点的组成:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域STL中的链表是一个双向......
  • iOS端创建ReactNative容器第一步:打出jsbundle和资源包
    react-native的打包流程是通过执行react-nativebundle指令进行的。 添加构建指令修改RN项目中的package.json文件,先其中添加构建命令build-release-ios和build-debug-ios"scripts":{"android":"react-nativerun-android","ios":"react-nativerun-ios"......
  • idea项目mapper.xml中的SQL语句黄色下划线去除
    问题描述当我们使用idea开发java项目时,经常会与数据库打交道,一般在使用mybatis的时候需要写一大堆的mapper.xml以及SQL语句,每当写完SQL语句的时候总是有黄色下划线,看着很不舒服。解决方案:修改idea的配置Editor->Inspections打开配置页面后,在中间视窗找到sql的>点击下......
  • 【C++进阶】C++关联式容器map和set用法详解
    map和set用法详解一,关联式容器二,键值对pair三,set1.set的用法2.multiset的用法四,map1.键值对pair的介绍2.map用法3.multimap用法五,总结上一节我们讲解了二叉搜索树,在讲解之前我们先来讲一下set和map,因为set和map的底层是AVL树和红黑树,而AVL树和红黑树又是一种二......
  • resultMap 和 resultType 的字段映射覆盖问题
    在MyBatis中,如果你使用resultType而不是resultMap,并且结果集中有同名字段,则默认情况下后出现的字段值会覆盖前面的字段值。这是因为MyBatis在将结果集映射到Java对象时,是按照字段名称一一对应进行赋值的。但若你希望更精确地控制映射关系,并且避免自动覆盖行为,则可以用resultMap来......
  • set容器详解
    set 是关联容器,含有键值类型对象的已排序集,搜索、移除和插入拥有对数复杂度。set 内部通常采用 红黑树 实现。平衡二叉树 的特性使得 set 非常适合处理需要同时兼顾查找、插入与删除的情况。和数学中的集合相似,set 中不会出现值相同的元素。如果需要有相同元素的集合,......
  • MapReduce配置和YARN部署命令
    部署说明HadoopHDFS分布式文件系统,我们会启动:NameNode进程作为管理节点DataNode进程作为工作节点SecondaryNamenode作为辅助同理,HadoopYARN分布式资源调度,会启动:ResourceManager进程作为管理节点NodeManager进程作为工作节点ProxyServer、JobHistoryServer这两个辅......