std::vector
动态数组,数组长度可变
方法:
push_back(i)在末尾加入一个元素ipop_back()把末尾元素弹出size()获取容器长度claer()清空容器内容(没有清理内存)insert(const_iterator position, InputIterator first, InputIterator last)往position位置后插入[first,last)的容器元素
重点l 清空内存的方法。
vector<int> v; vector<int>().swap(v);
(一) vector 基础使用
往vec中添加元素，然后用下标 遍历输出。
#include <iostream> #include <vector> using namespace std; int main() { vector<int> v; for(int i=1;i<=10;++i){ v.push_back(i*i); } for(int i=0;i<v.size();++i){ cout << v[i] << " "; } cout << endl; return 0; }
(二). 二维vector 使用
------注意空格,旧编译器无法过-------
构造 可变行 可变列。
vector<vector<T> > v2d (内无元素，只有能push_back后访问)
构造 n行 m列 , 组内元素都为0。
vector<vector<T> > v2d(n,vector<T>(m,0))
vector<vector<T> > v2d(n,vector<T>(n));
构造 n行 可变列。
vector<vector<T> > v2d(n,vector<T>())
构造 n行 1列 (因为默认初始值是一个空的一维vector)
vector<vector<T> > v2d(n);
错误示范:
vector<vector<int>> v2d; ------注意空格,旧编译器无法过-------
vector<vector<int> v2d(10,0) ----无法用整形去初始化-----
#include <iostream> #include <vector> using namespace std; int main() { vector<vector<int> > v2d; for(int i=0;i < 5; ++i){ v2d.push_back(vector<int>()); } for(int i=0;i<v2d.size();++i){ for(int j=0;j<=i;++j){ v2d[i].push_back( (i+1) * (j+1) ); } } for(int i=0;i<v2d.size();++i){ for(int j=0;j<v2d[i].size();++j){ cout << i+1 << " * " << j+1 << " = " << v2d[i][j] << " "; } cout << endl; } return 0; }
1 * 1 = 1 2 * 1 = 2 2 * 2 = 4 3 * 1 = 3 3 * 2 = 6 3 * 3 = 9 4 * 1 = 4 4 * 2 = 8 4 * 3 = 12 4 * 4 = 16 5 * 1 = 5 5 * 2 = 10 5 * 3 = 15 5 * 4 = 20 5 * 5 = 25
(三). vector 的erase
earse 删除后返回的是 删除元素的下一位。(如果是最后一个元素，则返回 end（） )
小心删除后的 iter 是野指针，所以要重新从 earse
int x = 2; for(vector<int>::iterator iter=veci.begin(); iter!=veci.end(); ) { if( *iter == x) //删除iter，erase返回删除 iter的下一位 iter = veci.erase(iter); // 返回删除后剩下的那个元素。 else iter ++ ; //防止删除最后一个元素的时候,it++ }
等价于用remove.
veci.erase(remove(veci.begin(),veci.end(),2),veci.end());
std::set
集合，集合内元素不能重复，
迭代器遍历的顺序是从小到大(set 容器内元素 自动排序)
方法:
insert(i)向集合插入一个元素i O(logn)erase(i)删除元素i O(logn)count(i)统计元素i个数 O(logn)size()获取容器长度 O(1)clear()清空容器内容(清理内存) O(n)
(一). set 的使用实例
#include <iostream> #include <string> #include <set> using namespace std; int main() { set<string> country; country.insert("China"); country.insert("America"); country.insert("France"); set<string>::iterator it; for(it = country.begin();it!=country.end();++it){ cout << *it << " "; } cout << endl; country.erase("America"); country.erase("England");I } country.clear(); return 0; }
(二). set 内的排序定义。
如果要定义Set元素的比较规则,
则需要通过 重载 元素本身的比较操作符 来定义。
重要: 相等的时候要返回 false 否则 count() 将失效
确保重载函数每个出口都有返回值。
#include <iostream> #include <set> using namespace std; struct Point{ int x,y; bool operator<(const Point &rhs) const{//重载操作符 if(x == rhs.x){ return y < rhs.y; }else{ return x < rhs.x; } } }; int main() { int n; set<Point> v; cin >> n; for(int i=0;i<n;++i){ Point temp; cin >> temp.x >> temp.y; v.insert(temp); } for(set<Point>::iterator it = v.begin(); it != v.end(); ++it){ cout << it->x << " " << it->y << endl; } return 0; }
判断集合Cri 是否出现过
#include <iostream> #include <set> using namespace std; const int MAXN = 2e+5 + 1; const int MAXN2 = 1e4; int n,m; struct Cri{ Cri(int a,int b,int c) : x(a),y(b),z(c){} int x; int y; int z; bool operator<(const Cri &rhs) const{ if(x!=rhs.x) return x < rhs.x; if(y!=rhs.y) return y < rhs.y; if(z!=rhs.z) return z < rhs.z; return false; //相等不要忘记False,否则count会失效 } }; set<Cri> cri; int s[MAXN2]; int main(){ cin >> n >> m; int a,b,c; for(int i=0;i<n;++i){ cin >> a >> b >> c; cri.insert(Cri(a,b,c)); } for(int i=0;i<m;++i){ cin >> a >> b >> c; if(cri.count(Cri(a,b,c))) cout << "yes" << endl; else cout << "no" << endl; } return 0; }
std::map
映射表,key 与 value 有一对一的关系。
map 默认按照 key 从小到大 顺序排列 ( 容器内元素 自动排序)
std::map<char,int> first;std::map<char,int> second (first.begin(),first.end());std::map<char,int> third (second);std::map<char,int,classcomp> fourth;
insert(i)插入一对映射 O(logn)count(i)判断关键字是否存在 O(logn)erase(i)删除元素 O(logn)size()获取映射对个数 O(1)clear()清空容器(清理内存) O(n)
(一). map 的使用实例
#include <iostream> #include <string> #include <map> using namespace std; int main() { map<string,int> dict; dict["Tom"] = 1; dict["Jone"] = 2; dict["Mary"] = 1; if(dict.count("Mary")){ cout << "Mary is in class " << dict["Mary"]; dict["Mary"] = 5; } for(map<string,int>::iterator it = dict.begin();it != dict.end(); ++ it){ cout << it->first << " is in class " << it->second << endl; } dict.clear(); return 0; }
(二). map 的套用
类似二维vector。> > 之间的空格不能省略
map<int, set<string> > s
#include <iostream> #include <map> #include <string> using namespace std; int main() { map<int, map<string,int > > info; int n; cin >> n; for(int i=0;i<n;++i){ int class_id; string name; cin >> class_id >> name; info[class_id][name]++; } for(map<int, map<string,int> >:: iterator it1 = info.begin(); it1 != info.end(); it1++){ for(map<string,int>::iterator it2 = it1->second.begin(); it2 != it1->second.end();it2++){ cout << "There are " << it2->second << " people named " << it2->first << " in class " << it1->first << endl; } } return 0; }
(三) map 自动排序
按key排序
(1) 在声明时，将第cmp函数打包成直接调用的类。
(2) 如果key 是结构体，则可以 重载 operater < (const T &rhs) const {}
struct classcomp { bool operator() (const string& lhs, const string& rhs) const {return lhs<rhs;} }; map<string,int,classcomp> mp; //从小到大排序
按 value 排序，得用sort()
但是 sort 只能对 序列容器(线性的，例如：vector,queue,list ) 排序。
map虽然是一个集合容器，但是它不是线性存储的（比如红黑树）。
所以只能：
-
一是通过将 map 转换到序列容器，再用STL提供的sort方法得以实现的。
-
二是通过将 map 的 key 和 value 位置替换
typedef pair<string,int> pr; struct classcomp { bool operator() (const pr &lhs, const pr &rhs) const{ return lhs.second < rhs.second; } }; bool cmp (const pr &lhs, const pr &rhs){ return lhs.second < rhs.second; } map<string,int> mp; vector<pr> vec; for(map<string,int>::iterator it = mp.begin(); it != mp.end(); ++it){ vec.push_back(make_pair(it->first, it->second)); } sort(vec.begin(),vec.end(),classcomp()); //sort(vec.begin(),vec.end(),cmp );
#include <iostream> #include <map> #include <string> #include <vector> #include <algorithm> using namespace std; int n; map<string,map<string,int> > mp; typedef pair<string,map<string,int> > PR; bool cmp (const PR &lhs,const PR &rhs) { if(lhs.first != rhs.first) return lhs.first < rhs.first; } int main() { cin >> n; string f,p; int num; for(int i=0; i<n; ++i) { cin >> f >> p >> num; mp[p][f]+=num; } vector<PR> vec; for(map<string,map<string,int> >::iterator it = mp.begin(); it!=mp.end(); ++it) { vec.push_back(make_pair(it->first,it->second)); } sort(vec.begin(),vec.end(),cmp); for(int i=0; i<vec.size(); ++i) { cout << vec[i].first << endl; map<string,int> &pm = vec[i].second; for(map<string,int>::iterator it = pm.begin(); it != pm.end(); ++it) { cout << " |----" << it->first << "(" << it->second << ")" << endl; } } return 0; }