源码网站程序,wordpress 主页 插件,凡科做网站行吗,公司网站建设如何做账unordered_multiset是以key为元素无序的关联容器#xff0c;搜索、移除和插入操作是平均常数的时间复杂度。unordered_multiset在内部没有按任何顺序排列#xff0c;而是放在桶当中的#xff0c;放进哪个桶是通过计算key的hash值来决定的。和unordered_set不同的是#xff…unordered_multiset是以key为元素无序的关联容器搜索、移除和插入操作是平均常数的时间复杂度。unordered_multiset在内部没有按任何顺序排列而是放在桶当中的放进哪个桶是通过计算key的hash值来决定的。和unordered_set不同的是unordered_multiset中的key值可以重复。
templateclass Key,class Hash std::hashKey,class KeyEqual std::equal_toKey,class Allocator std::allocatorKeyclass unordered_multiset;
本文章的代码库
https://gitee.com/gamestorm577/CppStd
成员函数
构造、析构和赋值
构造函数
可以构造一个空的unordered_multiset也可以用迭代器、另一个unordered_multiset或者元素列表来构造一个unordered_multiset。构造的时候还可以指定最小桶数、hash函数、比较函数或者分配器。代码示例
std::vectorint tmp{1, 1, 2, 3};std::unordered_multisetint s1;
std::unordered_multisetint s2(tmp.begin(), tmp.end());
std::unordered_multisetint s3(s2);
std::unordered_multisetint s4{1, 2, 3};std::cout s1 size s1.size() std::endl;
std::cout s2 size s2.size() std::endl;
std::cout s3 size s3.size() std::endl;
std::cout s4 size s4.size() std::endl;
输出结果
s1 size 0
s2 size 4
s3 size 4
s4 size 3
对于自定义的类型需要定义hash函数以及比较函数。代码示例
struct MyStruct
{int Num1;double Num2;
};struct MyHash
{std::size_t operator()(const MyStruct val) const{return std::hashint()(val.Num1) std::hashdouble()(val.Num2);}
};struct MyEqual
{bool operator()(const MyStruct lhs, const MyStruct rhs) const{return true;}
};std::unordered_multisetMyStruct, MyHash, MyEqual s;
析构函数
销毁容器时会调用各元素的析构函数。代码示例
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::hashint()(val.Num);}
};struct MyEqual
{bool operator()(const MyStruct lhs, const MyStruct rhs) const{return lhs.Num rhs.Num;}
};std::unordered_multisetMyStruct, MyHash, MyEqual s{1, 1, 2, 3};
std::cout end std::endl;
输出结果
destruct, Num 3
destruct, Num 2
destruct, Num 1
destruct, Num 1
end
destruct, Num 3
destruct, Num 2
destruct, Num 1
destruct, Num 1
赋值函数
可以用另一个unordered_multiset或者元素列表给unordered_multiset赋值。代码示例
std::unordered_multisetint tmp{1, 1, 2};
std::unordered_multisetint s1;
std::unordered_multisetint s2;
s1 tmp;
s2 {1, 1, 2, 3};
std::cout s1 size s1.size() std::endl;
std::cout s2 size s2.size() std::endl;
输出结果
s1 size 3
s2 size 4
迭代器
接口begin、cbegin指向unordered_multiset起始的迭代器end、cend指向末尾的迭代器。无论什么迭代器都不能修改元素的值。代码示例
std::unordered_multisetint s{1, 1, 2, 3};
for (auto iter s.begin(); iter ! s.end(); iter)
{std::cout num *iter std::endl;
}
输出结果
num 3
num 2
num 1
num 1
容量
empty
检查unordered_multiset是否为空。代码示例
std::unordered_multisetint s1{1, 1, 2};
std::unordered_multisetint s2;
std::cout std::boolalpha;
std::cout s1 empty: s1.empty() std::endl;
std::cout s2 empty: s2.empty() std::endl;
输出结果
s1 empty: false
s2 empty: true
size
获取unordered_multiset的元素个数。代码示例
std::unordered_multisetint s1{1, 1, 2};
std::unordered_multisetint s2;
std::cout s1 size: s1.size() std::endl;
std::cout s2 size: s2.size() std::endl;
输出结果
s1 size: 3
s2 size: 0
max_size
返回可以容纳的最大元素个数。代码示例
std::unordered_multisetchar s1;
std::unordered_multisetstd::string s2;
std::cout s1 max size s1.max_size() std::endl;
std::cout s2 max size s2.max_size() std::endl;
输出结果
s1 max size 768614336404564650
s2 max size 461168601842738790
修改器
clear
清除所有的元素。代码示例
std::unordered_multisetint s{1, 1, 2, 3};
std::cout s size s.size() std::endl;
s.clear();
std::cout s size s.size() std::endl;
输出结果
s size 4
s size 0
insert
插入元素参数可以是元素、迭代器或者元素节点。代码示例
std::unordered_multisetint s;s.insert(1);
s.insert(1);
std::cout s size s.size() std::endl;std::vectorint tmp{2, 2, 3};
s.insert(tmp.begin(), tmp.end());
std::cout s size s.size() std::endl;
输出结果
s size 2
s size 5
emplace
构造一个元素到容器中。代码示例
struct MyStruct
{MyStruct(int num1, int num2): Num1(num1), Num2(num2){std::cout construct: num1 num2 std::endl;}int Num1 0;int Num2 0;
};struct MyHash
{std::size_t operator()(const MyStruct val) const{return std::hashint()(val.Num1) std::hashint()(val.Num2);}
};struct MyEqual
{bool operator()(const MyStruct lhs, const MyStruct rhs) const{return (lhs.Num1 rhs.Num1) (lhs.Num2 rhs.Num2);}
};std::unordered_multisetMyStruct, MyHash, MyEqual s;
s.emplace(1, 1);
s.emplace(1, 2);
s.emplace(1, 2);
输出结果
construct: 1 1
construct: 1 2
construct: 1 2
emplace_hint
向容器中尽可能靠近hint之前的位置插入新元素
template class... Args
iterator emplace_hint(const_iterator hint, Args... args);
不同的hint会导致插入元素的效率不同。代码示例
auto timer [](std::functionstd::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::durationdouble, std::milli time end - start;std::cout tag , size: size , use time: time.count() std::endl;
};const int count 3000000;auto unordered_multiset_emplace []() - std::size_t
{std::unordered_multisetint s;for (int i 0; i count; i){s.emplace(i);}return s.size();
};auto unordered_multiset_emplace_hint1 []() - std::size_t
{std::unordered_setint s;auto iter s.begin();for (int i 0; i count; i){s.emplace_hint(iter, i);iter s.end();}return s.size();
};auto unordered_multiset_emplace_hint2 []() - std::size_t
{std::unordered_setint s;auto iter s.begin();for (int i 0; i count; i){s.emplace_hint(iter, i);iter s.begin();}return s.size();
};auto unordered_multiset_emplace_hint3 []() - std::size_t
{std::unordered_setint s;auto iter s.begin();for (int i 0; i count; i){iter s.emplace_hint(iter, i);}return s.size();
};timer(unordered_multiset_emplace, unordered_multiset_emplace);
timer(unordered_multiset_emplace_hint1, unordered_multiset_emplace_hint1);
timer(unordered_multiset_emplace_hint2, unordered_multiset_emplace_hint2);
timer(unordered_multiset_emplace_hint3, unordered_multiset_emplace_hint3);
输出结果
unordered_multiset_emplace, size: 3000000, use time: 498.258
unordered_multiset_emplace_hint1, size: 3000000, use time: 511.267
unordered_multiset_emplace_hint2, size: 3000000, use time: 499.438
unordered_multiset_emplace_hint3, size: 3000000, use time: 474.257
erase
移除指定位置的元素或者移除指定的值。代码示例
std::unordered_multisetint s1{1, 1, 2, 2, 3, 3, 3, 4, 4};
std::cout s1 size s1.size() std::endl;
s1.erase(s1.begin());
std::cout s1 size s1.size() std::endl;
s1.erase(s1.begin(), std::next(s1.begin(), 3));
std::cout s1 size s1.size() std::endl;std::unordered_multisetint s2{1, 1, 3, 3, 3};
std::cout s2 size s2.size() std::endl;
s2.erase(3);
std::cout s2 size s2.size() std::endl;
输出结果
s1 size 9
s1 size 8
s1 size 5
s2 size 5
s2 size 2
swap
和另一个容器交换元素内容。代码示例
std::unordered_multisetint s1{1, 1, 2, 2};
std::unordered_multisetint s2{1, 1};
s1.swap(s2);
std::cout s1 size s1.size() std::endl;
std::cout s2 size s2.size() std::endl;
输出结果
s1 size 2
s2 size 4
extract
提取容器中的某个元素节点提取后容器不再拥有该元素。代码示例
std::unordered_multisetint s{1, 1, 2, 3, 4};
std::cout s size s.size() std::endl;
auto node1 s.extract(1);
std::cout s size s.size() std::endl;
auto node2 s.extract(s.begin());
std::cout s size s.size() , node2 node2.value() std::endl;
s.insert(std::move(node2));
std::cout s size s.size() std::endl;
输出结果
s size 5
s size 4
s size 3, node2 4
s size 4
merge
合并另一个unordered_set或者unordered_multiset中的元素。代码示例
std::unordered_multisetint s1{1, 1, 2};
std::unordered_multisetint s2{1, 2};
s1.merge(s2);
std::cout s1 size s1.size() std::endl;
std::cout s2 size s2.size() std::endl;
输出结果
s1 size 5
s2 size 0
查找
count
获取给定key值的元素数量。代码示例
std::unordered_multisetint s{1, 1, 2, 3};
std::cout elment 1 count s.count(1) std::endl;
std::cout elment 2 count s.count(2) std::endl;
std::cout elment 4 count s.count(4) std::endl;
输出结果
elment 1 count 2
elment 2 count 1
elment 4 count 0
find
获取指定key值的元素的迭代器。如果有多个元素匹配key值那么返回任意一个。代码示例
std::unordered_multisetint s{1, 1, 2, 3};
auto iter1 s.find(1);
auto iter2 s.find(4);
std::cout std::boolalpha;
std::cout elment has 1: (iter1 s.end()) std::endl;
std::cout elment has 4: (iter2 s.end()) std::endl;
输出结果
elment has 1: false
elment has 4: true
contains
检查是否包含特定的元素。代码示例
std::unordered_multisetint s{1, 1, 2, 3};
std::cout std::boolalpha;
std::cout contain 1: s.contains(1) std::endl;
std::cout contain 4: s.contains(4) std::endl;
输出结果
contain 1: true
contain 4: false
equal_range
获取容器中等于给定key值的元素范围。返回第一个迭代器指向范围的首元素第二个迭代器指向范围的最后一个元素后面的位置。代码示例
std::unordered_multisetint s{1, 1, 2, 3, 3, 4};
for (auto item : s)
{std::cout item ;
}
std::cout std::endl;
auto [iter1, iter2] s.equal_range(3);
std::cout iter1 *iter1 std::endl;
std::cout iter2 *iter2 std::endl;
桶接口
bucket_count
返回unordered_multiset的桶数量。代码示例
std::unordered_multisetint s{1, 1, 2, 3, 3, 3, 3};
std::cout bucket count s.bucket_count() std::endl;
输出结果
bucket count 11
max_bucket_count
返回unordered_multiset可以容纳的最大桶数量。代码示例
std::unordered_multisetint s1;
std::unordered_multisetstd::string s2;
std::cout s1 max bucket count: s1.max_bucket_count() std::endl;
std::cout s2 max bucket count: s2.max_bucket_count() std::endl;
输出结果
s1 max bucket count: 768614336404564650
s2 max bucket count: 461168601842738790
bucket_size
范围特定桶中的元素数量。代码示例
std::unordered_multisetint s{1, 1, 1, 2, 2, 2, 3, 3};
for (int i 0; i s.bucket_count(); i)
{std::cout bucket i has item num s.bucket_size(i) std::endl;
}
输出结果
bucket 0 has item num 0
bucket 1 has item num 3
bucket 2 has item num 3
bucket 3 has item num 2
bucket 4 has item num 0
bucket 5 has item num 0
bucket 6 has item num 0
bucket 7 has item num 0
bucket 8 has item num 0
bucket 9 has item num 0
bucket 10 has item num 0
bucket
返回给定key值的元素所在桶的索引。代码示例
std::unordered_multisetint s{11, 11, 13, 13, 13, 14, 14, 15};
auto n s.bucket(13);
std::cout item 13 is in bucket n std::endl;
输出结果
item 13 is in bucket 2
begin、cbegin、end、cend
begin和cbegin返回索引为n的桶中的首个元素的迭代器。end和cend返回索引为n的桶中的末尾迭代器。代码示例
std::unordered_multisetint s{11, 11, 13, 13, 13, 14, 14, 15};
auto cnt s.bucket(13);
auto iter_begin s.begin(cnt);
auto iter_end s.end(cnt);
for (auto iter iter_begin; iter ! iter_end; iter)
{std::cout num *iter std::endl;
}
输出结果
num 13
num 13
num 13
哈希策略
load_factor
返回每个桶的平均元素数量。代码示例
std::unordered_multisetint s{1, 1, 2, 3};
float num s.load_factor();
std::cout load factor is: num std::endl;
输出结果
load factor is: 0.8
max_load_factor
没有参数的情况下返回每个桶的最大平均元素数。参数为float类型时设置每个桶的最大平均元素数如果超出了该数量容器就会自己增加桶数。代码示例
int n_count 200;std::unordered_multisetint s1;
s1.max_load_factor(1);
for (int i 0; i n_count; i)
{s1.insert(i);
}
std::cout s1 max load factor is: s1.max_load_factor() std::endl;
std::cout s1 bucket count: s1.bucket_count() std::endl;std::unordered_multisetint s2;
s2.max_load_factor(20);
for (int i 0; i n_count; i)
{s2.insert(i);
}
std::cout s2 max load factor is: s2.max_load_factor() std::endl;
std::cout s2 bucket count: s2.bucket_count() std::endl;
输出结果
s1 max load factor is: 1
s1 bucket count: 397
s2 max load factor is: 20
s2 bucket count: 11
rehash
设置桶的最小数量并重新散列容器。代码示例
std::unordered_multisetint s;
for (int i 0; i 200; i)
{s.insert(i);
}
std::cout bucket cnt: s.bucket_count() std::endl;s.rehash(s.bucket_count() / 2);
std::cout bucket cnt: s.bucket_count() std::endl;
s.rehash(s.bucket_count() * 4);
std::cout bucket cnt: s.bucket_count() std::endl;
输出结果
bucket cnt: 397
bucket cnt: 211
bucket cnt: 853
reserve
设置桶的最小元素个数并重新散列容器。重新散列后的容器的平均桶数不能超过设定的值。代码示例
std::unordered_multisetint s;
for (int i 0; i 200; i)
{s.insert(i);
}
std::cout bucket cnt: s.load_factor() std::endl;s.reserve(5);
std::cout bucket cnt: s.load_factor() std::endl;
输出结果
bucket cnt: 0.503778
bucket cnt: 0.947867
观察器
hash_function
返回计算hash值的函数。代码示例
std::unordered_multisetstd::string s;
auto hash_func s.hash_function();
std::cout hash is: hash_func(hello world) std::endl;
输出结果
hash is: 12386028635079221413
key_eq
返回用于比较key相等性的函数。代码示例
std::unordered_multisetint s;
auto key_eq_func s.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
非成员函数
比较运算符
比较两个unordered_multiset是否相等。代码示例
std::unordered_multisetint s1{1, 1, 2};
std::unordered_multisetint s2{1, 2};
std::cout std::boolalpha;
std::cout s1 s2: (s1 s2) std::endl;
std::cout s1 ! s2: (s1 ! s2) std::endl;
输出结果
s1 s2: false
s1 ! s2: true
swap
交换两个容器的元素内容。代码示例
std::unordered_multisetint s1{1, 1, 2};
std::unordered_multisetint s2{1, 2};
std::swap(s1, s2);
std::cout s1 size s1.size() std::endl;
std::cout s2 size s2.size() std::endl;
输出结果
s1 size 2
s2 size 3
enable_if
删除满足条件的元素。代码示例
std::unordered_multisetint s {1, 1, 2, 3, 3};
std::cout s size s.size() std::endl;
std::erase_if(s,[](int a){return a 2;});
std::cout s size s.size() std::endl;
输出结果
s size 5
s size 3
