网站制作方案怎么写,网站有时打不开,Dell网站建设建议,哈尔滨网站建设平台一、关联式容器
vector/list/deque… 这些容器统称为序列式容器 因为其底层为线性序列的数据结构 里面存储的是元素本身
map/set… 这些容器统称为关联式容器 关联式容器也是用来存储数据的 与序列式容器不同的是 其里面存储的是key, value结构的键值对 在数据检索时…
一、关联式容器
vector/list/deque… 这些容器统称为序列式容器 因为其底层为线性序列的数据结构 里面存储的是元素本身
map/set… 这些容器统称为关联式容器 关联式容器也是用来存储数据的 与序列式容器不同的是 其里面存储的是key, value结构的键值对 在数据检索时比序列式容器效率更高
二、键值对
“键值对”用来表示具有一一对应关系的一种结构 该结构中一般只包含两个成员变量key和value key代表键值value表示与key对应的信息 比如 现在要建立一个英汉互译的字典 那该字典中必然有英文单词与其对应的中文含义 而且英文单词与其中文含义是一一对应的关系 即通过该应该单词在词典中就可以找到与其对应的中文含义 SGI-STL中关于键值对的定义
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
3.1 树形结构的关联式容器 根据应用场景的不同 CSTL总共实现了 两种不同结构的管理式容器树型结构与哈希结构 树型结构的关联式容器主要有四种 map、set、multimap、multiset 底层都是使用平衡搜索树(红黑树)来实现 容器中的元素是一个有序的序列 3.2 set的介绍 set是按照一定次序存储元素的容器 与map/multimap不同的是 map/multimap中存储的是真正的键值对key, value set中只放value但在底层实际存放的是由value, value构成的键值对 在set中元素是唯一的 元素的value就是key类型为T set元素可以插入或删除但不能修改 map不能修改key但可以修改value值 set中插入元素时只需要插入value即可不需要构造键值对 set中的元素总是按内部比较对象(类型比较) 默认按照小于来比较 所指示的特定“严格弱排序”准则进行排序 使用set的迭代器遍历set中的元素可以得到有序序列 set容器通过key访问单个元素的速度通常比 unordered_set容器慢但它们允许根据顺序对 子集进行直接迭代 set中查找某个元素时间复杂度为 l o g 2 n log_2 n log2n set中的元素之所以不允许修改是怕破坏搜索规则 3.3 set的定义及使用
set的定义
setint s1; // 构造int类型的空容器setint s2(s1); // 拷贝构造string str(abcd);
setchar s3(str.begin(), str.end()); // 迭代器构造某段区间setint, greaterint s4; // 比较方式改为大于 set的各个接口跟之前学的vector、list差不多 就不多介绍 set的使用
void test_set()
{setint s;// 插入元素并去重s.insert(1);s.insert(1);s.insert(2);s.insert(1);s.insert(2);s.insert(3);s.insert(4);s.insert(3);// 搜索树不允许修改key可能会破坏搜索的规则// 1. 迭代器遍历容器setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;// 2. 范围for遍历容器for (auto e : s){cout e ;}cout endl;// 删除元素s.erase(1);// 查找删除setint::iterator pos s.find(2);if (pos ! s.end())s.erase(pos);// 计算容器中值为3的元素cout s.count(3) endl;// 清空容器s.clear();// 交换两个容器的数据setint tmp{ 5, 7, 9 };s.swap(tmp);
}// 输入一个值查找在不在
void test_set2()
{setint s;s.insert(1);s.insert(1);s.insert(2);s.insert(1);s.insert(2);s.insert(3);s.insert(3);s.insert(3);int x;while (cin x){/*setint::iterator it s.find(x);if (it ! s.end()){cout 在 endl;}else{cout 不在 endl;}*/if (s.count(x)){cout 在 endl;}else{cout 不在 endl;}}
}multiset 允许冗余其他跟set还是一样的
void test_set3()
{multisetint s;s.insert(1);s.insert(1);s.insert(2);s.insert(1);s.insert(2);s.insert(3);s.insert(3);s.insert(3);for (auto e : s){cout e ;}cout endl;// 有多个keyfind找中序的第一个key
}四、map
4.1 map的介绍 map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元 素使用迭代器遍历map中的元素可以得到一个有序序列 在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的 内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型 value_type绑定在一起为其取别名称为pairtypedef pairconst key, T value_type; map容器中的键值key不能修改但元素值value可以修改 因为map底层是根据每个元素的键值key构建的 在内部map中的元素总是按照键值key进行比较排序的 不传内部比较对象时map中元素键值key默认按小于比较 map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序 对元素进行直接迭代 map支持下标访问符即在[]中放入key就可以找到与key对应的value map的底层是平衡二叉搜索树(红黑树) map查找某个元素时间复杂度为 l o g N log N logN
4.2 map的定义及使用
map的定义
// 构造一个key为stringvalue为char的容器
mapstring, char m1; // 构造一个跟m1一样的容器
mapstring, char m2(m1);// 迭代器构造m2的某段区间的容器
mapstring, char m3(m2.begin(), m2.end());// key的比较方式改成大于
mapstring, char, greaterstring m4; map的插入和删除 value_type是pair的别名
typedef pairconst key, T calue_type;因此插入时需要构造一个pair的匿名对象
void test_map()
{mapstring, string dict;// 构造一个pair的匿名对象去插入dict.insert(pairstring, string(int, 整型)); // 用pair代码会很长更常用的是make_pair// make_pair是一个函数模板,能通过传参自动推导类型dict.insert(make_pair(sort, 排序)); dict.insert(make_pair(string, 字符串));dict.insert(make_pair(count, 计数));// 已经有的key,会插入失败dict.insert(make_pair(count, (计数))); // mapstring, string::iterator dit dict.begin();auto dit dict.begin();while (dit ! dict.end()){// 直接*dit无法通过编译.C不支持返回两个值// dit解引用后是一个pair的结构体,里面有两个值,并不支持流插入// cout (*dit).first : (*dit).second endl;cout dit-first : dit-second endl; // 结构体里的指针一般用箭头dit;}cout endl;// 根据key值删除dict.erase(string);//迭代器删除mapstring, string::iterator pos dict.find(sort);if (pos ! dict.end())dict.erase(pos);
}insert的返回值是pair pair第一个成员是map的迭代器类型 第二个成员是bool类型
若插入元素的键值key在map中不存在 insert插入成功并返回插入后元素的迭代器和true若插入元素的键值key在map中已存在 则insert插入失败并返回map中键值为key元素的迭代器和false
map的operator[ ] operator[ ] 的返回值 [ ]operator实现的逻辑分为以下3个步骤
调用insert函数插入键值对拿出从insert函数获取到的迭代器返回该迭代器位置元素的值value
代码分解
mapped_type operator[] (const key_type k)
{//1. 调用insert函数插入键值对pairiterator, bool ret insert(make_pair(k, mapped_type()));//2. 拿出从insert函数获取到的迭代器iterator it ret.first;//3. 返回该迭代器位置元素的值valuereturn it-second;
}[ ]的插入、修改、查找、插入修改 以及统计水果出现的次数
void test_map2()
{string arr[] { 苹果, 香蕉, 西瓜, 梨子, 香蕉, 西瓜, 西红柿, 香蕉, 西瓜, 苹果, 西红柿 };mapstring, int countMap;//for (auto e : arr) // 统计水果出现次数//{// mapstring, int::iterator it countMap.find(e);// if (it countMap.end())// {// countMap.insert(make_pair(e, 1));// }// else// {// it-second;// }//}for (auto e : arr) // 方括号统计水果出现次数{countMap[e]; // [] 的三个功能: 插入、修改、查找、插入修改}for (auto kv : countMap){cout kv.first : kv.second endl; // 结构体里的指针一般用箭头}cout endl;}// countMap[e]; 这段代码底层实现
// V operator[](const K key)
// {
// pairiterator, bool ret insert(make_pair(key, V()));
// return ret.first-second;
//}void test_map3()
{mapstring, string dict;dict.insert(make_pair(sort, 排序));dict.insert(make_pair(string, 字符串));dict.insert(make_pair(count, 计数));dict.insert(make_pair(count, (计数)));dict[left]; // 插入dict[right] 右; // 插入修改dict[string] (字符串); // 修改cout dict[string] endl; // 查找cout dict[endl] endl; // 查找auto dit dict.begin();while (dit ! dict.end()){cout dit-first : dit-second endl; dit;}cout endl;
}[ ]operator的返回值是key的value的引用 所以我们对该函数返回值的修改 实际就是对键值key的value的修改
multimap multimap跟map基本一样 只是multimap允许键值冗余 find返回值是返回搜索树中序第一个键值 为key的元素的迭代器
由于冗余调用operator[ ]时 返回键值应为哪个key的value引用 而存在歧义因此multimap没有operator[ ]接口 如果支持迭代器就一定支持范围for 因为范围for的底层就是迭代器 五、map和set的区别 map元素是key-value(关键字-值)对 set元素是关键字 map和set都不允许插入重复关键字 set迭代器是const 所以不允许修改元素值 map可以修改value但不能修改key map和set底层红黑树依靠关键字保持有序性 所以不允许修改关键字 map支持下标操作set则不支持 注意map下标通过insert实现 也就是尝试插入一个查询键值对 如果存在则返回该键值对
✨✨✨✨✨✨✨✨ 本篇博客完感谢阅读 如有错误之处可评论指出 博主会耐心听取每条意见 ✨✨✨✨✨✨✨✨
