容器库(13)-std::unordered_multimap

2024-02-27 04:44
文章标签 容器 std 13 unordered multimap

本文主要是介绍容器库(13)-std::unordered_multimap,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

unordered_multimap是含有键值对的无序关联容器,搜索、移除和插入操作是平均常数的时间复杂度。unordered_multimap在内部没有按任何顺序排列,而是放在桶当中的,放进哪个桶是通过计算key的hash值来决定的。和unordered_map不同的是,unordered_multimap中的key值可以重复。

template<class Key,class T,class Hash = std::hash<Key>,class KeyEqual = std::equal_to<Key>,class Allocator = std::allocator<std::pair<const Key, T>>
> class unordered_multimap;

本文章的代码库:

https://gitee.com/gamestorm577/CppStd

成员函数

构造、析构和赋值

构造函数

可以构造一个空的unordered_multimap,也可以用迭代器、另一个unordered_multimap或者元素列表来构造一个unordered_multimap。构造的时候还可以指定最小桶数、hash函数、比较函数或者分配器。代码示例:

std::unordered_multimap<int, float> m1;
std::unordered_multimap<int, float> m2{{1, 1.1f}, {1, 1.2f}, {2, 1.3f}};
std::unordered_multimap<int, float> m3(m2);
std::unordered_multimap<int, float> m4(m2.begin(), std::next(m2.begin(), 2));std::cout << "m1 size = " << m1.size() << std::endl;
std::cout << "m2 size = " << m2.size() << std::endl;
std::cout << "m3 size = " << m3.size() << std::endl;
std::cout << "m4 size = " << m4.size() << std::endl;

输出结果:

m1 size = 0
m2 size = 3
m3 size = 3
m4 size = 2

对于自定义的类型,需要定义hash函数以及比较函数。代码示例:

struct MyStruct
{int Num1;double Num2;
};struct MyHash
{std::size_t operator()(const MyStruct& val) const{return std::hash<int>()(val.Num1) + std::hash<double>()(val.Num2);}
};struct MyEqual
{bool operator()(const MyStruct& lhs, const MyStruct& rhs) const{return true;}
};std::unordered_multimap<MyStruct, int, MyHash, MyEqual> m;

析构函数

销毁容器时,会调用各元素的析构函数。代码示例:

struct MyStruct
{MyStruct(int i): Num(i){}~MyStruct(){std::cout << "destruct, Num = " << Num << std::endl;}int Num = 0;
};struct MyHash
{std::size_t operator()(const MyStruct& val) const{return std::hash<int>()(val.Num);}
};struct MyEqual
{bool operator()(const MyStruct& lhs, const MyStruct& rhs) const{return lhs.Num == rhs.Num;}
};std::unordered_multimap<MyStruct, float, MyHash, MyEqual> m;
m.emplace(MyStruct(1), 1.1f);
m.emplace(MyStruct(1), 2.1f);
m.emplace(MyStruct(2), 3.1f);
std::cout << "end" << std::endl;

输出结果:

destruct, Num = 1
destruct, Num = 1
destruct, Num = 2
end
destruct, Num = 2
destruct, Num = 1
destruct, Num = 1

赋值函数

可以用另一个unordered_map或者元素列表给unordered_map赋值。代码示例:

std::unordered_multimap<int, float> tmp{{1, 1.1f}, {1, 1.2f}, {2, 1.3f}};
std::unordered_multimap<int, float> m1;
std::unordered_multimap<int, float> m2;
m1 = tmp;
m2 = {{1, 1.1f}, {2, 1.2f}};
std::cout << "m1 size = " << m1.size() << std::endl;
std::cout << "m2 size = " << m2.size() << std::endl;

输出结果:

m1 size = 3
m2 size = 2

迭代器

接口begin、cbegin指向容器起始的迭代器,end、cend指向末尾的迭代器。代码示例:

std::unordered_multimap<int, float> tmp{{1, 1.1f}, {1, 1.2f}, {3, 1.3f}};
for (auto iter = tmp.begin(); iter != tmp.end(); ++iter)
{iter->second += 10.f;
}for (auto iter = tmp.cbegin(); iter != tmp.cend(); ++iter)
{std::cout << "value = " << iter->second << std::endl;
}

