在C++中使用unordered_map equal_range
unordered_map::equal_range()是C ++ STL中的内置函数,用于返回包括与k相等的键的所有元素的范围的边界。 unordered_map容器是一个唯一键的容器,该范围最多包括一个元素。该范围由两个迭代器定义,
- 第一个指向范围的第一个元素。
- 第二个指向范围之外的最后一个元素。
参数: 此函数接受单个参数key,该参数用于保存要比较的值。
返回值: 它返回一个包含定义所需范围的迭代器对的对。 其成员是pair :: first和pair :: second。 第一个是范围的下界的迭代器,第二个是其上界的迭代器。 范围中的元素是这两个迭代器之间的元素,包括第一个pair,但不是第二个。
下面的程序说明了C ++ STL中的unordered_map :: equal_range()函数:
示例1:
// C++ program to implement
// unordered_map::equal_range() function
#include <iostream>
#include <unordered_map>
using namespace std;
// main program
int main()
{
unordered_map <int, int> map = { { 1, 3 },
{ 1, 2 },
{ 3, 1 },
{ 2, 3 } };
for (int j = 1; j <= 3; j++) {
auto range = map.equal_range(j);
//'auto' is a keyword
for (auto i = range.first; i != range.second; i++) {
// iterates first to last
cout << "first : " << i->first;
cout << "\nsecond : " << i->second << endl
<< endl;
}
}
}
first : 1
second : 3
first : 2
second : 3
first : 3
second : 1
程序2:
// C++ program to search 'unordered map' container
#include <iostream>
#include <unordered_map>
using namespace std;
// Rename 'unordered_map<int, char>' as 'gfg'
typedef unordered_map<char, char> gfg;
int main()
{
// 'g' is object
gfg g;
// Container values
// Contents are look like [a, b] [c, d] [e, f]
g.insert(gfg::value_type('a', 'b'));
g.insert(gfg::value_type('b', 'd'));
g.insert(gfg::value_type('e', 'f'));
// Look into the syntax part above
// here 'f' is key
pair<gfg::iterator, gfg::iterator> p1 = g.equal_range('f');
// 'f' is not exits, so no output for 'f'
cout << "search for 'f' :";
for (; p1.first != p1.second; ++p1.first) {
cout << p1.first->first << ", " << p1.first->second << endl;
}
// Successful search
// Here 'a' is key
p1 = g.equal_range('a');
// 'a' is exits, so it searched successfully
cout << "\nsearch for 'a' : [";
for (; p1.first != p1.second; ++p1.first) {
cout << p1.first->first << ", " << p1.first->second << "]";
}
return 0;
}
search for 'f' :
search for 'a' : [a, b]
复杂度:
- 平均情况: 与键k的元素数量成线性关系,这是稳定的。
- 最坏情况: 与容器的大小成线性关系。