网站如何连接微信支付宝吗,wordpress 如何做门户,海南网站建设方案,网站建设流量入口1 关联式容器
STL中我们常用的部分容器#xff0c;比如#xff1a;vector、list、deque、forward_list(C11)等#xff0c;这些容器统称为序列式容器#xff0c;因为其底层为线性序列的数据结构#xff0c;里面存储的是元素本身。 那什么是关联式容器呢#xff1f;它与序…1 关联式容器
STL中我们常用的部分容器比如vector、list、deque、forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。 那什么是关联式容器呢它与序列式容器有什么区别 关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是**key, value结构的键值对**在数据检索时比序列式容器效率更高。
2 键值对pair
用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。 比如现在要建立一个英汉互译的字典那该字典中必然有英文单词与其对应的中文含义而且英文单词与其中文含义是一一对应的关系即通过该应该单词在词典中就可以找到与其对应的中文含义。 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){}
};可见pair内有两个成员变量一个是first即key一个是second即value。 pair的构造函数 在C98中pair共有三个构造函数。 无参构造函数根据模板参数推导出类型调用该类型的默认构造函数生成key和value的值。拷贝构造函数通过两个值来构造以key、value的顺序。 此外C中还提供了一种构造键值对的方法利用make_pair函数
可以看到make_pair函数本质上是创建一个键值对对象并返回其拷贝。使用make_pair的好处是不用我们显示写模板参数。 在map的插入操作中就需要插入一个一个的键值对。此时我们可以利用匿名对象构造插入也可以使用make_pair函数。此外C11中还支持了多参数构造函数的隐式类型转换为插入键值对提供了一种更新的方式将在下文中演示。
3 树形结构的关联式容器
根据应用场景的不桶STL总共实现了两种不同结构的管理式容器树型结构与哈希结构。 树型结构的关联式容器主要有四种map、set、multimap、multiset。 这四种容器的共同点是使用平衡搜索树(即红黑树)作为其底层结果容器中的元素是一个有序的序列。下面一依次介绍每一个容器。
4 set
4.1 set
set的文档介绍如下 翻译 set是按照一定次序存储元素的容器在set中元素的value也标识它(value就是key类型为T)并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们。在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对子集进行直接迭代。set在底层是用二叉搜索树(红黑树)实现的。 注意 与map/multimap不同map/multimap中存储的是真正的键值对key, valueset中只放value但在底层实际存放的是由value, value构成的键值对。set中插入元素时只需要插入value即可不需要构造键值对。set中的元素不可以重复(因此可以使用set进行去重)。使用set的迭代器遍历set中的元素可以得到有序序列set中的元素默认按照小于来比较set中查找某个元素时间复杂度为 l o g 2 n log_2 n log2nset中的元素不允许修改(文档最后一句set底层是搜索二叉树如果允许修改整个树的大小关系就乱套了)set中的底层使用二叉搜索树(红黑树)来实现 注意set的模板参数中有一个Compare这个是用于比较的仿函数在priority_queue中也用到过仿函数这一工具。
4.2 set的使用
知晓了set的作用set的使用其实非常简单有了前面stl容器的使用经验非常方便上手。 首先是set的构造函数根据之前的经验无非就是全缺省的默认构造函数、迭代器区间构造和拷贝构造。
不过要注意的是由于set底层是一颗树在执行拷贝构造和赋值时代价是比较大的因为要进行深拷贝
4.2.1 insert
下面是比较重要的insert
对于set常用的插入操作时第一个函数。我们可以看见返回值是一个键值对这是什么意思呢 其实这里牵扯到map实现方面的问题。在map中的insert需要设计成这样以支持[]运算符重载这里是为了统一风格而设计。 由于set内不允许有重复元素当插入元素并不存在于set中时才能执行插入此时返回一个键值对键值对中的key是插入元素的迭代器value是一个bool值如果插入成功则为true当插入元素已经存在于set此时键值对中的key是那个重复元素的迭代器而value就为false。 其他的一些操作命名也都沿袭了stl一贯的风格看一眼大概就知道其功能。
4.2.2 erase和find
想要删除一个元素可以用erase。可以直接以待删除元素的值作为参数。
// 在就删除不在就不做任何处理
s.erase(3);
s.erase(30);
for (auto e : s)
{cout e ;
}
cout endl;但是要注意的是如果在set中没有找到要删除的值是什么都不会发生的。 我们也可以用迭代器进行删除用find搜索待删除元素。
// 这个值在找到有效位置再进行删除
pos s.find(5);
s.erase(pos);两种方式的区别是find如果没有找到而直接对其erase是会报错的。 这是由于如果find找不到将会返回end位置的迭代器导致越界相关的问题。 此外我们知道算法库里面也有一个find通过一段迭代器区间来进行查找但是这个find的效率不如set内置的效率高因为set中时根据红黑树来查找的而算法库中的find是根据迭代器一个一个的找。时间复杂度是对数级别和线性级别的差别。
4.2.3 count
count也可以用于查找一个元素在不在set中如果在返回1不在返回0。
4.2.4 lower_bound和upper_bound 返回迭代器到下界 返回一个迭代器该迭代器指向容器中的第一个元素该元素不被认为位于val之前(即它要么等价要么在val之后)。 该函数使用其内部比较对象(key_comp)来确定这一点并返回一个迭代器指向key_comp(element,val)将返回false的第一个元素。 如果用默认比较类型(less)实例化set类则该函数返回一个指向不小于val的第一个元素的迭代器。即val的第一个值 类似的成员函数upper_bound具有与lower_bound相同的行为只是set包含一个与val等效的元素:在这种情况下lower_bound返回一个指向该元素的迭代器而upper_bound返回一个指向下一个元素的迭代器。即val的第一个值
5 multiset
multyset和set非常类似其区别是multiset允许键值冗余即允许存在重复的元素其余操作都是一样的。 此时如果我们再对multiset执行count操作那么返回值就可能大于1了。 multiset是按照特定顺序存储元素的容器其中元素是可以重复的。在multiset中元素的value也会识别它(因为multiset中本身存储的就是value, value组成的键值对因此value本身就是keykey就是value类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)但可以从容器中插入或删除。在内部multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢但当使用迭代器遍历时会得到一个有序序列。multiset底层结构为二叉搜索树(红黑树)。 注意 multiset中再底层中存储的是value, value的键值对mtltiset的插入接口中只需要插入即可与set的区别是multiset中的元素可以重复set是中value是唯一的使用迭代器对multiset中的元素进行遍历可以得到有序的序列multiset中的元素不能修改在multiset中找某个元素时间复杂度为 O ( l o g 2 N ) O(log_2 N) O(log2N)multiset的作用可以对元素进行排序 6 map
6.1 map
先来看看map的介绍 map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型value_type绑定在一起为其取别名称为pair:typedef pairconst key, T value_type;在内部map中的元素总是按照键值key进行比较排序的。map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。map支持下标访问符即在[]中放入key就可以找到与key对应的value。map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。 map内部的成员变量中有如下三个是最为关键的 由上到下分别是 键key类型 值value)类型map有映射的意思即key映射mapped之后的值为value 键值对keyvalue类型 在map中键值通常用于排序和唯一标识元素而映射值存储与该键相关联的内容。键和映射值的类型可能不同组合在成员类型value_type中这是一种组合了两者的pair类型:
typdef pairconst Key, T value_type;其实map和set本质上是非常接近的区别在于存储的数据不同而已。map存放的是key,value而set存放的是value,value
6.2 常用接口 map大多数接口和set也很类似。先来看insert。
这里对于最常用的第一个其返回值的意义同set是一样的。 对于map的insert支持以下几种方式。
pairstring, string p(banana, 香蕉);
m.insert(p);
m.insert(pairstring, string(apple, 苹果));
m.insert(make_pair(orange, 橙子));
m.insert({ blue,蓝色 }); // C11新增多参数构造函数的隐式类型转换还需要注意的是如果插入的时候key相同但是val不相同是不会插入进去的也不会覆盖进去的。即插入过程中只比较key。key相同就不插入了。 删除操作也与set类似需要注意的是同样是以key作为标识。
6.3 map的[]运算符重载
map的[]运算符重载跟之前的序列容器如vectorstring等实现方式有比较明显的区别。先来看文档说明。
可以看到是以key为参数返回值为该key对应的value的引用。这是为什么呢 其实官方还给了一个非常重要的解释。
我们把中间部分拆开来看 会发现调用的是insert函数而insert函数的返回值是一个pair 再来看函数功能的介绍 访问元素 如果k与容器中某个元素的键匹配则该函数返回对其映射值的引用。 如果k与容器中任何元素的键不匹配则该函数用该键插入一个新元素并返回对其映射值的引用。注意这总是将容器的大小增加1即使没有将映射值赋给元素(元素是使用其默认构造函数构造的)。 类似的成员函数map::at在具有键的元素存在时具有相同的行为但在不存在时抛出异常。 简而言之 原理就是用key, T()构造一个键值对然后调用insert()函数将该键值对插入到map中
如果key已经存在插入失败insert函数返回该key所在位置的迭代器如果key不存在插入成功insert函数返回新插入元素所在位置的迭代器operator[]函数最后将insert返回值键值对中的value返回 有了这种机制就可以利用下面的代码统计关键词的个数.
string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (auto e : arr){countMap[e];}mapstring, int::iterator it countMap.begin();while (it ! countMap.end()){cout it-first : it-second endl;it;}countMap对象中它的两个参数是string和int第一次的时候不存在所以会创建一个pairstring,int对象。int则会调用它的默认构造函数即结果为0。然后有一个所以最终会将这个值给插入进去。 由于[]运算符重载返回的是value的引用那么就可以实现以下几种功能 插入查找修改插入修改 7 multimap
类比multisetmultimap即允许一个键对应多个值。 这个在实际生活中也是有意义的比如一个英文单词可能有多个中文意思。 但是与map在使用上还是有一些区别比如这个容器没有提供[]运算符重载因为无法根据一个key确定需要取的是哪个value。 同时insert函数和erase函数也有一些变化。 insert不会再返回键值对因为插入永远是成功的只需要返回迭代器就可以了
而对于erase由于一个key对应多个value此时对一个key进行删除会将所有value一并删除。 总结 Multimaps是关联式容器它按照特定的顺序存储由key和value映射成的键值对key,value其中多个键值对之间的key是可以重复的。在multimap中通常按照key排序和惟一地标识元素而映射的value存储与key关联的内容。key和value的类型可能不同通过multimap内部的成员类型value_type组合在一起value_type是组合key和value的键值对:typedef pairconst Key, T value_type;在内部multimap中的元素总是通过其内部比较对象按照指定的特定严格弱排序标准对key进行排序的。multimap通过key访问单个元素的速度通常比unordered_multimap容器慢但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。multimap在底层用二叉搜索树(红黑树)来实现。 注意multimap和map的唯一不同就是map中的key是唯一的而multimap中key是可以重复的。
