程序员面试秘笈之(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 称为:双向队列容器
- deque 比 vector 多了 push_front() 和 pop_front()两个函数,而这两个函数都是对于 首部 进行操作的。因此得到第一个使用 deque 的情况,就是当程序需要从首尾两端进行 插入 和 删除 元素的操作;
- 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)的内部结构是一个 平衡二叉树。平衡二叉树有下面几种:
- AVL-tree;
- RB-tree;
- 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 通过迭代才做,不知道容器的内部结构,所以无法做到真正的删除。
更多推荐
C和C++程序员面试秘笈之(11)
发布评论