输出结果:

value = 11.3
value = 11.1
value = 11.2

容器

empty

检查容器是否为空。代码示例:

std::unordered_multimap<int, float> m1{{1, 1.1f}, {1, 1.2f}, {3, 1.3f}};
std::unordered_multimap<int, float> m2;
std::cout << std::boolalpha;
std::cout << "m1 empty: " << m1.empty() << std::endl;
std::cout << "m2 empty: " << m2.empty() << std::endl;

输出结果:

m1 empty: false
m2 empty: true

size

返回容器的元素个数。代码示例:

std::unordered_multimap<int, float> m1{{1, 1.1f}, {1, 1.2f}, {3, 1.3f}};
std::unordered_multimap<int, float> m2;
std::cout << "m1 size: " << m1.size() << std::endl;
std::cout << "m2 size: " << m2.size() << std::endl;

输出结果:

m1 size: 3
m2 size: 0

max_size

返回容器可容纳的最大元素个数。代码示例:

std::unordered_multimap<char, char> m1;
std::unordered_multimap<double, double> m2;
std::cout << "m1 max size = " << m1.max_size() << std::endl;
std::cout << "m2 max size = " << m2.max_size() << std::endl;

输出结果:

m1 max size = 768614336404564650
m2 max size = 576460752303423487

修改器

clear

清除所有的元素。代码示例:

std::unordered_multimap<int, float> m{{1, 1.1f}, {1, 1.2f}, {3, 1.3f}};
std::cout << "m size = " << m.size() << std::endl;
m.clear();
std::cout << "m size = " << m.size() << std::endl;

输出结果:

m size = 3
m size = 0

insert

插入元素,参数可以是元素、迭代器或者元素节点。代码示例:

std::unordered_multimap<int, float> m1{{1, 1.1f}, {2, 1.2f}};
std::unordered_multimap<int, float> m2{{1, 1.1f}, {2, 1.2f}};
std::cout << "m1 size = " << m1.size() << std::endl;
m1.insert(m2.begin(), m2.end());
std::cout << "m1 size = " << m1.size() << std::endl;
m1.insert({1, 1.2f});
std::cout << "m1 size = " << m1.size() << std::endl;

输出结果:

m1 size = 2
m1 size = 4
m1 size = 5

emplace

构造元素到容器中。代码示例:

std::unordered_multimap<int, float> m{{1, 1.1f}, {2, 1.2f}};
m.emplace(1, 1.5f);
m.emplace(2, 2.5f);
for (auto& [key, value] : m)
{std::cout << "key: " << key << ", value: " << value << std::endl;
}

输出结果:

key: 2, value: 1.2
key: 2, value: 2.5
key: 1, value: 1.1
key: 1, value: 1.5

emplace_hint

向容器中尽可能靠近hint之前的位置插入新元素:

不同的hint会导致插入元素的效率不同。代码示例:

auto timer = [](std::function<std::size_t()> func, std::string tag) -> void
{auto start = std::chrono::system_clock::now();std::size_t size = func();auto end = std::chrono::system_clock::now();std::chrono::duration<double, std::milli> time = end - start;std::cout << tag << ", size: " << size << ", use time: " << time.count()<< std::endl;
};const int count = 1000000;auto unordered_multimap_emplace = [=]() -> std::size_t
{std::unordered_multimap<int, float> m;for (int i = 0; i < count; ++i){m.emplace(i, 1.1f);}return m.size();
};auto unordered_multimap_emplace_hint1 = [=]() -> std::size_t
{std::unordered_multimap<int, float> m;auto iter = m.begin();for (int i = 0; i < count; ++i){m.emplace_hint(iter, i, 1.1f);iter = m.end();}return m.size();
};auto unordered_multimap_emplace_hint2 = [=]() -> std::size_t
{std::unordered_multimap<int, float> m;auto iter = m.begin();for (int i = 0; i < count; ++i){m.emplace_hint(iter, i, 1.1f);iter = m.begin();}return m.size();
};auto unordered_multimap_emplace_hint3 = [=]() -> std::size_t
{std::unordered_multimap<int, float> m;auto iter = m.begin();for (int i = 0; i < count; ++i){iter = m.emplace_hint(iter, i, 1.1f);}return m.size();
};timer(unordered_multimap_emplace, "unordered_multimap_emplace");
timer(unordered_multimap_emplace_hint1, "unordered_multimap_emplace_hint1");
timer(unordered_multimap_emplace_hint2, "unordered_multimap_emplace_hint2");
timer(unordered_multimap_emplace_hint3, "unordered_multimap_emplace_hint3");

