C和C++程序员面试秘笈之（11）

程序员面试秘笈之（11）"/>

C和C++程序员面试秘笈之（11）

本系列博客基于董山海的<C和C++程序员面试秘笈>，旨在记录，欢迎交流，可联系 zywang@shu.edu !

---

第11章：STL（标准模板库）

---

文章目录

• • 1、面试题1
  • 2、面试题2
  • 3、面试题3
  • 4、面试题4
  • 5、面试题5
  • 6、面试题6
  • 7、面试题7
  • 8、面试题8
  • 9、面试题9
  • 10、面试题10

1、面试题1

S T L ( S t a n d a r d T e m p l a t e L i b r a r y ) STL \ (Standard \ Template \ Library) STL (Standard Template Library)：标准模板库。 S T L STL STL 就是把数据和操作分离开。

S T L STL STL 序列容器： v e c t o r 、 s t r i n g 、 d e q u e 、 l i s t vector、string、deque、list vector、string、deque、list
S T L STL STL 关联容器： s e t 、 m u l t i s e t 、 m a p 、 m u l t i m a p set、multiset、map、multimap set、multiset、map、multimap
S T L STL STL适配容器： s t a c k 、 q u e u e 、 p r i o r i t y q u e u e stack、queue、priorityqueue stack、queue、priorityqueue

2、面试题2

S T L STL STL 怎么实现 v e c t o r vector vector

#include <vector>
using namespace std;vector<int> array;
array.push_back(1);
array.push_back(2);
array.push_back(3);
//反向遍历 array 数组
for (vector<int>::size_type i = array.size() - 1; i > 0; --i) {cout << array[i] << endl;
}

---

3、面试题3

l i s t list list 和 v e c t o r vector vector 区别：

v e c t o r vector vector 和数组类似，拥有一段连续的内存空间，并且起始地址不变，因此它能非常好的支持随机存取（使用 [] 操作符访问其中的元素）。但由于它的内存地址是连续的，所以中间进行插入和删除操作会造成内存块的拷贝。

l i s t list list 由数据结构中双向链表实现的，因此它的内存空间可以是不连续的。因此只能通过指针来进行数据的访问。但由于链表的特点，它可以很好的效率支持任意地方的删除和插入。

#include <iostream>
#include <vector>
#include <list>
using namespace std;int main(void) {vector<int> v;list<int> l;//往 v 和 l 中分别添加元素for (int i = 0; i < 8; i++) {v.push_back(i);l.push_back(i);}cout << "v[2]=" << v[2] << endl;//cout << "l[2]=" << l[2] << endl;	//编译错误，list没有重载[]cout << (v.begin() < v.end()) << endl;//cout << (l.begin() < l.end()) << endl;	//编译错误，list::iterator 没有重载 []cout << *(v.begin() + 1) << endl;//vector<int>::iterator itv = v.begin();list<int>::iterator itl = l.begin();itv = itv + 2;//itl = itl +2;		//编译错误，list::iterator 没有重载+itl++;	//list::iterator 中重载了 ++，只能使用 ++ 进行迭代访问itl++;cout << &itv << endl;cout << *itl << endl;return 0;
}

Vector 拥有一段连续的内存空间，能非常好的支持随机存取，因此 vector::iterator 支持 ‘+’、‘+=’、‘<’ 等操作符。

List 的内存空间是不连续的，不支持随机访问，因此 list::iterator 不支持 ‘+’、‘+=’、‘<’ 等操作运算符运算。所以只能用 ‘++’ 进行迭代。

vector 使用的是数组方式，当删除一个元素后，此元素的后面元素会自动往前移动；
list 是使用链表结构，因此执行 erase 时会释放链表的节点内存。但是可以通过 erase 的返回值获得链表的下一个元素；

---

4、面试题4

stl::deque 是由一段一段定量的连续空间组成的，因此是动态数组类型。

deque 称为：双向队列容器

1. deque 比 vector 多了 push_front() 和 pop_front()两个函数，而这两个函数都是对于 首部 进行操作的。因此得到第一个使用 deque 的情况，就是当程序需要从首尾两端进行 插入 和 删除 元素的操作；
2. deque 中不存在 capacity() 和 reserve() 成员函数，在 vector 中分别用于获取和设置容器容量；

---

5、面试题5

