容器库(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。

相关文章

详解C++ 存储二进制数据容器的几种方法

详解C++ 存储二进制数据容器的几种方法

《详解C++存储二进制数据容器的几种方法》本文主要介绍了详解C++存储二进制数据容器,包括std::vector、std::array、std::string、std::bitset和std::ve... 目录1.std::vector<uint8_t>（最常用）特点：适用场景：示例：2.std::arra
阅读更多...
python项目打包成docker容器镜像的两种方法实现

python项目打包成docker容器镜像的两种方法实现

《python项目打包成docker容器镜像的两种方法实现》本文介绍两种将Python项目打包为Docker镜像的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要... 目录简单版：（一次成功，后续下载对应的软件依赖）第一步：肯定是构建dockerfile，如下：第二步
阅读更多...
C++中unordered_set哈希集合的实现

C++中unordered_set哈希集合的实现

《C++中unordered_set哈希集合的实现》std::unordered_set是C++标准库中的无序关联容器,基于哈希表实现,具有元素唯一性和无序性特点,本文就来详细的介绍一下unorder... 目录一、概述二、头文件与命名空间三、常用方法与示例1. 构造与析构2. 迭代器与遍历3. 容量相关4
阅读更多...
Java JUC并发集合详解之线程安全容器完全攻略

Java JUC并发集合详解之线程安全容器完全攻略

《JavaJUC并发集合详解之线程安全容器完全攻略》Java通过java.util.concurrent（JUC）包提供了一整套线程安全的并发容器,它们不仅是简单的同步包装,更是基于精妙并发算法构建... 目录一、为什么需要JUC并发集合？二、核心并发集合分类与详解三、选型指南：如何选择合适的并发容器？在多
阅读更多...
python语言中的常用容器(集合)示例详解

python语言中的常用容器(集合)示例详解

《python语言中的常用容器(集合)示例详解》Python集合是一种无序且不重复的数据容器,它可以存储任意类型的对象,包括数字、字符串、元组等,下面：本文主要介绍python语言中常用容器(集合... 目录1.核心内置容器1. 列表2. 元组3. 集合4. 冻结集合5. 字典2.collections模块
阅读更多...
Spring Boot中获取IOC容器的多种方式

Spring Boot中获取IOC容器的多种方式

《SpringBoot中获取IOC容器的多种方式》本文主要介绍了SpringBoot中获取IOC容器的多种方式,包括直接注入、实现ApplicationContextAware接口、通过Spring... 目录1. 直接注入ApplicationContext2. 实现ApplicationContextA
阅读更多...
linux配置podman阿里云容器镜像加速器详解

linux配置podman阿里云容器镜像加速器详解

《linux配置podman阿里云容器镜像加速器详解》本文指导如何配置Podman使用阿里云容器镜像加速器：登录阿里云获取专属加速地址,修改Podman配置文件并移除https://前缀,最后拉取镜像... 目录1.下载podman2.获取阿里云个人容器镜像加速器地址3.更改podman配置文件4.使用po
阅读更多...
k8s容器放开锁内存限制问题

k8s容器放开锁内存限制问题

《k8s容器放开锁内存限制问题》nccl-test容器运行mpirun时因NCCL_BUFFSIZE过大导致OOM,需通过修改docker服务配置文件,将LimitMEMLOCK设为infinity并... 目录问题问题确认放开容器max locked memory限制总结参考：https://Access
阅读更多...
通过Docker容器部署Python环境的全流程

通过Docker容器部署Python环境的全流程

《通过Docker容器部署Python环境的全流程》在现代化开发流程中,Docker因其轻量化、环境隔离和跨平台一致性的特性,已成为部署Python应用的标准工具,本文将详细演示如何通过Docker容... 目录引言一、docker与python的协同优势二、核心步骤详解三、进阶配置技巧四、生产环境最佳实践
阅读更多...
Debian 13升级后网络转发等功能异常怎么办? 并非错误而是管理机制变更

Debian 13升级后网络转发等功能异常怎么办? 并非错误而是管理机制变更

《Debian13升级后网络转发等功能异常怎么办?并非错误而是管理机制变更》很多朋友反馈，更新到Debian13后网络转发等功能异常，这并非BUG而是Debian13Trixie调整... 日前 Debian 13 Trixie 发布后已经有众多网友升级到新版本，只不过升级后发现某些功能存在异常，例如网络转
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2