输出结果:

unordered_multimap_emplace, size: 1000000, use time: 192.404
unordered_multimap_emplace_hint1, size: 1000000, use time: 234.959
unordered_multimap_emplace_hint2, size: 1000000, use time: 249.606
unordered_multimap_emplace_hint3, size: 1000000, use time: 227.878

erase

移除指定位置的元素或者移除指定key值的元素。代码示例:

std::unordered_multimap<int, float> m1{{1, 1.1f}, {2, 1.2f}, {3, 1.3f}, {4, 1.4f}};
std::cout << "m1 size = " << m1.size() << std::endl;
m1.erase(m1.begin());
std::cout << "m1 size = " << m1.size() << std::endl;
m1.erase(m1.begin(), std::next(m1.begin(), 2));
std::cout << "m1 size = " << m1.size() << std::endl;std::unordered_multimap<int, float> m2{{1, 1.1f}, {1, 1.2f}, {2, 1.3f}, {2, 1.4f}};
std::cout << "m2 size = " << m2.size() << std::endl;
m2.erase(1);
std::cout << "m2 size = " << m2.size() << std::endl;

输出结果:

m1 size = 4
m1 size = 3
m1 size = 1
m2 size = 4
m2 size = 2

swap

和另一个容器交换元素内容。代码示例:

std::unordered_multimap<int, float> m1{{1, 1.1f}, {1, 1.2f}, {3, 1.3f}};
std::unordered_multimap<int, float> m2{{1, 1.1f}, {1, 1.2f}};
m1.swap(m2);
std::cout << "m1 size = " << m1.size() << std::endl;
std::cout << "m2 size = " << m2.size() << std::endl;

输出结果:

m1 size = 2
m2 size = 3

extract

提取容器中的某个元素节点,提取后容器不再拥有该元素。代码示例:

std::unordered_multimap<int, float> m{{1, 1.1f}, {1, 1.2f}, {3, 1.3f}};
auto node1 = m.extract(m.begin());
std::cout << "node1 key: " << node1.key() << ", value: " << node1.mapped()<< std::endl;
std::cout << "m size " << m.size() << std::endl;
auto node2 = m.extract(m.begin()->first);
std::cout << "m size " << m.size() << std::endl;
node2.key() += 20;
node2.mapped() += 20;
m.insert(std::move(node2));
std::cout << "m size " << m.size() << std::endl;
for (auto& [key, value] : m)
{std::cout << "key: " << key << ", value: " << value << std::endl;
}

输出结果:

node1 key: 3, value: 1.3
m size 2
m size 1
m size 2
key: 1, value: 1.2
key: 21, value: 21.1

merge

合并另一个unordered_map或者unordered_multimap的元素。代码示例:

std::unordered_multimap<int, float> m1{{1, 1.1f}, {2, 1.2f}};
std::unordered_multimap<int, float> m2{{1, 1.2f}, {2, 1.3f}};
m1.merge(m2);
std::cout << "m1 size = " << m1.size() << std::endl;
std::cout << "m2 size = " << m2.size() << std::endl;

输出结果:

m1 size = 4
m2 size = 0

查找

count

获取给定key值的元素数量。代码示例:

std::unordered_multimap<int, float> m{{1, 1.1f}, {1, 1.2f}, {3, 1.3f}};
std::cout << "m key 1 count: " << m.count(1) << std::endl;
std::cout << "m key 3 count: " << m.count(3) << std::endl;
std::cout << "m key 4 count: " << m.count(4) << std::endl;

输出结果:

m key 1 count: 2
m key 3 count: 1
m key 4 count: 0

