STL总结与常见面试题( 八 ) _STL

使用双向迭代器的重排算法

reverse(beg, end); // 翻转序列中的元素，返回 voidreverse_copy(beg, end, dest);; // 翻转序列中的元素，返回一个迭代器，指向拷贝到目的序列的元素的尾后位置

使用随机访问迭代器的重排算法

random_shuffle(beg, end); // 混洗输入序列中的元素，返回 voidrandom_shuffle(beg, end, rand); // 混洗输入序列中的元素，rand 接受一个正整数的随机对象，返回 voidshuffle(beg, end, Uniform_rand); // 混洗输入序列中的元素，Uniform_rand 必须满足均匀分布随机数生成器的要求，返回 void

最小值和最大值

min(val1, va12); // 返回 val1 和 val2 中的最小值，两个实参的类型必须完全一致 。参数和返回类型都是 const的引引用，意味着对象不会被拷贝 。下略min(val1, val2, comp);min(init_list);min(init_list, comp);max(val1, val2);max(val1, val2, comp);max(init_list);max(init_list, comp);minmax(val1, val2); // 返回一个 pair，其 first 成员为提供的值中的较小者，second 成员为较大者 。下略minmax(vall, val2, comp);minmax(init_list);minmax(init_list, comp);min_element(beg, end); // 返回指向输入序列中最小元素的迭代器min_element(beg, end, comp); // 返回指向输入序列中最小元素的迭代器max_element(beg, end); // 返回指向输入序列中最大元素的迭代器max_element(beg, end, comp); // 返回指向输入序列中最大元素的迭代器minmax_element(beg, end); // 返回一个 pair，其中 first 成员为最小元素，second 成员为最大元素minmax_element(beg, end, comp); // 返回一个 pair，其中 first 成员为最小元素，second 成员为最大元素

字典序比较，根据第一对不相等的元素的相对大小来返回结果。如果第一个序列在字典序中小于第二个序列，则返回 true 。否则，返回 fa1se 。如果个序列比另一个短，且所有元素都与较长序列的对应元素相等，则较短序列在字典序中更小。如果序列长度相等，且对应元素都相等，则在字典序中任何一个都不大于另外一个。

lexicographical_compare(beg1, end1, beg2, end2);lexicographical_compare(beg1, end1, beg2, end2, comp);5 如何选择合适的容器需要根据容器的特点和使用场景而定，可能满足需求的不止一种容器。
按是否有序关联性分为：

序列式容器：array、vector、deque、list 和 forward_list；
关联式容器：map、multimap、set 和 multiset；
无序关联式容器：unordered_map、unordered_multimap、unordered_set 和 unordered_multiset；
容器适配器：stack、queue 和 priority_queue 。根据容器底层采用是否是连续的存储空间分为：
采用连续的存储空间：array、vector、deque；
采用分散的存储空间：list、forward_list 以及所有的关联式容器和哈希容器。

注意：deque 容器归为使用连续存储空间的这一类，是存在争议的。因为 deque 容器底层采用一段一段的连续空间存储元素，但是各段存储空间之间并不一定是紧挨着的。

文章插图

选择容器流程图(来源于网络)
选择容器的几点建议：

如果只是存储确定或不确定的对象，而不去删除它们，可以选用vector 。就是因为vector是数组的替代品，是连续内存的，不适合频繁的删除。
如果在容器的指定位置插入新元素，则只能选择序列式容器，不选择关联式容器和哈希容器。
如果频繁的插入和删除，可以选用list(链表)，内存不是连续的，可以方便的插入和删除，但是不支持索引访问。
数据量很大，不在乎他们的排序，要求效率，对容器中各元素的存储位置没有要求，可以考虑使用哈希容器，反之就要避免使用哈希容器。
如果是随机访问迭代器，选择 array、vector、deque 。
如果是双向迭代器，考虑 list 序列式容器以及所有的关联式容器。
如果必须是前向迭代器，考虑 forward_list序列式容器以及所有的哈希容器。
如果插入或删除操作时，容器中的其它元素不移动？选择不是array、vector、deque的其它容器。

6 面试中常出现的STL问题

vector的底层原理

vector底层是一个动态数组，包含三个迭代器，start和finish之间是已经被使用的空间范围，end_of_storage是整块连续空间包括备用空间的尾部。
当空间不够装下数据（vec.push_back(val)）时，会自动申请另一片更大的空间（1.5倍或者2倍），然后把原来的数据拷贝到新的内存空间，接着释放原来的那片空间【vector内存增长机制】。