江苏龙网

  1. 主页 > 生活百科 > >

STL总结与常见面试题( 五 )

STL

priority_queue优先队列，其底层是用堆来实现的 。在优先队列中，队首元素一定是当前队列中优先级最高的那一个 。
setset 是按照特定顺序存储唯一元素的容器 。
template<class _Kty,class _Pr = less<_Kty>,class _Alloc = allocator<_Kty> >class set

  1. set 的 底层数据结构是 红黑树，一种高效的平衡检索二叉树 。
  2. set 容器中 每一个元素就是二叉树的每一个节点，对于set容器的插入删除操作，效率都比较高，原因是因为二叉树的删除插入元素并不需要进行内存拷贝和内存移动，只是改变了指针的指向 。
  3. 对 set 进行插入删除操作 都不会引起iterator的失效，因为迭代器相当于一个指针指向每一个二叉树的节点，对set的插入删除并不会改变原有内存中节点的改变，但是vector的插入删除操作一般会发生内存移动和内存拷贝，所以会发生迭代器的失效 。
  4. set容器的检索速度很快，因为采用二分查找的方法。
multisetmultiset允许元素重复而set不允许 。
template<class _Kty, class _Pr = less<_Kty>, class _Alloc = allocator<_Kty> >class multisetmapmap 是关联容器，按照特定顺序存储由 key value (键值) 和 mApped value (映射值) 组合形成的元素 。
由于 RB-tree 是一种平衡二叉搜索树，自动排序的效果很不错，所以标准的STL map 即以 RB-tree 为底层机制 。又由于 map 所开放的各种操作接口，RB-tree 也都提供了，所以几乎所有的 map 操作行为，都只是转调 RB-tree 的操作行为 。
方法说明map构造函数begin返回引用容器中第一个元素的迭代器key_comp返回容器用于比较键的比较对象的副本value_comp返回可用于比较两个元素的比较对象，以获取第一个元素的键是否在第二个元素之前find在容器中搜索具有等于 k的键的元素，如果找到返回一个迭代器，否则返回 map::endcount在容器中搜索具有等于 k（参数）的键的元素，并返回匹配的数量lower_bound返回一个非递减序列 [first, last)中的第一个大于等于值 val的位置的迭代器upper_bound返回一个非递减序列 [first, last)中第一个大于 val的位置的迭代器equal_range获取相同元素的范围，返回包含容器中所有具有与 k等价的键的元素的范围边界
multimapmultimap 的特性以及用法与 map 完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层机制 RB-tree 的 insert_equal() 而非 insert_unique 。
unordered_setunordered_set是基于哈希表，因此要了解unordered_set，就必须了解哈希表的机制 。哈希表是根据关键码值而进行直接访问的数据结构，通过相应的哈希函数(也称散列函数)处理关键字得到相应的关键码值，关键码值对应着一个特定位置，用该位置来存取相应的信息，这样就能以较快的速度获取关键字的信息 。
template < class Key,      class Hash = hash<Key>,      class Pred = equal_to<Key>,      class Alloc = allocator<Key>  > class unordered_set;  4 算法
  1. 简单查找算法，要求输入迭代器（input iterator）
find(beg, end, val); // 返回一个迭代器，指向输入序列中第一个等于 val 的元素，未找到返回 endfind_if(beg, end, unaryPred); // 返回一个迭代器，指向第一个满足 unaryPred 的元素，未找到返回 endfind_if_not(beg, end, unaryPred); // 返回一个迭代器，指向第一个令 unaryPred 为 false 的元素，未找到返回 endcount(beg, end, val); // 返回一个计数器，指出 val 出现了多少次count_if(beg, end, unaryPred); // 统计有多少个元素满足 unaryPredall_of(beg, end, unaryPred); // 返回一个 bool 值，判断是否所有元素都满足 unaryPredany_of(beg, end, unaryPred); // 返回一个 bool 值，判断是否任意（存在）一个元素满足 unaryPrednone_of(beg, end, unaryPred); // 返回一个 bool 值，判断是否所有元素都不满足 unaryPred
  1. 查找重复值的算法，传入向前迭代器（forward iterator）
adjacent_find(beg, end); // 返回指向第一对相邻重复元素的迭代器，无相邻元素则返回 endadjacent_find(beg, end, binaryPred); // 返回指向第一对相邻重复元素的迭代器，无相邻元素则返回 endsearch_n(beg, end, count, val); // 返回一个迭代器，从此位置开始有 count 个相等元素，不存在则返回 endsearch_n(beg, end, count, val, binaryPred); // 返回一个迭代器，从此位置开始有 count 个相等元素，不存在则返回 end


推荐阅读


上一篇：教你如何沏白茶,百合山药茶的做法

下一篇：喝茶是不是可以解酒,喝什么能解酒