网站建设女装规划书,火车头wordpress获取不到分类,东莞网站关键排名,北京网站建设net2006关联式容器
在前面#xff0c;我们所学的vector、list、deque#xff0c;这些都是序列容器#xff0c;也就是底层为线性序列的数据结构。 而关联式容器是C标准库中的一种类别#xff0c;用于存储键值对#xff08;key-value pair#xff09;#xff0c;关联式容器中的元…关联式容器
在前面我们所学的vector、list、deque这些都是序列容器也就是底层为线性序列的数据结构。 而关联式容器是C标准库中的一种类别用于存储键值对key-value pair关联式容器中的元素中的元素是按照键值进行有序存储的同时也支持快速查找、插入、修改等操作。而map和set就是主要的类型
这些关联式容器在实现上通常采用平衡二叉搜索树或哈希表等数据结构来保证元素的有序性和高效的查找性能。
键值对
键值对是关联式容器中的一种结构它由一个键key和一个对应值value组成。在关联式容器中每个元素都有一个唯一的键用于标识和访问该元素。键值对的特性使得关联式容器能够通过键快速查找、插入、删除。
在关联式容器中键通常用于确定元素的顺序和唯一性而值则是与键关联的数据。键和值可以是任何类型但通常使用类或结构体作为键类型以提供自定义的比较规则。通过比较键的值关联式容器能够按照键的顺序进行有序存储并支持快速的查找操作。
键值对的定义
template class T1, class T2
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1 a, const T2 b): first(a), second(b)
{}
};set
介绍
set是C标准库中的一种关联式容器它用于存储一组有序的、唯一的元素。set中的元素按照键值进行自动排序并且不允许存在重复的元素。
set在底层是由二叉搜索树红黑树实现的。 set中只放value但在底层实际存放的是由vlaue,value 构成的键值对。
set中查找某个元素时时间复杂度为log_2 n .
使用 void test1()
{setint s;s.insert(1);s.insert(3);s.insert(3);s.insert(4);s.insert(6);s.insert(9);s.insert(7);setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;// 使用迭代器逆向打印set中的元素for (auto it s.rbegin(); it ! s.rend(); it){cout *it ;}cout endl;setint::iterator pos s.find(7);if (pos ! s.end()){cout 找到了 endl;s.erase(pos);}}void test2()
{setint s;s.insert(1);s.insert(3);s.insert(3);//s.insert(4);s.insert(6);s.insert(9);s.insert(7);auto start s.lower_bound(4);cout *start endl;auto finish s.upper_bound(4);cout *finish endl;
}muiltiset
multisetsC标准库中的一种关联式容器它与set容器类似但允许存储重复的元素。 muiltiset容器和set容器的主要区别在于对重复元素的处理。在set容器中每个键值只能出现一次而在muitiset容器中同一个键值可以出现多次。multisey中的元素会根据键值自动进行排序。
void test3()
{multisetint s;s.insert(5);s.insert(1);s.insert(6);s.insert(3);s.insert(4);s.insert(5);s.insert(1);s.insert(1);s.insert(5);s.insert(1);s.insert(1);s.insert(2);s.insert(7);s.insert(10);multisetint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;//统计相同元素的个数cout s.count(1) endl;cout s.count(5) endl;
}map
介绍
map是C标准库中的一种关联式容器它用于存储一组键值对。每个元素都由一个唯一的键和对应的值组成。map中的元素按照键进行自动排序并且不允许存在重复键。
在map内部key和value通过成员类型value_type绑定在一起为其取别名为pair
typedef pairconst key,T value_type;map支持下标访问符即在[]中放入key就可以找到与key对应的value值
map通常被实现为二叉搜索树平衡二叉搜索树.
使用 void test4()
{mapstring, string dict;dict.insert(pairstring, string(sort, 排序));//pairstring, string kv(string, 字符串);pairstring, string kv { string, 字符串 };dict.insert(kv);// C11 多参数隐式类型转换(构造函数)dict.insert({ apple, 苹果 });// C98dict.insert(make_pair(sort, 排序));for (auto kv : dict){cout kv.first : kv.second endl;}cout endl;
}void test5()
{string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,
苹果, 香蕉, 苹果, 西瓜, 香蕉, 草莓 };mapstring, int countMap;for (auto e : arr){countMap[e];}for (auto kv : countMap){cout kv.first : kv.second endl;}cout endl;//通过operator[]进行查找value值cout countMap[苹果] endl;
}multimap
multimapC标准库中的一种关联式容器它与map容器类似但允许存储重复的键。
multimap容器和map容器的主要区别在于对重复键的处理方式。在multimap中可以有很多个元素具有相同的键这些元素会按照键进行自动排序但不保证值的顺序。
multimap中没有重载operator[]操作 使用时与map包含的头文件相同。
