手机便宜网站建设,vs 网站开发教程,阿里云服务器租用,山东省住房与建设厅网站首页✨个人主页#xff1a; 熬夜学编程的小林
#x1f497;系列专栏#xff1a; 【C语言详解】 【数据结构详解】【C详解】
目录
1 unordered_set
1.1 unordered_set的接口说明
1.1.1 unordered_set的构造
1.1.2. unordered_set的容量
1.1.3. unordered_set的迭代器
1.1…✨个人主页 熬夜学编程的小林
系列专栏 【C语言详解】 【数据结构详解】【C详解】
目录
1 unordered_set
1.1 unordered_set的接口说明
1.1.1 unordered_set的构造
1.1.2. unordered_set的容量
1.1.3. unordered_set的迭代器
1.1.4. unordered_set的查询
1.1.5. unordered_set的修改操作
1.1.6. unordered_set的桶操作
2 unordered_map
1.2 unordered_map的接口说明
1.2.1. unordered_map的构造
1.2.2. unordered_map的容量
1.2.3. unordered_map的迭代器
1.2.4. unordered_map的元素访问
6. unordered_map的修改操作
7. unordered_map的桶操作 在C98中STL提供了底层为红黑树结构的一系列关联式容器在查询时效率可达到log2 N即最差情况下需要比较红黑树的高度次当树中的节点非常多时查询效率也不理想。最好的查询是进行很少的比较次数就能够将元素找到因此在C11中STL又提供了4个unordered系列的关联式容器这四个容器与红黑树结构的关联式容器使用方式基本类似只是其底层结构不同本文中只对unordered_map和unordered_set进行介绍。
1 unordered_set
1. unordered_set 是以不特定顺序存储唯一元素的容器并允许根据其值快速检索单个元素。2. 在unordered_set中元素的值同时是其键它唯一地标识它。键是不可变的因此unordered_set中的元素不能在容器中修改一次但是它们可以插入和删除。3. 在内部unordered_set中的元素不按任何特定顺序排序而是根据其哈希值组织到桶中以便直接通过其值快速访问各个元素平均平均时间复杂度恒定。4. unordered_set容器通过其键访问单个元素的速度比设置的容器更快尽管它们在通过其元素子集进行范围迭代时通常效率较低。5. 容器中的迭代器至少是正向迭代器。
1.1 unordered_set的接口说明
1.1.1 unordered_set的构造
代码演示
#includeunordered_set
int main()
{// 构造空对象unordered_setint s1;// 列表构造对象unordered_setint s2 { 1,3,4,9,2,7 };return 0;
} 测试结果 1.1.2. unordered_set的容量
函数声明功能介绍bool empty() const检测unordered_set是否为空size_t size() const获取unordered_set的有效元素个数 代码演示
#includeunordered_set
int main()
{unordered_setint s1 { 1,3,4,9,2,7 };cout empty() s1.empty() endl;cout size() s1.size() endl;return 0;
}
测试结果 1.1.3. unordered_set的迭代器
函数声明功能介绍begin返回unordered_set第一个元素的迭代器end返回unordered_set最后一个元素下一个位置的迭代器
代码演示
#includeunordered_set
int main()
{unordered_setint s1 { 1,3,4,9,2,7 };// 获取unordered_set第一个元素的迭代器unordered_setint::iterator it1 s1.begin();while (it1 ! s1.end()){cout *it1 ;it1;}cout endl;return 0;
}
测试结果 1.1.4. unordered_set的查询
函数声明功能介绍iterator find(const K key)返回key在哈希桶中的位置size_t count(const K key)返回哈希桶中key的个数
代码演示
#includeunordered_set
int main()
{unordered_setint s1 { 1,3,4,9,2,7,4 };// 查找数值3的位置并打印该位置的值auto pos s1.find(3);cout *pos endl;// 计算数值4的个数size_t countFour s1.count(4);cout countFour countFour endl;return 0;
}
测试结果 注意unordered_set中key是不能重复的因此count函数的返回值最大为1。 1.1.5. unordered_set的修改操作
函数声明功能介绍insert向容器中插入key值erase删除容器中的key值void clear()清空容器中有效元素个数void swap(unordered_set)交换两个容器中的元素
代码演示
#includeunordered_set
int main()
{unordered_setint s1;// 插入值s1.insert(1);s1.insert(4);s1.insert(5);// 支持迭代器因此也支持范围forfor (auto e : s1){cout e ;}cout endl;// 删除6没有该值则不删除s1.erase(6);// 删除4有该值则删除该值s1.erase(4);for (auto e : s1){cout e ;}cout endl;return 0;
}
测试结果 1.1.6. unordered_set的桶操作
函数声明功能介绍size_t bucket_count()const返回哈希桶中桶的总个数size_t bucket_size(size_t n)const返回n号桶中有效元素的总个数size_t bucket(const K key)返回元素key所在的桶号
代码演示
#includeunordered_set
int main()
{unordered_setint s1 { 1,4,6,9,3,7,5 };// 获取桶的总个数cout bucket_count() s1.bucket_count() endl;// 获取2号桶有效元素个数cout bucket_size(2) s1.bucket_size(2) endl;// 数值6所在的桶号cout bucket(6) s1.bucket(6) endl;return 0;
}
测试结果 2 unordered_map
1. unordered_map是存储key, value键值对的关联式容器其允许通过key快速的索引到与其对应的value。2. 在unordered_map中键值通常用于惟一地标识元素而映射值是一个对象其内容与此键关联。键和映射值的类型可能不同。3. 在内部,unordered_map没有对kye, value按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的valueunordered_map将相同哈希值的键值对放在相同的桶中。4. unordered_map容器通过key访问单个元素要比map快但它通常在遍历元素子集的范围迭代方面效率较低。5. unordered_maps实现了直接访问操作符(operator[])它允许使用key作为参数直接访问value。6. 它的迭代器至少是前向迭代器。 1.2 unordered_map的接口说明
1.2.1. unordered_map的构造
函数声明功能介绍unordered_map构造一个空的 unordered_map 对象unordered_map(initializer_listT il) 使用列表的内容初始化容器。
代码演示
#includeunordered_map
int main()
{// 构造空对象unordered_mapstring,int m1;// 列表构造对象unordered_mapstring, string m2 {{insert,插入},{erase,删除},{string,字符串} };return 0;
}
测试结果 1.2.2. unordered_map的容量
函数声明功能介绍bool empty() const检测unordered_map是否为空size_t size() const获取unordered_map的有效元素个数
代码演示
#includeunordered_map
int main()
{unordered_mapstring, string m1 {{insert,插入},{erase,删除},{string,字符串} };cout empty() m1.empty() endl;cout size() m1.size() endl;return 0;
}
测试结果 1.2.3. unordered_map的迭代器
函数声明功能介绍begin返回unordered_map第一个元素的迭代器end返回unordered_map最后一个元素下一个位置的迭代器
代码演示
#includeunordered_map
int main()
{unordered_mapstring, string m1 {{insert,插入},{erase,删除},{string,字符串} };// 获取第一个元素的迭代器使用auto更简便//unordered_mapstring, string::iterator it m1.begin();auto it m1.begin();while (it ! m1.end()){cout it-first : it-second endl;it;}cout endl;return 0;
}
测试结果 1.2.4. unordered_map的元素访问
函数声明功能介绍operator[]返回与key对应的value没有一个默认值
代码演示
#includeunordered_map
int main()
{// 统计各自水果的个数string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉,苹果,草莓, 苹果,草莓 };unordered_mapstring, int countMap;for (auto e : arr){// 水果没有出现则插入该水果出现则将个数countMap[e];}for (auto kv : countMap){cout kv.first : kv.second endl;}cout endl;return 0;
}
测试结果 注意该函数中实际调用哈希桶的插入操作用参数key与V()构造一个默认值往底层哈希桶中插入如果key不在哈希桶中插入成功返回V()插入失败说明key已经在哈希桶中将key对应的value返回。此处与map中的operator[]原理类似。 1.2.5. unordered_map的查询
函数声明功能介绍iterator find(const K key)返回key在哈希桶中的位置size_t count(const K key)返回哈希桶中关键码为key的键值对的个数
代码演示
#includeunordered_map
int main()
{unordered_mapstring, int m1 {{string,1 }, { insert,2 }, { left,3 } };// 查找left的位置打印该位置键值对的值auto pos m1.find(left);cout pos-first : pos-second endl;// 计算key为string的键值对个数size_t count m1.count(string);cout count count endl;return 0;
}
测试结果 注意unordered_map中key是不能重复的因此count函数的返回值最大为1。
6. unordered_map的修改操作
函数声明功能介绍insert向容器中插入键值对erase删除容器中的键值对void clear()清空容器中有效元素个数void swap(unordered_map)交换两个容器中的元素
代码演示
#includeunordered_map
int main()
{unordered_mapstring, int m1;pairstring, int kv1(string, 1);// 插入值m1.insert(kv1);// 有名对象m1.insert({ left,2 });m1.insert(make_pair(right, 3));for (auto e : m1){cout e.first : e.second endl;}cout endl;// 删除key为string的键值对m1.erase(string);for (auto e : m1){cout e.first : e.second endl;}cout endl;return 0;
}
测试结果 7. unordered_map的桶操作
函数声明功能介绍size_t bucket_count()const返回哈希桶中桶的总个数size_t bucket_size(size_t n)const返回n号桶中有效元素的总个数size_t bucket(const K key)返回元素key所在的桶号
代码演示
#includeunordered_map
int main()
{unordered_mapstring, int m1 {{string,1},{right,2},{insert,3}};// 获取桶的总个数cout bucket_count() m1.bucket_count() endl;// 获取3号桶有效元素个数cout bucket_size(2) m1.bucket_size(3) endl;// key为right所在的桶号cout bucket(right) m1.bucket(right) endl;return 0;
}
测试结果
