C++标准库容器篇--顺序容器

一、概述

1、标准库定义了三种顺序容器类型：vector、list 和 deque。 2、他们差别在于访问元素 的方式，以及添加或删除元素相关操作的运行代价。 3、单纯的类容器只定义了少量操作，大多数额外操作由算法库提供。

二、容器的初始化

1、构造函数初始化

#include<iostream> #include<vector> #include<list> #include<deque> using namespace std; int main() { vector<int> ivec; vector<int> ivec2(ivec); // ok //list<int> ilist(ivec); // error //vector<double> dvec(ivec); // error vector<int> a(10);// a包含10个0值元素 vector<int> b(10,1);//b为10个值为1的元素 }

2、用迭代器范围赋值

int main() { vector<string> svec; //用下面方法不要求迭代器的元素类型或者容器类型完全相同，只要相互兼容即可，兼容性待考证 list<string> slist(svec.begin(), svec.end()); //迭代器标记了复制元素的范围，由此方法可以将其他容器的子序列复制 vector<string>::iterator i = svec.begin() + svec.size() / 2; deque<string> front(svec.begin(), i);//前半部分给front deque<string> back(i, svec.end()); }

当然迭代器就是指针了，所以我们也可以用自定义的迭代器进行赋值：

#include<iostream> #include<vector> #include<list> #include<deque> #include<string> using namespace std; int main() { char *kk[] = { "kkk", "zlk", "123", "abv", "love" }; int size_kk = sizeof(kk) / sizeof(char*); list<string> list_kk(kk, kk + size_kk); vector<char*> vector_kk(kk, kk + size_kk); list<string>::iterator i = list_kk.begin(); while (i != list_kk.end()) { cout << *i++ << endl; } for (vector<char*>::iterator j = vector_kk.begin(); j < vector_kk.end(); j++) { cout << *j << endl; } }

指定数目初始化：

const list<int>::size_type list_size = 64; list<sting> kk(list_size,"kk");//kk是含有64个元素，每个都是kk的容器 list<string> kk(list_size);//64个元素初始化为0

问题：复制容器对象的构造函数和使用两个迭代器的构造函数有什么区别？ 复制容器对象：只能将一个容器初始化为另一个容器的副本，要求两个容器的类型，元素的类型完全相等。 使用两个迭代器：用一个容器的子序列初始化另外一个容器，不要求两个容器的类型是相同的。

二、顺序容器的迭代器

1、end()迭代器指向的从来就不是最后一个元素，而是最后一个元素的下一个位置！所以其迭代器范围为： [begin(), end())，左开右闭区间。

2、顺序容器中定义的类型别名

三、对顺序容器的操作

1、添加操作 需要注意的是，vector和deque在添加元素时候会导致全部迭代器失效例如：

int main() { string k[] = { "i", "have", "a", "dream" }; deque<string>kk = {k,k+4}; string word("ha"); deque<string>::iterator first = kk.begin(), last = kk.end(); while (first!=last) { kk.insert(first, word); first++; } }

在用了循环体的添加运算后，last 失效，不再指向kk.end(); 所以： 不要存储 end 操作返回的迭代器。添加或删除 deque 或 vector 容器内的元素都会导致存储的迭代器失效。 以下是正确的代码：

int main() { string k[] = { "i", "have", "a", "dream" }; deque<string>kk = {k,k+4}; string word("ha"); deque<string>::iterator first = kk.begin(), last = kk.end(); while (first!=kk.end()) { first=kk.insert(first, word); ++first; ++first; } for (deque<string>::iterator i = kk.begin(); i != kk.end(); i++) { cout << *i << endl; } }

补充：

一、vector的size和capacity的区别：

int main() { vector<int> kk; cout << kk.size() << endl;//0 cout << kk.capacity() << endl;//0 for (int i = 0; i < 20; i++) { kk.push_back(i); } cout << kk.size() << endl;//20 cout << kk.capacity() << endl;//28 kk.reserve(50); cout << kk.size() << endl;//20 cout << kk.capacity() << endl;//50 }

二、顺序容器的选择法则：

a. 如果程序要求随机访问元素，则应使用 vector 或 deque 容器。 b. 如果程序必须在容器的中间位置插入或删除元素，则应采用 list 容器。 c. 如果程序不是在容器的中间位置，而是在容器首部或尾部插入或删除元 素，则应采用 deque 容器。 d. 如果只需在读取输入时在容器的中间位置插入

原因： 1、vector 容器，除了容器尾部外，其他任何位置上的插入（或删除）操 作都要求移动被插入（或删除）元素右边所有的元素。

2、list 容器不支持随机访问，访问某 个元素要求遍历涉及的其他元素。但list容器可以高效地 insert 或 erase 一个元素。

3、在 deque 容器首部或尾部插入元素不会使任何迭代器失效，而首部或尾 部删除元素则只会使指向被删除元素的迭代器失效。

三、支持顺序容器操作的string 理解：string的很多功能也是用stl实现的，所以支持很多顺序容器的操作 用迭代器初始化string：

char *cp = "Hiya"; // null-terminated array char c_array[] = "World!!!!"; // null-terminated char no_null[] = {'H', 'i'}; // not null-terminated string s1(cp); // s1 == "Hiya" string s2(c_array, 5); // s2 == "World" string s3(c_array + 5, 4); // s3 == "!!!!" string s4(no_null); // runtime error: no_null not null-terminated string s5(no_null, 2); // ok: s5 == "Hi"

特殊的一些函数：

string s("hello world"); // return substring of 5 characters starting at position 6 string s2 = s.substr(6, 5); // s2 = world string s3=s.append("!!!!"); // s3= hello world!!!! int i=s.find("world"); //i=6 是world第一次出现的下标，没有找到会返回-1 string kong(" "); int j = s.find_first_of(kong);//j为5，查找第一次出现kong内字符的位置

例题1:搜索字符串内的数字和字母：

int main() { int x = 0, y = 0, z = 0; string k = ("ab2c3d7R4E6"); string num = ("0123456789"); string ar = ("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"); int a1[100]; int a2[100]; while (1) { z = k.find_first_of(num, z); //find_first_of函数要求z<k.size()-1，即z小于最后一个元素的下标！！ cout << "下标为：" << z << "值为：" << k[z] << endl; if ((z >= k.size()-2)||z==-1) { break; } ++z; } z = 0; cout << endl; while (1) { z = k.find_first_of(ar, z); //z<k.size()-1 cout << "下标为：" << z << "值为：" << k[z] << endl; if ((z >= k.size() - 2) || z == -1) { break; } ++z; } cout << endl; cout << k.size(); }

例题2：查找单词个数，与最长最短单词

//单词分隔符号为空格的时候 int main() { string line1 = "We were her pride of 10 she named us:"; string line2 = "Benjamin, Phoenix, the Prodigal"; string line3 = "and perspicacious pacific Suzanne"; string sentence = line1 + ' ' + line2 + ' ' + line3; string temps; int counter = 0; int max = 0; int min = 9999; stringstream ss(sentence); while (ss >> temps) { ++counter; if (temps.size() > max) { max = temps.size(); } if (temps.size() < min) { min = temps.size(); } } cout << "单词数为：" << counter << endl; stringstream sss(sentence); while (sss >> temps) { if (temps.size() == max) { cout << "最长单词为：" << temps << endl; } if (temps.size() == min) { cout << "最短单词为：" << temps << endl; } } } //单词分隔符号任意（可为，:\t\n的时候) int main() { string line1 = "We were her pride of 10 she named us:"; string line2 = "Benjamin, Phoenix, the Prodigal"; string line3 = "and perspicacious pacific Suzanne"; string sentence = line1 + ' ' + line2 + ' ' + line3; string temps; vector<string> maxs; vector<string> mins; int max = 0, min = 9999; int counter = 0; int wordlen; int start = 0, end = 0; string fenge(" ,.\t\n\\"); while (1) { start = sentence.find_first_not_of(fenge, end); //start是从结束坐标开始第一个不是分隔符的元素下标 ++counter; end = sentence.find_first_of(fenge, start);//end变为单词末尾的下一个分隔符下标 if (end == -1) { break; } wordlen = end - start; if (wordlen > max) { maxs.clear(); temps.assign(sentence.begin() + start, sentence.begin() + end); maxs.push_back(temps); max = wordlen; } else if (wordlen == max) { temps.assign(sentence.begin() + start, sentence.begin() + end); maxs.push_back(temps); } if (wordlen < min) { mins.clear(); temps.assign(sentence.begin() + start, sentence.begin() + end); mins.push_back(temps); min = wordlen; } else if (wordlen == min) { temps.assign(sentence.begin() + start, sentence.begin() + end); mins.push_back(temps); } if (start > sentence.size() - 2 || end > sentence.size() - 2) { break; } } cout <<"单词数目为：" <<counter << endl; for (vector<string>::iterator iter = maxs.begin(); iter != maxs.end(); iter++) { cout << "最长的单词为" << *iter << endl; } for (vector<string>::iterator iter = mins.begin(); iter != mins.end(); iter++) { cout << "最短的单词为" << *iter << endl; } }

容器适配器

除了顺序容器，标准库还提供了三种顺序容器适配器：queue、priority_queue和stack 一、什么是容器适配器： 容器适配器让一种已存在的容器类型采用另一种 不同的抽象类型的工作方式实现。例如，stack（栈）适配器可使任何一种顺序容器以栈的方式工作。

deque<int> deqint; stack<int> stk(deqint);// 用deqint容器初始化一个新的栈 stack<string, vector<string>> string_stk; //在vector的基础上覆盖空栈

实现： 1、默认的 stack 和 queue 都基于 deque 容器实现 2、默认的priority_queue 则在 vector 容器上实现。 有以下规则： 1、stack 栈可以建立在 vector、list 或者 deque 容器之上。 2、queue 适配器要求其关联的基础容器 必须提供 push_front 运算，因此只能建立在 list 容器上(此处我认为deque也可以，书上的表述应该不清楚)，而不能建立在 vector 容器上。 3、priority_queue 适配器要求提供随机访问功能，因此可建立在 vector 或 deque 容器上，但不能建立在 list 容器。

二、栈适配器stack 先进后出

int main() { const int size = 10; stack<int> sta_int; int i = 0, j = 1; while (sta_int.size() != size) { int tem = j; sta_int.push(j); //元素压栈 j += i; i = tem; } while (!sta_int.empty()) { int val = sta_int.top(); //读出栈顶元素 sta_int.pop(); //删除栈顶元素，完成栈顶出栈过程 cout << val << ends; } }

三、适配器队列和优先级队列 queue标准队列：先进先出，新进的元素在队尾； priority_queue优先级队列：用户为队列设置优先级，新进入的元素比较优先级，将自己放在比他低优先级的元素前面；

四、关于这几个适配器的应用实例 1、stack应用：括号匹配

//遇到左括号的时候将其标记，遇到右括号时弹出括号间的元素 int main() { stack<char> sta_char; string exp; cin >> exp; string::iterator iter = exp.begin(); while (iter != exp.end()) { if (*iter == '(') { ++iter; while (*iter != ')') { sta_char.push(*iter); ++iter; } while (!sta_char.empty()) { cout << sta_char.top()<<ends; sta_char.pop(); } sta_char.push('#');//表示表达式已经弹出 } ++iter; } }

2、queue的应用：图的广度优先遍历

//无向图的广度优先遍历 #include<iostream> #include<queue> using namespace std; #define MAX 20 int map[MAX][MAX]; int arr[MAX] = { 0 }; //标记是否已经被访问 void bfs(int n) //图的广度优先遍历 { int top; queue<int> que; arr[0] = 1; cout << 1 << ends; for (int i = 0; i < n; i++) { if (map[0][i] == 1 && arr[i] == 0) //从第0个顶点开始入队联通且没有被标记的点 { que.push(i); arr[i] = 1; } } while (!que.empty()) { top = que.front(); que.pop(); cout << top+1 << ends; for (int i = 0; i < n; i++) { if (map[top][i] == 1 && arr[i] == 0) { que.push(i); arr[i] = 1; } } } } int main() { int vex, edge, x, y; cin >> vex >> edge; for (int i = 0; i < MAX; i++) { for (int j = 0; j < MAX; j++) map[i][j] = 0; } for (int i = 0; i < edge; i++) { cin >> x >> y; map[x-1][y-1] = map[y-1][x-1] = 1; } bfs(vex); }

3、最高奖励问题：

//有N个任务，每个任务有一个最晚结束时间以及一个对应的奖励。 //在结束时间之前完成该任务，就可以获得对应的奖励。完成每一个任务所需的时间都是1个单位时间。 //有时候完成所有任务是不可能的，因为时间上可能会有冲突，这需要你来取舍。 //求能够获得的最高奖励。 //input:第1行：一个数N，表示任务的数量(2 <= N <= 50000) //第2 - N + 1行，每行2个数，中间用空格分隔，表示任务的最晚结束时间E[i]以及对应的奖励W[i]。 //(1 <= E[i] <= 10 ^ 9，1 <= W[i] <= 10 ^ 9) #include<iostream> #include<queue> #include<algorithm> using namespace std; struct r{ int e, w; friend bool operator< (r a, r b) //定义了比较方式之后，优先级队列的算符也会改变 { return a.w>b.w; //将价值最低的放在top用以替换 } }; //分析一波：每个任务完成需要一个单位时间。那么不妨先将任务按结束时间排序。 //依次遍历每个任务，如果当前时间足够完成该任务，则加入队列，如果冲突，则比较队列中价值最小的元素， //如果该任务价值高，则替换之。 int cmp(r a, r b) //sort 函数的从小到大排序 { if (a.e < b.e) { return true; } else return false; } int main() { r p[20]; int N; cin >> N; for (int i = 0; i < N; i++) { cin >> p[i].e >> p[i].w; } //建立一个优先级队列，将结束时间晚的放到最后，争取利益最大化 priority_queue<r> pro_que; sort(p, p + N, cmp); //先把所有任务按时间排序（从小到大） for (int i = 0; i < N; i++) { if (pro_que.size() < p[i].e) //如果当前队列执行完的时间小于 任务的结束时间（任务未结束） { pro_que.push(p[i]); //按照任务价值排进优先级队列 } else if (p[i].w>pro_que.top().w) //如果当前时间等于任务结束的时间（即可以替换） { pro_que.pop(); pro_que.push(p[i]); } } long ans = 0; while (!pro_que.empty()) { ans += pro_que.top().w; pro_que.pop(); } cout << ans; }