find

获取指定key值的元素的迭代器。代码示例:

std::unordered_multimap<int, float> m{{1, 1.1f}, {1, 1.2f}, {3, 1.3f}};
auto iter1 = m.find(1);
auto iter2 = m.find(4);
std::cout << std::boolalpha;
std::cout << "elment has key 1: " << (iter1 == m.end()) << std::endl;
std::cout << "elment has key 4: " << (iter2 == m.end()) << std::endl;

输出结果:

elment has key 1: false
elment has key 4: true

contains

检查是否包含特定key的元素。代码示例:

std::unordered_multimap<int, float> m{{1, 1.1f}, {1, 1.2f}, {3, 1.3f}};
std::cout << std::boolalpha;
std::cout << "contain key 1: " << m.contains(1) << std::endl;
std::cout << "contain key 4: " << m.contains(4) << std::endl;

输出结果:

contain key 1: true
contain key 4: false

equal_range

获取容器中等于给定key值的元素范围。返回第一个迭代器指向范围的首元素,第二个迭代器指向范围的最后一个元素的下一个位置。代码示例:

std::unordered_multimap<int, float> m{{1, 1.1f}, {2, 1.2f}, {2, 1.3f}, {2, 1.4f}, {5, 1.5f}};
for (auto item : m)
{std::cout << item.first << " ";
}
std::cout << std::endl;auto [iter1, iter2] = m.equal_range(2);
for (auto iter = iter1; iter != iter2; ++iter)
{std::cout << "k: " << iter->first << ", val: " << iter->second << "\n";
}

输出结果:

5 2 2 2 1 
k: 2, val: 1.2
k: 2, val: 1.3
k: 2, val: 1.4

桶接口

bucket_count

返回容器的桶数量。代码示例:

std::unordered_multimap<int, float> m{{1, 1.1f}, {1, 1.2f}, {3, 1.3f}};
std::cout << "bucket count = " << m.bucket_count() << std::endl;

输出结果:

bucket count = 5

max_bucket_count

返回容器可以容纳的最大桶数量。代码示例:

std::unordered_multimap<int, float> m;
std::cout << "max bucket count = " << m.max_bucket_count() << std::endl;

输出结果:

max bucket count = 768614336404564650

bucket_size

返回给定索引的桶中的元素数量。代码示例:

std::unordered_multimap<int, float> m{{1, 1.1f}, {1, 1.2f}, {3, 1.3f}};
for (int i = 0; i < m.bucket_count(); ++i)
{std::cout << "bucket " << i << " has item num " << m.bucket_size(i)<< std::endl;
}

输出结果:

bucket 0 has item num 0
bucket 1 has item num 2
bucket 2 has item num 0
bucket 3 has item num 1
bucket 4 has item num 0

bucket

返回给定key值的元素所在桶的索引。代码示例:

std::unordered_multimap<int, float> m{{11, 1.1f}, {11, 1.2f}, {12, 1.3f}};
auto n = m.bucket(11);
std::cout << "item 11 is in bucket " << n << std::endl;

输出结果:

item 11 is in bucket 1

begin、cbegin、end、cend

std::unordered_multimap<int, float> m{{11, 1.1f}, {11, 1.2f}, {31, 1.3f}, {31, 1.1f}, {52, 1.2f}};
auto cnt = m.bucket(31);
auto iter_begin = m.begin(cnt);
auto iter_end = m.end(cnt);
for (auto i = iter_begin; i != iter_end; ++i)
{std::cout << "k: " << i->first << ", val: " << i->second << std::endl;
}

输出结果:

k: 11, val: 1.1
k: 11, val: 1.2
k: 31, val: 1.3
k: 31, val: 1.1

散列策略

load_factor

返回每个桶的平均元素数量。代码示例:

std::unordered_multimap<int, float> m{{11, 1.1f}, {11, 1.2f}, {31, 1.3f}};
float num = m.load_factor();
std::cout << "load factor is: " << num << std::endl;

输出结果:

load factor is: 0.6

max_load_factor