适配器 stack 和 queue 的使用：

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;int main() {stack<int, vector<int>>	s;queue<int, vector<int>>	q;//for (int i = 1; i < 10; i++) {s.push(i);q.push(i);}//while (!s.empty()) {cout << s.top() << endl;s.pop();}//while (!q.empty()) {cout << q.front() << endl;//q.pop();  这边是错误的，因为 vector 用 erase}//return 0;
}

---

6、面试题6

set 作用：set 中元素的插入、删除、遍历操作

#include <iostream>
#include <set>
#include <string>
using namespace std;int main() {set <string> strset;set <string>::iterator si;strset.insert("cantaloupes");strset.insert("apple");strset.insert("orange");strset.insert("banana");strset.insert("grapes");strset.insert("grapes");strset.erase("banana");//for (si = strset.begin(); si != strset.end(); si++) {cout << *si << " ";}cout << endl;return 0;
}

上述代码，往 set 中插入 6 个元素，其中两个是相同的，grapes，所以实际插入只有5个元素。然后使用迭代器 si 遍历 set 集合。

---

7、面试题7

关联容器 map 的使用：
map 中存放的每一个元素都是一个键值对。

#include <iostream>
#include <map>
#include <string>
using namespace std;
//
int main() {map<int, string> mapstring;	//mapstring存放pair<int，string>类型的元素，键为int，值为string类型mapstring.insert(pair<int, string>(1, "one"));	//插入4个元素mapstring.insert(pair<int, string>(4, "four"));mapstring.insert(pair<int, string>(3, "three"));mapstring.insert(pair<int, string>(2, "two"));mapstring.insert(pair<int, string>(4, "four four"));	//4已经存在，插入失败//mapstring[1] = "one one";	//1已经存在，修改键为1对应的值mapstring[5] = "five";	//5不存在，添加键为 5 且值为 "five" 的元素cout << mapstring[1] << endl;	//打印键为 1 所对应的值//mapstring.erase(2);	//删除键为 2 的元素map<int, string>::iterator f = mapstring.find(2);	//迭代器，查找键为2的元素if (f != mapstring.end()) {mapstring.erase(f);}//map<int, string>::iterator it = mapstring.begin();while (it != mapstring.end()) {cout << (*it).first << " " << (*it).second << endl;it++;}return 0;
}

---

8、面试题8

map 底层是以 红黑树 实现的。
标准的关联容器（set、map 以及 set 的衍生体 multiset 和 map 的衍生体 multimap）的内部结构是一个 平衡二叉树。平衡二叉树有下面几种：

1. AVL-tree;
2. RB-tree;
3. AA-tree;

STL 的底层机制由 RB-tree(红黑树)完后的。
红黑树是一颗二叉查找树，除了二叉查找树带有一般的要求外：

• 结点为红色或者黑色；
• 所有叶子结点都是空节点，并且被着为黑色；
• 如果父节点为红色，那么两个子节点都是黑色的；
• 结点到其子孙节点的每条简单路径上都包含相同数目的黑色结点；
• 根节点是黑色的；

---

9、面试题9

S T L STL STL 算法的使用：

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
//
void print(int elem) {cout << elem << " ";
}
//
int main() {deque<int>	coll;//for (int i = 1; i <= 9; ++i) {coll.push_back(i);}//deque<int>::iterator pos1;pos1 = find(coll.begin(), coll.end(), 2);	//调用 find 分别获得整数 2 在 coll 的位置deque<int>::iterator pos2;pos2 = find(coll.begin(), coll.end(), 7);for_each(pos1, pos2, print);	//调用 for_each 函数从 pos1 到 pos2 的区间元素依次执行 printcout << endl;//deque<int>::reverse_iterator rpos1(pos1);deque<int>::reverse_iterator rpos2(pos2);for_each(rpos2, rpos1, print);cout << endl;//return 0;
}

---

10、面试题10

v e c t o r vector vector 中的 e r a s e erase erase 方法与 a l g o r i t h m algorithm algorithm 中的 r e m o v e remove remove 的区别：

• v e c t o r vector vector 中的 e r a s e erase erase 是真正的删除元素，迭代器就不能访问；
• a l g o r i t h m algorithm algorithm 中的 r e m o v e remove remove 只是简单地把 r e m o v e remove remove 的元素移动到容器的最后面，迭代器还是可以访问到的。这是因为 a l g o r i t h m algorithm algorithm 通过迭代才做，不知道容器的内部结构，所以无法做到真正的删除。

---