STL 第九日 ： 容器篇总结

xiaoxiao2021-02-28  5

私房STL之vector

vector创建与遍历

vector提供了几个版本的构造函数。详见：http://www.cplusplus.com/reference/stl/vector

vector<int> iv(3,3); /*3,3,3*/

...... vector<int>::iterator beg = iv.begin(), end = iv.end(); cout << *beg << endl; ......

vector删除

a b c d e f g hb c d e f g h hb c d e f g h

a b c d e f g hh b c d e f g ah b c d e f g

vector陷阱

...... vector<int> iv(3,3); iv.push_back(10); /*3,3,3,10*/ vector<int>::iterator beg = iv.begin(), end = --iv.end(); cout << iv.size() << " " << *beg << " " << *end << endl; /*4 3 10*/ iv.push_back(20); cout << iv.size() << " " << *beg << " " << *end << endl; /*bomb.invalid iterator.*/ ...... bomb！！！

vector元素排序

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> iv(3,3); unsigned int i; /*add new elem.*/ iv.push_back(10); iv.push_back(9); iv.push_back(0); vector<int>::iterator beg = iv.begin(), end = iv.end(); /*print.*/ for(i=0; i<iv.size(); i++) cout << iv[i] << " "; cout << endl; /*sort.*/ sort(beg,end); /*print.*/ for(i=0; i<iv.size(); i++) cout << iv[i] << " "; cout << endl; return 0; }

3 3 3 10 9 00 3 3 3 9 10请按任意键继续. . .

vector查找

...... vector<int> iv(3,3); unsigned int i; /*add new elem.*/ iv.push_back(10); iv.push_back(9); iv.push_back(0); vector<int>::iterator beg = iv.begin(), end = iv.end(), ret; ret = find(beg,end,10); cout << *ret << endl; ......

建议

vector还提供insert，earse，clear等元素的操作，不一一复述。最后是很不错的vector文档：http://www.cplusplus.com/reference/stl/vector/

私房STL之list

list_node

list的查找

...... list<int> il; il.push_back(5); il.push_back(98); il.push_back(7); il.push_back(20); il.push_back(22); il.push_back(17); list<int>::iterator ite; ite = find(il.begin(),il.end(),20); cout << *ite << endl;/*20*/ ......

list创建与遍历

STL中也为list实现了几个版本的构造函数：http://www.cplusplus.com/reference/stl/list/list/，有最简单缺省的版本。

list的遍历使用迭代器，如下：

#include <iostream> #include <list> #include <algorithm> using namespace std; int main() { unsigned int i; list<int> il; il.push_back(5); il.push_back(98); il.push_back(7); il.push_back(20); il.push_back(22); il.push_back(17); list<int>::iterator ite; for(ite = il.begin(); ite != il.end(); ite++) cout << *ite << " "; cout << endl; return 0; }

list在空间拓展的时候，没有经历vector式的空间倒腾，所以只要不earse元素，指向它ite是不会失效的。

list元素操作

list有提供pop_back,erase,clear,insert等实用的元素操作，不一一复述，给出有用的文档：http://www.cplusplus.com/reference/stl/list/

list排序

STL算法（<algorithm>）实现的sort只适用于支持随机访问的数据，所以它不适用于list，list不支持随机访问。所以list内部实现了自己的sort，内部排序使用使用迭代版本的快排。

unsigned int i; list<int> il; il.push_back(5); il.push_back(98); il.push_back(7); il.push_back(20); il.push_back(22); il.push_back(17); list<int>::iterator ite; for(ite = il.begin(); ite != il.end(); ite++) cout << *ite << " "; cout << endl; il.sort(); for(ite = il.begin(); ite != il.end(); ite++) cout << *ite << " "; cout << endl; return 0;

5 98 7 20 22 175 7 17 20 22 98请按任意键继续. . .

建议

list使用轻松自如，硬伤是由于空间的个性（不连续），不能随机访问。

私房STL之deque

bug,deque_in_real

deque的迭代器

deque的迭代器与一般的迭代器不同，并不是vector或者list的普通指针式迭代器，有必要写下。

...... typedef T map_pointer; T* cur;//指向当前元素 T* first;//指向缓冲区头 T* last;//指向缓冲区尾巴 map_pointer node;//二级指针，指向缓冲区地址表中的位置 ......

deque的创建与遍历

STL中deque有提供多种版本的构造函数，一把使用缺省构造函数。

...... deque<int> id; ......

...... deque<int> id; id.push_back(1); id.push_back(2); id.push_back(3); id.push_back(4); id.push_back(5); id.push_back(6); cout << id[2] << endl; /*3*/ ......

deque的查找

...... deque<int> id; id.push_back(1); id.push_back(2); id.push_back(6); deque<int>::iterator ite; ite = find(id.begin(),id.end(),6); cout << *ite << endl; /*6*/ ......

建议

deque在实际的应用当中使用的比较少，但正如文章开头指出的，它是容器stack和queue的幕后功臣，所以了解它的内部实现机制多多益善。

私房STL之stack与queue

stack

==================

queue

stack的创建与遍历

..... stack<int> is; is.push(4); is.push(3); is.push(2); is.push(1); is.push(0); while(!is.empty()) { cout << is.top() << " "; is.pop(); }// while /*0 1 2 3 4*/ .....

stack不允许遍历！

queue的创建与遍历

...... queue<int> iq; iq.push(4); iq.push(3); iq.push(2); iq.push(1); iq.push(0); cout << iq.back() << endl; /*0*/ while(!iq.empty()) { cout << iq.front() << " "; iq.pop(); }// while /*4 3 2 1 0*/ ......

queue不允许遍历！

stack/queue的查找和排序

stack/queue不允许遍历！

关于stack的top()和pop()

...... Sequence c; // 底层容器 ...... reference top() { return c.back(); } void pop() { c.pop_back(); } ......

...... stack<int,list<int>> is; is.push(4); is.push(3); is.push(2); is.push(1); is.push(0); while(!is.empty()) { cout << is.top() << " "; is.pop(); }// while /*0 1 2 3 4*/ ......

建议

stack/queue在实际应用用的比较多，两者有很大的共性，因此queue被提取出来。嘿嘿，突然对STL肃然起敬。