没有参数的情况下返回最大平均桶数。参数为float类型时设置每个桶的平均最大元素数量,如果超出了该数量,容器就会自己增加桶数。代码示例:

int n_count = 200;std::unordered_multimap<int, float> m1;
m1.max_load_factor(1);
for (int i = 0; i < n_count; ++i)
{m1.emplace(i, 1.0f);
}
std::cout << "m1 max load factor is: " << m1.max_load_factor() << std::endl;
std::cout << "m1 bucket count: " << m1.bucket_count() << std::endl;std::unordered_multimap<int, float> m2;
m2.max_load_factor(20);
for (int i = 0; i < n_count; ++i)
{m2.emplace(i, 1.0f);
}
std::cout << "m2 max load factor is: " << m2.max_load_factor() << std::endl;
std::cout << "m2 bucket count: " << m2.bucket_count() << std::endl;

输出结果:

m1 max load factor is: 1
m1 bucket count: 397
m2 max load factor is: 20
m2 bucket count: 11

rehash

设置桶的最小数量并重新散列容器。代码示例:

std::unordered_multimap<int, float> m;
for (int i = 0; i < 200; ++i)
{m.emplace(i, 1.0f);
}
std::cout << "bucket cnt: " << m.bucket_count() << std::endl;m.rehash(m.bucket_count() / 2);
std::cout << "bucket cnt: " << m.bucket_count() << std::endl;
m.rehash(m.bucket_count() * 4);
std::cout << "bucket cnt: " << m.bucket_count() << std::endl;

输出结果:

bucket cnt: 397
bucket cnt: 211
bucket cnt: 853

reserve

设置桶的最小元素个数,并重新散列容器。重新散列后的容器的平均元素数量不能超过设定的值。代码示例:

std::unordered_multimap<int, float> m;
for (int i = 0; i < 200; ++i)
{m.emplace(i, 1.0f);
}
std::cout << "bucket cnt: " << m.load_factor() << std::endl;m.rehash(5);
std::cout << "bucket cnt: " << m.load_factor() << std::endl;

输出结果:

bucket cnt: 0.503778
bucket cnt: 0.947867

观察器

hash_function

返回计算hash值的函数。代码示例:

std::unordered_multimap<std::string, float> m;
auto hash_func = m.hash_function();
std::cout << "hash is: " << hash_func("hello world") << std::endl;

输出结果:

hash is: 12386028635079221413

key_eq

返回用于比较key相等性的函数。代码示例:

std::unordered_multimap<int, std::string> m;
auto key_eq_func = m.key_eq();
std::cout << std::boolalpha;
std::cout << key_eq_func(1, 1) << std::endl;
std::cout << key_eq_func(1, 2) << std::endl;

输出结果:

true
false

非成员函数

比较运算符

比较两个容器是否相等。代码示例:

std::unordered_multimap<int, float> m1{{1, 1.1f}, {1, 1.2f}, {3, 1.3f}};
std::unordered_multimap<int, float> m2{{1, 1.1f}, {1, 1.2f}};
std::cout << std::boolalpha;
std::cout << "m1 == m2: " << (m1 == m2) << std::endl;
std::cout << "m1 != m2: " << (m1 != m2) << std::endl;

输出结果:

m1 == m2: false
m1 != m2: true

swap

交换两个容器的元素。代码示例:

std::unordered_multimap<int, float> m1{{1, 1.1f}, {1, 1.2f}, {3, 1.3f}};
std::unordered_multimap<int, float> m2{{1, 1.1f}, {1, 1.2f}};
std::swap(m1, m2);
std::cout << "m1 size = " << m1.size() << std::endl;
std::cout << "m2 size = " << m2.size() << std::endl;

输出结果:

m1 size = 2
m2 size = 3

erase_if

删除满足条件的元素。代码示例:

std::unordered_multimap<int, float> m{{1, 1.1f}, {1, 1.2f}, {3, 1.3f}};
std::cout << "m size = " << m.size() << std::endl;
std::erase_if(m,[](const std::pair<int, float>& pair){return pair.second > 1.15;});
std::cout << "m size = " << m.size() << std::endl;

输出结果:

m size = 3
m size = 1

