六、标准模板库(STL) … 2.向量(vector) … 2)迭代器 … begin() begin() const end() end() const rbegin() rbegin() const rend() rend() const - 反向只读终止迭代器 begin - 起始 end - 终止 没有const - 可写 const - 只读 没有r - 正向 r - 反向 正向迭代器：起始指向首元素，终止指向尾元素后，+向尾，-向首 反向迭代器：起始指向尾元素，终止指向首元素前，+向首，-向尾 代码：vec2.cpp
#include <vector> #include <iostream> using namespace std; void print(vector<int> const& vi) { for (vector<int>::const_iterator it = vi.begin(); it != vi.end(); ++it) cout << /*++*/*it << ' '; cout << endl; } void rprint(vector<int> const* vi) { /* for (vector<int>::const_iterator it = vi->end()-1; it != vi->begin()-1; --it) */ typedef vector<int>:: const_reverse_iterator CRIT; for (CRIT it = vi->rbegin(); it != vi->rend(); ++it) cout << *it << ' '; cout << endl; } int main(void) { vector<int> v1; v1.push_back(10); v1.push_back(20); v1.push_back(30); vector<int>::iterator it1 = v1.begin(); cout << *it1 << endl; // 10 ++*it1; cout << *it1 << endl; // 11 cout << *++it1 << endl; // 20 cout << ++*++it1 << endl; // 31 cout << *----it1 << endl; // 11 cout << *(it1 += 2) << endl; // 31 it1 = v1.end(); cout << *(it1 - 1) << endl; // 31 vector<int>::iterator it2 = v1.begin(); cout << boolalpha << (it1 > it2) << endl; // true cout << (it1 - it2) << endl; // 3 vector<int>::reverse_iterator it3 = v1.rbegin(), it4 = v1.rend(); cout << *it3 << endl; // 31 cout << *(it4 - 1) << endl; // 11 cout << (it4 > it3) << endl; // true cout << (it4 - it3) << endl; // 3 vector<int>::const_iterator it5 = v1.begin(); cout << *it5 << endl; //*it5 = 10; vector<int>::const_reverse_iterator it6 = v1.rbegin(); cout << *it6 << endl; // 31 //(*it6)--; *it6--; vector<int> const& cr = v1; //it1 = cr.begin(); it5 = cr.begin(); vector<int> const* cp = &v1; //it3 = cp->rbegin(); it6 = cp->rbegin(); print(v1); rprint(&v1); return 0; }注意：任何可能导致向量内存结构发生变化的操作，比如push_back，都可能引起之前获得的迭代器失效，即迭代器内部保存的元素地址不能反映改变以后的状态，为了安全起见，最好在使用这些迭代器之前，更新一次，以获得最新的内存地址。 代码：vec3.cpp
#include <vector> #include <iostream> using namespace std; int main(void) { vector<int> vi; vi.push_back(100); vector<int>::iterator it = vi.begin(); cout << *it << endl; // 100 vi.push_back(200); it = vi.begin(); cout << *it << endl; return 0; }3)常用成员函数 front/back push_back/pop_back 没有push_front和pop_front insert/erase clear/size/resize/empty 特征迭代器函数族 代码：vec4.cpp
#include <vector> #include "print.h" int main(void) { vector<int> vi; vi.push_back(20); vi.push_back(30); vi.push_back(40); print(vi.begin(), vi.end()); //vi.push_front(10); vi.insert(vi.begin(), 10); print(vi.begin(), vi.end()); vi.erase(vi.begin() + 2); print(vi.begin(), vi.end()); vi.front() *= 2; vi.back() /= 2; print(vi.begin(), vi.end()); cout << vi.size() << endl; vi.resize(2); print(vi.begin(), vi.end()); vi.resize(4); print(vi.begin(), vi.end()); cout << boolalpha << vi.empty() << endl; vi.clear(); cout << vi.empty() << endl; vi.resize(5, 13); print(vi.begin(), vi.end()); return 0; }4)泛型算法 #include iterator find(iterator begin, iterator end, value_type const& key); 在[begin, end)区间内查找第一个和key匹配的元素，返回其迭代器，如果找不到则返回end。 代码：vec5.cpp
#include <vector> #include <algorithm> #include "print.h" int main(void) { int ai[] = {10, 20, 30, 20, 40, 20, 50, 20, 20}; vector<int> vi(ai, ai + sizeof(ai) / sizeof(ai[0])); print(vi.begin(), vi.end()); for(vector<int>::iterator it = vi.begin(); (it = find(it, vi.end(), 20)) != vi.end(); it = vi.erase(it)); print(vi.begin(), vi.end()); return 0; }void sort(iterator begin, iterator end); // < void sort(iterator begin, iterator end, less cmp) // 比较器 代码：vec6.cpp
#include <vector> #include <algorithm> #include "print.h" bool cmp(int const& a, int const& b) { return a > b; } class Cmp { public: bool operator()(int const& a, int const& b) const { return a > b; } }; class Integer { public: Integer(int const& data = 0) : m_data(data) {} operator int&(void) { return m_data; } operator int const&(void) const { return static_cast<int&>( const_cast<Integer&>(*this)); } private: int m_data; }; int main(void) { int ai[] = { 11, 19, 17, 13, 29, 21, 23}; vector<int> vi(ai, ai + sizeof(ai) / sizeof(ai[0])); print(vi.begin(), vi.end()); //sort(vi.begin(), vi.end()); //sort(vi.begin(), vi.end(), cmp); //sort(vi.begin(), vi.end(), Cmp()); sort(vi.rbegin(), vi.rend()); print(vi.begin(), vi.end()); vector<Integer> vn( vi.begin(), vi.end()); print(vn.begin(), vn.end()); sort(vn.begin(), vn.end()); print(vn.begin(), vn.end()); //sort(vn.begin(), vn.end(), cmp); //sort(vn.begin(), vn.end(), Cmp()); sort(vn.rbegin(), vn.rend()); print(vn.begin(), vn.end()); return 0; }5)类类型元素 如果用自己定义的类作为向量元素的类型，通常需要满足一下条件： 缺省构造函数、深拷贝语义的拷贝构造函数和拷贝赋值运算符函数，如果涉及排序还需要支持小于号运算符，或者用比较器替代，如果涉及查找则需要支持相等性判断运算符。 代码：vec7.cpp
#include <vector> #include <algorithm> #include "print.h" class A { public: A(void) { cout << "缺省构造：" << this << endl; } A(A const& that) { cout << "拷贝构造：" << &that << "->" << this << endl; } ~A(void) { cout << "析构函数：" << this << endl; } A& operator=(A const& rhs) { cout << "拷贝赋值：" << &rhs << "->" << this << endl; return *this; } bool operator==(A const& rhs) const { return true; } /* bool operator<(A const& rhs) const { return this; } */ }; class Cmp { public: bool operator()(A const& x, A const& y) const { return true; } }; int main(void) { cout << "------ 1 ------" << endl; vector<A> v1; cout << "------ 2 ------" << endl; vector<A> v2(3); cout << "------ 3 ------" << endl; v2.erase(v2.begin()); cout << "------ 4 ------" << endl; v2.push_back(A()); cout << "------ 5 ------" << endl; v2.push_back(A()); cout << "------ 0 ------" << endl; find(v2.begin(), v2.end(), A()); //sort(v2.begin(), v2.end()); sort(v2.begin(), v2.end(), Cmp()); return 0; }3.双端队列(deque) 相比于向量，增加了在首部压入和弹出数据元素的接口： push_front/pop_front 同时去掉了获取容器容量的接口：capacity 连续内存、动态管理、下标访问、随机迭代。运行效率略逊于向量，但是优于列表，通常可以作为缺省容器。 代码：deque.cpp
#include <deque> #include <algorithm> #include <iostream> using namespace std; void print1(deque<string> const& ds) { size_t size = ds.size(); for (size_t i = 0; i < size; ++i) cout << '[' << ds[i] << ']'; cout << endl; } void print2(deque<string> const& ds) { typedef deque<string>:: const_iterator CIT; for (CIT it = ds.begin(); it != ds.end(); ++it) cout << '[' << *it << ']'; cout << endl; } int main(void) { deque<string> ds; ds.push_back("北京"); ds.push_back("天津"); ds.push_front("上海"); ds.push_front("重庆"); print1(ds); print2(ds); ds.pop_front(); print1(ds); ds.pop_back(); print2(ds); deque<string>::iterator it = find( ds.begin(), ds.end(), "北京"); if (it != ds.end()) ds.erase(it); print1(ds); ds.resize(5); print2(ds); ds[1] = "广州"; ds[2] = "西安"; ds[3] = "南京"; ds[4] = "吉林"; print1(ds); ds[5] = "长沙"; print2(ds); cout << ds[5] << endl; cout << *ds.end() << endl; ds.push_back("武汉"); print1(ds); sort(ds.begin(), ds.end()); print2(ds); sort(ds.rbegin(), ds.rend()); print1(ds); //cout << ds.capacity() << endl; return 0; }4.列表(list) 链式存储结构(双向线性链表)，内存不连续，不支持下标访问，顺序迭代器。在任意位置增删元素效率非常高。 void unique(void); 唯一化连续的重复元素。 void sort(void); 排序。全局泛型sort函数只能用于支持随机访问迭代器的容器：向量和双端队列，而对于那些只支持顺序访问迭代器的非连续内存容器，如列表等，需要使用成员函数sort实现排序。 void splice(iterator pos, list& l2); l1.splice(pos, l2); 将l2列表中全部元素剪切到l1列表的pos之前。 void splice(iterator pos, list& l2, iterator del); l1.splice(pos, l2, del); 将l2列表中del所指向的元素剪切到l1列表的pos之前。 void splice(iterator pos, list& l2, iterator begin, iterator end); l1.splice(pos, l2, begin, end); 将l2列表中[begin,end)区间内的元素剪切到l1列表的pos之前。 l1：有序 l2：有序 l1.merge(l2); 将l2列表中的全部元素剪切到l1列表的适当位置，保持结果有序。 代码：list.cpp
#include <list> #include <algorithm> #include "print.h" class Cmp { public: bool operator()(int const& a, int const& b) const { return a > b; } }; int main(void) { list<int> l1; l1.push_back(10); l1.push_back(20); l1.push_back(30); l1.push_back(40); l1.push_back(50); print(l1.begin(), l1.end()); //cout << l1[1] << endl; //cout << *(l1.begin() + 1) << endl; cout << *++l1.begin() << endl; list<int>::iterator it = l1.begin(); l1.insert( l1.insert(it, 10), 10); l1.insert( l1.insert(++++++it, 20), 20); it = l1.end(); l1.insert( l1.insert(--it, 40), 40); print(l1.begin(), l1.end()); l1.unique(); print(l1.begin(), l1.end()); //sort(l1.begin(), l1.end()); l1.sort(); print(l1.begin(), l1.end()); l1.unique(); print(l1.begin(), l1.end()); list<int> l2; for (int i = 1000; i < 6000; i += 1000) l2.push_front(i); cout << "l1: " << flush; print(l1.begin(), l1.end()); cout << "l2: " << flush; print(l2.begin(), l2.end()); list<int>::iterator pos = l1.end(); //l1.splice(----pos, l2); //l1.splice(----pos, l2, // ++++l2.begin()); l1.splice(----pos, l2, ++l2.begin(), --l2.end()); cout << "l1: " << flush; print(l1.begin(), l1.end()); cout << "l2: " << flush; print(l2.begin(), l2.end()); l1.clear(); l1.push_back(400); l1.push_back(700); l1.push_back(800); l2.clear(); l2.push_back(200); l2.push_back(300); l2.push_back(500); l2.push_back(600); l2.push_back(900); l1.sort(Cmp()); l2.sort(Cmp()); cout << "l1: " << flush; print(l1.begin(), l1.end()); cout << "l2: " << flush; print(l2.begin(), l2.end()); l1.merge(l2, Cmp()); cout << "l1: " << flush; print(l1.begin(), l1.end()); cout << "l2: " << flush; print(l2.begin(), l2.end()); return 0; }5.堆栈、队列和优先队列 适配器容器<元素类型, 底层容器类型> stack: 后进先出 push -> push_back pop -> pop_back top -> back size -> size clear -> clear empty -> empty 底层容器：vector/[deque]/list queue: 先进先出 push -> push_back pop -> pop_front back -> back front -> front size -> size clear -> clear emtpy -> empty 底层容器：[deque]/list priority_queue: "大"者先出 底层容器：vector/[deque] 代码：adp.cpp
#include <vector> #include <list> #include <stack> #include <queue> #include <iostream> using namespace std; class Cmp { public: bool operator()(int const& a, int const& b) const { return a > b; } }; int main(void) { stack<int, vector<int> > si; si.push(10); si.push(20); si.push(30); while (! si.empty()) { cout << si.top() << ' '; si.pop(); } cout << endl; queue<int, /*vector*/list<int> > qi; qi.push(10); qi.push(20); qi.push(30); while (! qi.empty()) { cout << qi.front() << ' '; qi.pop(); } cout << endl; // priority_queue<int, // vector<int> > pi; priority_queue<int, /*list*/vector<int>, Cmp> pi; pi.push(40); pi.push(10); pi.push(50); pi.push(20); pi.push(30); while (! pi.empty()) { cout << pi.top() << ' '; pi.pop(); } cout << endl; return 0; }6.映射、多重映射、集合、多重集合 键——值对的容器 键必须唯一 关于键的平衡有序二叉树（红黑）
8 / \ 4 12 / \ / \ 2 6 10 14 1 \ 2 \ 3 \ 4 3 / \ 2 4 / \ 1 5检索性能：O(logN)，与二分法相当 支持以键作为参数的下标运算符：增加、读取、修改 键都是只读 用pair<键类型, 值类型>容器作为键值对的封装。 first - 键 second - 值 值的类型必须提供缺省构造函数，键的类型必须提供小于号运算符或提供相应类型的比较器。 代码：map.cpp
#include <map> #include <iostream> using namespace std; class A { public: A(int arg) : m_var(arg) {} /* bool operator< (A const& rhs) const { return m_var < rhs.m_var; } */ private: int m_var; friend class Cmp; }; class B { public: B(int arg = 0) : m_var(arg) {} int m_var; }; class Cmp { public: bool operator()(A const& x, A const& y) const { return x.m_var < y.m_var; } }; int main(void) { map<string, int> m1; m1.insert(pair<string, int>( "壹", 1)); m1.insert(make_pair( "贰", 2)); m1["叁"] = 3; typedef map<string, int>::iterator IT; for (IT it = m1.begin(); it != m1.end(); ++it) { cout << it->first << "->" << it->second << endl; } cout << m1["贰"] << endl; m1["贰"] = 20; cout << m1["贰"] << endl; IT it = m1.begin(); cout << it->first << "->" << it->second << endl; it->second = 30; cout << it->second << endl; //it->first = "三"; m1.erase(it); m1["三"] = 3; for (IT it = m1.begin(); it != m1.end(); ++it) { cout << it->first << "->" << it->second << endl; } //cout << m1["肆"] << endl; it = m1.find("肆"/*"壹"*/); if (it == m1.end()) cout << "\"肆\"不存在！" << endl; else cout << it->first << "->" << it->second << endl; map<A, B, Cmp> m2; A a(100); B b(200); m2[a] = b; cout << m2[a].m_var << endl; //m1["三"] = 30; pair<IT, bool> res = m1.insert( make_pair("三十", 30)); if (res.second == false) cout << "插入失败！" << endl; else cout << "插入成功：" << res.first->first << "->" << res.first->second << endl; for (IT it = m1.begin(); it != m1.end(); ++it) { cout << it->first << "->" << it->second << endl; } return 0; }多重映射就是允许键重复的映射。 代码：mmap.cpp
#include <map> #include <iostream> using namespace std; int main(void) { multimap<string, int> mmap; mmap.insert(make_pair("张飞", 80)); mmap.insert(make_pair("赵云", 70)); mmap.insert(make_pair("关羽", 60)); mmap.insert(make_pair("张飞", 90)); mmap.insert(make_pair("赵云", 80)); mmap.insert(make_pair("关羽", 70)); typedef multimap<string, int>:: iterator IT; for (IT it = mmap.begin(); it != mmap.end(); ++it) cout << it->first << "->" << it->second << endl; cout << "--------" << endl; pair<IT, IT> its = mmap.equal_range( "张飞"); for (IT it = its.first; it != its.second; ++it) cout << it->first << "->" << it->second << endl; return 0; }集合就是没有值只有键的映射。 多重集合就是没有值只有键的多重映射。 代码：set.cpp
#include <set> #include <iostream> using namespace std; int main(void) { set<int> s1; s1.insert(10); s1.insert(20); s1.insert(30); s1.insert(20); s1.insert(10); for (set<int>::iterator it = s1.begin(); it != s1.end(); ++it) cout << *it << ' '; cout << endl; multiset<int> s2; s2.insert(10); s2.insert(20); s2.insert(30); s2.insert(20); s2.insert(10); for (multiset<int>::iterator it = s2.begin(); it != s2.end(); ++it) cout << *it << ' '; cout << endl; }