C++容器—unordered_map
1. 简介
#include template <
class Key,// unordered_map::key_type
class T,// unordered_map::mapped_type
class Hash = std::hash,// unordered_map::hasher
class Pred = std::equal_to,// unordered_map::key_equal
class Alloc = std::allocator>// unordered_map::allocator_type
> class unordered_map;
unordered_map 具有如下性质：
- 唯一性：键是唯一的；
- 无序性：键值对是无序存储的，元素被存储在桶中，如果两个元素拥有相同哈希值的键，则它们会被存储于同一桶中；
- 具有常数时间复杂度（平均来说）的搜索、插入、删除操作。
方法1：显式提供相应的模板参数
#include
#include
#include struct Key
{
std::string first;
std::string second;
};
struct KeyHash
{
std::size_t operator()(const Key& k) const
{
return std::hash()(k.first) ^
(std::hash()(k.second) << 1);
}
};
struct KeyEqual
{
bool operator()(const Key& lhs, const Key& rhs) const
{
return lhs.first == rhs.first && lhs.second == rhs.second;
}
};
int main()
{
Key k1{ "John", "Doe" }, k2{ "Mary", "Sue" };
std::unordered_map m =
{
{ k1, "example"},
{ k2, "another"}
};
std::cout << m[k1] << '\n';
// example
} 方法2：显式特化 std::hash<> 模板
template
struct hash;
#include
#include
#include struct Foo
{
Foo(int val_) : val(val_) {}
int val;
// unordered_map::key_equal
bool operator==(const Foo& rhs) const
{
return val == rhs.val;
}
};
namespace std
{
template<>
struct hash
{
std::size_t operator()(const Foo& f) const
{
return std::hash{}(f.val);
}
};
}int main()
{
std::unordered_map m =
{
{ Foo(1), "One"}, { 2, "Two"}, { 3, "Three"}
};
std::cout << m[Foo(1)] << '\n';
// One
} 3. 容器大小
std::unordered_map m;
bool isEmpty = m.empty();
// Test whether container is empty
size_t n = m.size();
// Return container size
size_t limit = m.max_size();
// Return maximum size/*
Sets the number of buckets in the container (bucket_count)
to the most appropriate to contain at least 30 elements.
*/
m.reserve(30);
4. 访问元素
std::unordered_map m;
m["Bakery"] = "Barbara";
// 存在时更新值；不存在时插入键值对
std::string v = m["Bakery"];
// 存在时返回对应的值；不存在时插入键值对（使用值类型的默认构造函数来创建值）m.at("Hello") = "World";
// 存在时更新值；不存在时抛出 out_of_range 异常
std::string v = m.at("Hello");
// 存在时返回对应的值；不存在时抛出 out_of_range 异常5. 查找元素
std::unordered_map m =
{
{"mom", 5.4},
{"dad", 6.1},
{"bro", 5.9}
};
auto it = m.find("mom");
if (it == m.end())
{
std::cout << "not found";
}
else
{
std::cout << "key=" << it->first << ", value="https://www.it610.com/article/<< it->second;
}bool exists = m.contains("mom");
// 是否存在（C++20）6. 插入元素 emplace：使用给定的实参原地构造元素，可以避免不必要的拷贝。只有不存在相应的键才会插入。
struct Person
{
std::string m_name;
double m_salary;
Person() = default;
Person(const std::string& name, double salary)
: m_name(name), m_salary(salary)
{}
};
int main()
{
std::unordered_map m;
/*
返回值类型为 pair
其中，迭代器执行新插入的元素，或已存在的元素
bool 表示是否插入成功
*/
auto p = m.emplace(1, Person(std::string("Mike"), 12345.6));
if (p.second)
{
std::cout << "插入成功\n";
}
else
{
std::cout << "已存在，原值为：" << p.first->second.m_salary;
}
} insert：只有不存在相应的键才会插入。
std::unordered_map m;
/*
返回值类型为 pair
其中，迭代器执行新插入的元素，或已存在的元素
bool 表示是否插入成功
*/
auto p = m.insert({ "sugar", 0.8 });
if (p.second)
{
std::cout << "插入成功\n";
}
else
{
std::cout << "已存在，原值为：" << p.first->second;
} 7. 删除元素
std::unordered_map m;
m.erase("France");
// 删除指定键的元素，不存在时也没事auto it = m.find("France");
if (it != m.end())
{
m.erase(it);
// 删除指定位置的元素
}m.clear();
// 清空容器8. 遍历容器 遍历元素
std::unordered_map m
{
{ "Australia", "Canberra" },
{ "U.S.", "Washington" },
{ "France", "Paris" }
};
for (auto it = m.begin();
it != m.end();
it++)
{
if (it->first[0] == 'U')
{
std::cout << it->first << "->" << it->second << '\n';
}
}【C++容器—unordered_map】遍历桶
std::unordered_map m
{
{"house","maison"},
{"apple","pomme"},
{"tree","arbre"},
{"book","livre"},
{"door","porte"},
{"grapefruit","pamplemousse"}
};
size_t bucketCount = m.bucket_count();
std::cout << "bucket count: " << bucketCount << '\n';
for (size_t i = 0;
i < bucketCount;
i++)
{
std::cout << "bucket #" << i << " has " << m.bucket_size(i) << " elements.\n";
}
std::cout << '\n';
for (size_t i = 0;
i < bucketCount;
i++)
{
std::cout << "bucket #" << i << " contains: ";
for (auto it = m.begin(i);
it != m.end(i);
it++)
{
std::cout << "[" << it->first << ":" << it->second << "] ";
}
std::cout << '\n';
}bucket count: 8
bucket #0 has 1 elements.
bucket #1 has 1 elements.
bucket #2 has 1 elements.
bucket #3 has 1 elements.
bucket #4 has 0 elements.
bucket #5 has 1 elements.
bucket #6 has 0 elements.
bucket #7 has 1 elements.bucket #0 contains: [book:livre]
bucket #1 contains: [door:porte]
bucket #2 contains: [grapefruit:pamplemousse]
bucket #3 contains: [house:maison]
bucket #4 contains:
bucket #5 contains: [tree:arbre]
bucket #6 contains:
bucket #7 contains: [apple:pomme]推荐阅读
- 急于表达——往往欲速则不达
- 慢慢的美丽
- Docker应用:容器间通信与Mariadb数据库主从复制
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 2019-02-13——今天谈梦想（）
- 考研英语阅读终极解决方案——阅读理解如何巧拿高分
- Ⅴ爱阅读，亲子互动——打卡第178天
- 低头思故乡——只是因为睡不着
- 取名——兰
- 每日一话（49）——一位清华教授在朋友圈给大学生的9条建议