这篇关于容器库(13)-std::unordered_multimap的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/751257

相关文章

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

K8S(Kubernetes)开源的容器编排平台安装步骤详解

K8S(Kubernetes)是一个开源的容器编排平台,用于自动化部署、扩展和管理容器化应用程序。以下是K8S容器编排平台的安装步骤、使用方式及特点的概述: 安装步骤: 安装Docker:K8S需要基于Docker来运行容器化应用程序。首先要在所有节点上安装Docker引擎。 安装Kubernetes Master:在集群中选择一台主机作为Master节点,安装K8S的控制平面组件,如AP

Spring框架5 - 容器的扩展功能 (ApplicationContext)

private static ApplicationContext applicationContext;static {applicationContext = new ClassPathXmlApplicationContext("bean.xml");} BeanFactory的功能扩展类ApplicationContext进行深度的分析。ApplicationConext与 BeanF

容器编排平台Kubernetes简介

目录 什么是K8s 为什么需要K8s 什么是容器(Contianer) K8s能做什么? K8s的架构原理  控制平面(Control plane)         kube-apiserver         etcd         kube-scheduler         kube-controller-manager         cloud-controlle

13 transition数组的动画使用

划重点 动画:transitiontransition-group :数组动画数组的 添加 / 删除 豆腐粉丝汤 清淡又健康 <!DOCTYPE html><html lang="en"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><me

【CTF Web】BUUCTF Upload-Labs-Linux Pass-13 Writeup(文件上传+PHP+文件包含漏洞+PNG图片马)

Upload-Labs-Linux 1 点击部署靶机。 简介 upload-labs是一个使用php语言编写的,专门收集渗透测试和CTF中遇到的各种上传漏洞的靶场。旨在帮助大家对上传漏洞有一个全面的了解。目前一共20关,每一关都包含着不同上传方式。 注意 1.每一关没有固定的通关方法,大家不要自限思维! 2.本项目提供的writeup只是起一个参考作用,希望大家可以分享出自己的通关思路

Chapter 13 普通组件的注册使用

欢迎大家订阅【Vue2+Vue3】入门到实践 专栏,开启你的 Vue 学习之旅! 文章目录 前言一、组件创建二、局部注册三、全局注册 前言 在 Vue.js 中,组件是构建应用程序的基本单元。本章详细讲解了注册和使用 Vue 的普通组件的两种方式:局部注册和全局注册。 本篇文章参考黑马程序员 一、组件创建 ①定义 Vue 组件是一种具有特定功能的 Vue 实

C++ STL关联容器Set与集合论入门

1. 简介 Set(集合)属于关联式容器,也是STL中最实用的容器,关联式容器依据特定的排序准则,自动为其元素排序。Set集合的底层使用一颗红黑树,其属于一种非线性的数据结构,每一次插入数据都会自动进行排序,注意,不是需要排序时再排序,而是每一次插入数据的时候其都会自动进行排序。因此,Set中的元素总是顺序的。 Set的性质有:数据自动进行排序且数据唯一,是一种集合元素,允许进行数学上的集合相

VMware Fusion Pro 13 Mac版虚拟机 安装Win11系统教程

Mac分享吧 文章目录 Win11安装完成,软件打开效果一、VMware安装Windows11虚拟机1️⃣:准备镜像2️⃣:创建虚拟机3️⃣:虚拟机设置4️⃣:安装虚拟机5️⃣:解决连不上网问题 安装完成!!! Win11安装完成,软件打开效果 一、VMware安装Windows11虚拟机 首先确保自己的mac开启了网络共享。不然虚拟机连不上👀的 1️⃣:准备镜像

华为 HCIP-Datacom H12-821 题库 (13)

有需要题库的可以看主页置顶 1.可以携带外部路由的 tag 标签信息的是以下哪一类 LSA? A、4 类 LSA B、5 类 LSA  C、3 类 LSA  D、2 类 LSA 答案:B 解析: 暂无解析 2..两台路由器直连,并设定网络类型为 p2p 建立OSPF 邻居。那么两台路由器传输 OSPF 报文的目的 IP 地址是以下哪一项? A、使用组播地址 224.0.0.6 B