容器库(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+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元
阅读更多...
C++中std::distance使用方法示例

C++中std::distance使用方法示例

《C++中std::distance使用方法示例》std::distance是C++标准库中的一个函数,用于计算两个迭代器之间的距离,本文主要介绍了C++中std::distance使用方法示例,具... 目录语法使用方式解释示例输出：其他说明：总结std::distance&n编程bsp;是 C++ 标准
阅读更多...
如何将Tomcat容器替换为Jetty容器

如何将Tomcat容器替换为Jetty容器

《如何将Tomcat容器替换为Jetty容器》：本文主要介绍如何将Tomcat容器替换为Jetty容器问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat容器替换为Jetty容器修改Maven依赖配置文件调整（可选）重新构建和运行总结Tomcat容器替
阅读更多...
C++从序列容器中删除元素的四种方法

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque
阅读更多...
C++常见容器获取头元素的方法大全

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素（即第一个元素）是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa
阅读更多...
Python容器类型之列表/字典/元组/集合方式

Python容器类型之列表/字典/元组/集合方式

《Python容器类型之列表/字典/元组/集合方式》：本文主要介绍Python容器类型之列表/字典/元组/集合方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 列表（List） - 有序可变序列1.1 基本特性1.2 核心操作1.3 应用场景2. 字典（D
阅读更多...
Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
c++中std::placeholders的使用方法

c++中std::placeholders的使用方法

《c++中std::placeholders的使用方法》std::placeholders是C++标准库中的一个工具,用于在函数对象绑定时创建占位符,本文就来详细的介绍一下,具有一定的参考价值,感兴... 目录1. 基本概念2. 使用场景3. 示例示例 1：部分参数绑定示例 2：参数重排序4. 注意事项5.
阅读更多...
Spring核心思想之浅谈IoC容器与依赖倒置(DI)

Spring核心思想之浅谈IoC容器与依赖倒置(DI)

《Spring核心思想之浅谈IoC容器与依赖倒置(DI)》文章介绍了Spring的IoC和DI机制,以及MyBatis的动态代理,通过注解和反射,Spring能够自动管理对象的创建和依赖注入,而MyB... 目录一、控制反转 IoC二、依赖倒置 DI1. 详细概念2. Spring 中 DI 的实现原理三、
阅读更多...
C++11的函数包装器std::function使用示例

C++11的函数包装器std::function使用示例

《C++11的函数包装器std::function使用示例》C++11引入的std::function是最常用的函数包装器,它可以存储任何可调用对象并提供统一的调用接口,以下是关于函数包装器的详细讲解... 目录一、std::function 的基本用法1. 基本语法二、如何使用 std::function
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2