网站建设管理流程,二维码生成软件,删除wordpress缓存文件在哪,淘宝店铺如何推广阅读导航 前言一、unordered系列容器二、unordered_map1. unordered_map简介⭕函数特点 2. unordered_map接口- 构造函数- unordered_map的容量- unordered_map的迭代器- unordered_map的元素访问- unordered_map的修改操作- unordered_map的桶操作 三、unordered_set1. unorde… 阅读导航 前言一、unordered系列容器二、unordered_map1. unordered_map简介⭕函数特点 2. unordered_map接口- 构造函数- unordered_map的容量- unordered_map的迭代器- unordered_map的元素访问- unordered_map的修改操作- unordered_map的桶操作 三、unordered_set1. unordered_srt简介⭕函数特点 2. unordered_set接口 温馨提示 前言
欢迎各位大佬们的关顾本文将介绍unordered系列容器以及其中的两个重要成员unordered_map和unordered_set。unordered_map是一种无序的关联容器它使用哈希表来存储键值对并提供高效的插入、查找和删除操作。在本文中我们将首先介绍unordered_map的基本概念和特点然后详细讲解其接口和用法。接下来我们将介绍unordered_set它是一种无序的集合容器同样基于哈希表实现。我们将对unordered_set进行简要介绍并深入探讨其接口和用法。通过学习本文您将对unordered系列容器有更加清晰的理解并能够灵活运用它们解决实际问题。下面话不多说坐稳扶好咱们要开车了
一、unordered系列容器
在C98中STL提供了一系列底层为红黑树结构的关联式容器包括set、multiset、map和multimap。这些容器在查询操作时的时间复杂度为 O ( l o g N ) O(logN) O(logN)其中N是容器中元素的数量。
为了提高查询效率C11引入了unordered_map和unordered_set这两个底层基于哈希表的关联式容器。与红黑树结构的关联式容器相比unordered系列容器在平均情况下具有更高的查询效率时间复杂度为常数级别 O ( 1 ) O(1) O(1)。当哈希函数设计得好且没有太多的冲突时它们可以在插入、查找和删除等操作上表现出很好的性能。
unordered_map是一种键值对存储的容器每个键唯一对应一个值而unordered_set是一种存储唯一元素的容器。它们的使用方式与红黑树结构的关联式容器类似提供了insert、erase、find等方法来操作元素。
注意unordered_map和unordered_set的元素顺序是根据哈希函数计算的哈希值来确定的因此它们无法保证元素的顺序稳定。如果需要有序的容器仍然可以使用红黑树结构的关联式容器。
二、unordered_map
| | unordered_map在线文档说明 |
1. unordered_map简介
unordered_map是C标准库中的一个关联式容器它是基于哈希表实现的。unordered_map提供了一种存储键值对的方式每个键唯一对应一个值。它被设计为在平均情况下具有常数时间复杂度的插入、查找和删除操作。
unordered_map与map的用法类似但其内部结构不同。unordered_map使用哈希函数将键映射到桶bucket中并在桶内使用链表或其他数据结构解决冲突。通过哈希函数和桶的结构可以快速定位键对应的值。
⭕函数特点 常数时间复杂度平均情况下unordered_map的插入、查找和删除操作都具有常数时间复杂度。这是因为哈希表充分利用了哈希函数的散列性质快速定位元素。 无序存储与map不同unordered_map不会按照键的顺序进行存储而是根据哈希函数计算得到的哈希值进行存储。因此遍历unordered_map的结果是无序的。 自定义哈希函数unordered_map支持自定义哈希函数可以根据键的类型实现一个符合需求的哈希函数来提高查询效率。如果不提供自定义哈希函数会使用默认的哈希函数。 冲突处理由于哈希函数的限制可能会出现多个元素映射到同一个桶的情况这就是冲突。unordered_map使用链表或其他数据结构来解决冲突保证键值对的正确存储和查找。 支持各种数据类型unordered_map可以存储各种数据类型的键值对包括内置类型和自定义类型。
注意使用unordered_map时需要包含头文件unordered_map并使用std命名空间或者使用using语句简化操作。
2. unordered_map接口
- 构造函数 默认构造函数 unordered_mapKey, T myMap;使用默认构造函数创建一个空的unordered_map对象。 列表初始化构造函数 unordered_mapKey, T myMap {{key1, value1}, {key2, value2}, ...};使用初始化列表创建unordered_map对象并初始化其中的键值对。 区间构造函数 templateclass InputIt
unordered_map(InputIt first, InputIt last);从指定范围内的元素创建unordered_map对象。范围由迭代器first和last指定可以是数组、容器或其他实现了前向迭代器的数据结构。 拷贝构造函数 unordered_map(const unordered_map other);使用另一个unordered_map对象进行拷贝构造创建一个与原unordered_map相同的副本。 移动构造函数 unordered_map(unordered_map other) noexcept;使用另一个unordered_map对象进行移动构造创建一个新的unordered_map对象并从原对象中窃取资源。
构造函数功能介绍unordered_map()默认构造函数创建一个空的unordered_map对象。unordered_map(initializer_listpairconst Key, T)列表初始化构造函数使用初始化列表创建unordered_map对象并初始化其中的键值对。unordered_map(const unordered_map)拷贝构造函数创建一个与原unordered_map相同的副本。unordered_map(unordered_map) noexcept移动构造函数创建一个新的unordered_map对象并从原对象中窃取资源。unordered_map(size_type)构造函数创建具有指定桶数的unordered_map对象。unordered_map(size_type, const hasher, const key_equal)构造函数创建具有指定桶数、哈希函数和相等比较操作符的unordered_map对象。template unordered_map(InputIt, InputIt)区间构造函数从指定范围内的元素创建unordered_map对象。
- unordered_map的容量
unordered_map的容量相关的成员函数主要包括
函数声明功能介绍unordered_map::size返回unordered_map中键值对的个数。unordered_map::empty判断unordered_map是否为空返回true或false。unordered_map::max_size返回unordered_map所能容纳的最大元素数量。
- unordered_map的迭代器
unordered_map提供了以下迭代器
迭代器类型功能介绍unordered_map::iterator用于遍历和修改unordered_map中的键值对可以通过解引用操作符*和箭头操作符-访问元素。unordered_map::const_iterator用于遍历unordered_map中的键值对但不允许修改元素值。
你可以使用以下成员函数来获取迭代器
函数声明功能介绍unordered_map::begin返回指向unordered_map起始位置的迭代器。unordered_map::end返回指向unordered_map末尾位置的迭代器。unordered_map::find返回指向键对应的元素的迭代器如果键不存在则返回尾部迭代器。
使用迭代器可以遍历unordered_map中的所有元素示例代码如下所示
#include iostream
#include unordered_mapint main() {std::unordered_mapint, std::string map {{1, one}, {2, two}, {3, three}};// 使用迭代器遍历unordered_map并打印键值对for (auto it map.begin(); it ! map.end(); it) {std::cout Key: it-first , Value: it-second std::endl;}// 使用find函数查找指定键的元素auto findIt map.find(2);if (findIt ! map.end()) {std::cout Key: findIt-first , Value: findIt-second std::endl;}return 0;
}输出结果
Key: 1, Value: one
Key: 2, Value: two
Key: 3, Value: three
Key: 2, Value: two通过迭代器我们可以依次访问unordered_map中的键值对并通过迭代器的解引用操作符 - 来访问元素的键和值。使用find函数可以查找指定键的元素并返回一个指向该元素的迭代器。
- unordered_map的元素访问 下标运算符 []使用键作为索引来访问和修改unordered_map中的元素。如果键存在则返回对应的值如果键不存在则将该键插入到unordered_map中并返回一个默认构造的值。 std::unordered_mapstd::string, int map {{apple, 1}, {banana, 2}, {orange, 3}};int value map[apple]; // 访问键apple对应的值
map[banana] 5; // 修改键banana对应的值
map[grape] 4; // 插入新键grape并对应一个值 使用成员函数 at()使用键作为参数来访问和修改unordered_map中的元素。如果键存在则返回对应的值如果键不存在则抛出std::out_of_range异常。 std::unordered_mapstd::string, int map {{apple, 1}, {banana, 2}, {orange, 3}};int value map.at(apple); // 访问键apple对应的值
map.at(banana) 5; // 修改键banana对应的值
map.at(grape) 4; // 抛出异常因为键grape不存在- unordered_map的修改操作
函数声明功能介绍insert向容器中插入键值对erase删除容器中的键值对void clear()清空容器中有效元素个数void swap(unordered_map)交换两个容器中的元素
- unordered_map的桶操作
函数声明功能介绍size_t bucket_count()const返回哈希桶中桶的总个数size_t bucket_size(size_t n)const返回n号桶中有效元素的总个数size_t bucket(const K key)返回元素key所在的桶号
三、unordered_set
| | unordered_set在线文档说明 |
1. unordered_srt简介
std::unordered_set 是 C STL 提供的一个哈希表实现的无序集合容器。与 std::set 不同std::unordered_set 中元素的顺序是不确定的它使用哈希函数来快速访问、插入和删除元素。哈希函数将元素的键转换为一个哈希值然后用该哈希值来映射到对应的桶中每个桶中存储一组键值相同的元素。当需要访问、插入或删除某个元素时首先根据哈希函数计算出该元素对应的桶的位置然后在该桶中查找该元素。
⭕函数特点
元素的顺序是不确定的不能保证元素的插入顺序就是元素的访问顺序。访问、插入和删除元素的平均时间复杂度是 O ( 1 ) O(1) O(1)。查找元素的时间复杂度取决于哈希函数的质量最坏情况下会退化为线性时间复杂度 O ( n ) O(n) O(n)。支持使用自定义类型作为元素需要提供哈希函数和相等比较函数。内部结构是一个哈希表具有一定的空间浪费和碰撞问题。
2. unordered_set接口
std::unordered_set 是 C STL 提供的一个哈希表实现的无序集合容器。它提供了一系列成员函数用于插入、删除、查找和遍历元素。下面是 std::unordered_set 常用的成员函数 insert(): 向 unordered_set 中插入元素。有多种重载形式可以接受单个元素、区间或者初始化列表作为参数。插入操作的平均时间复杂度是 O(1)。 std::unordered_setint set;set.insert(10); // 插入单个元素
set.insert({20, 30, 40}); // 插入初始化列表
set.insert(begin(vec), end(vec)); // 插入区间erase(): 从 unordered_set 中删除元素。有多种重载形式可以接受单个元素、区间或者迭代器作为参数。删除操作的平均时间复杂度是 O(1)。 std::unordered_setint set {10, 20, 30, 40};set.erase(20); // 删除单个元素
set.erase(begin(set), end(set)); // 删除整个区间
set.erase(set.find(30)); // 删除指定迭代器位置的元素find(): 查找元素返回一个迭代器指向该元素的位置如果元素不存在则返回 end()。查找操作的平均时间复杂度是 O(1)。 std::unordered_setint set {10, 20, 30, 40};auto it set.find(20); // 查找元素
if (it ! set.end()) {std::cout Found: *it std::endl;
} else {std::cout Not found std::endl;
}count(): 获取某个元素在 unordered_set 中出现的次数返回值为0或1。可以用于判断元素是否存在。 std::unordered_setint set {10, 20, 30, 40};if (set.count(20) 0) {std::cout Element 20 exists in the set std::endl;
} else {std::cout Element 20 does not exist in the set std::endl;
}size(): 获取 unordered_set 中当前存储的元素数量。 std::unordered_setint set {10, 20, 30, 40};std::cout Size of set: set.size() std::endl;empty(): 检查 unordered_set 是否为空如果为空返回 true否则返回 false。 std::unordered_setint set;if (set.empty()) {std::cout Set is empty std::endl;
} else {std::cout Set is not empty std::endl;
}clear(): 清空 unordered_set 中的所有元素。 std::unordered_setint set {10, 20, 30, 40};set.clear();注意std::unordered_set 并不提供按索引方式访问元素的功能因为 unordered_set 是无序的。 若要遍历 unordered_set 中的元素可以使用迭代器
std::unordered_setint set {10, 20, 30, 40};for (auto it set.begin(); it ! set.end(); it) {std::cout *it ;
}
std::cout std::endl;以上是 std::unordered_set 常用的几个成员函数。通过这些函数可以方便地进行元素的插入、删除、查找和遍历操作。更多的操作可见官方文档的描述。
温馨提示
感谢您对博主文章的关注与支持另外我计划在未来的更新中持续探讨与本文相关的内容会为您带来更多关于C以及编程技术问题的深入解析、应用案例和趣味玩法等。请继续关注博主的更新不要错过任何精彩内容
再次感谢您的支持和关注。期待与您建立更紧密的互动共同探索C、算法和编程的奥秘。祝您生活愉快排便顺畅
