1 vector(向量)
vector是与数组相关的序列式容器,set模版类的定义在头文件<vector>中。当我们在程序中需要使用动态数组时, vector将会是理想的选择, vector可以在使用过程中动态地增长存储空间。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 vector <int > s;vector <int > s (n, 1 ) ;vector <int > s (first, last) ;vector <int > s = {1 ,7 ,3 ,6 ,5 ,6 };s[i] s.front() s.back() s.push_back(x) s.pop_back() s.size () s.empty() s.begin () s.end () s.insert(it, val); s.insert(s.begin ()+pos, val); s.insert(it, n, val); s.insert(it, first, last); s.erase(it) s.erase(first, last) s.reserve(n) s.resize(n) s.resize(n, val) s.clear () s.swap(v) s.assign(first, last) operator : > < >= <= == != s.insert(s.begin (), x) s.erase(s.begin ()) reverse(s.begin (), s.end ()) sort(s.begin (), s.end ()); return vector <int > {a, b};
2 pair(二元组)
pair用来表示一个二元组或元素对,定义在头文件<utility>中。pair模版类需要两个参数:首元素的数据类型和尾元素的数据类型。 pair模版类对象有两个成员: first和second,分别表示首元素和尾元素。
1 2 3 4 5 6 pair<double , double > p; p = make_pair(int , int ); operator : < > <= >= == !=
3 set(集合)
set是与集合相关的关联式容器,set模版类的定义在头文件<set>中。在set中每个元素的值都唯一,而且系统能根据元素的值自动进行排序(默认升序)。set中元素的值不能直接被改变。
标准库提供set关联容器分为:
按关键字有序保存元素:set(关键字即值,即只保存关键字的容器);multiset(关键字可重复出现的set);
无序集合:unordered_set(用哈希函数组织的set);unordered_multiset(哈希组织的set,关键字可以重复出现)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 set <T> s;set <T>::iterator it;int arr[]={0 ,1 ,2 ,3 };set <int > ss (arr, arr+4 ) ;set <int > ss (s) ;s.begin () s.clear () s.count(T) s.empty() s.end () s.equal_range(T) s.erase(T) s.find (T) s.get_allocator() s.insert(T) s.lower_bound(T) s.key_comp() s.max_size() s.rbegin() s.rend() s.size () s.swap(set <T>) s.upper_bound(T) s.value_comp() for (auto ptr = s.begin (); ptr != s.end (); ptr++) { cout << *ptr<< " " ; } struct cmp { bool operator () (const int & u, const int & v) const { if (abs (u - v) <= k) return false ; return u < v; } }; set <int , cmp> se;
4 string(字符串)
string类的定义在头文件< s t r i n g > <string> < s t r i n g > 中。string类其实可以看作是一个字符的vector, vector上的各种操作都可以适用于string,另外,string类对象还支持字符串的拼合、转换等操作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 string str;operator + char *p=(char *)str.c_str();char *p=(char *)str.data();cin >> str;cin .ignore();getline(cin , str); stringstream ss;ss<< str; ss>> str; vector <string > splitStr (const string & src, const string & delimiter) { vector <string > vetStr; if (src == "" || src == delimiter) { return vetStr; } if (delimiter == "" ) { vetStr.push_back(src); return vetStr; } string ::size_type startPos = 0 ; auto index = src.find (delimiter); while (index != string ::npos) { auto str = src.substr(startPos, index - startPos); if (str != "" ) { vetStr.push_back(str); } startPos = index + delimiter.length(); index = src.find (delimiter, startPos); } auto str = src.substr(startPos); if (str != "" ) { vetStr.push_back(str); } return vetStr; } isalpha (ch);isupper (ch);islower ();isdigit ();isalnum ();toupper ();tolower ();int stoi (const string & str, size_t * idx = 0 , int base = 10 ) ;long stol (const string & str, size_t * idx = 0 , int base = 10 ) ;unsigned long stoul (const string & str, size_t * idx = 0 , int base = 10 ) ;long long stoll (const string & str, size_t * idx = 0 , int base = 10 ) ;unsigned long long stoull (const string & str, size_t * idx = 0 , int base = 10 ) ;float stof (const string & str, size_t * idx = 0 ) ;double stod (const string & str, size_t * idx = 0 ) ;long double stold (const string & str, size_t * idx = 0 ) ;string to_string (T) ;str.find (tmp_str); str.find_first_of(tmp_str); str.find_last_of(tmp_str); str.find (tmp_str, pos); str.rfind(tmp_str); string substr (size_t pos = 0 , size_t len = npos) const ;transform(s.begin (),s.end (),s.begin (),::tolower ); transform(s.begin (),s.end (),s.begin (),::toupper );
5 list(列表)
list是由双向链表实现的,因此内存空间是不连续的。只能通过指针访问数据,所以list的随机存取非常没有效率,时间复杂度为O ( n ) O(n) O ( n ) ;但由于链表的特点,能高效地进行插入和删除。
使用:
需要高效的随机存取,而不在乎插入和删除的效率,使用vector;
如果需要大量的插入和删除,而不关心随机存取,则应使用list
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 list <int > l;list <int > l (n) ;list <int > l (n,val) ;list <int > l () ;list <int > l (first,last) ;l.begin () l.end () l.push_back(x) l.push_front(x) l.empty() l.resize(n) l.resize(n, val) l.clear () l.front() l.back() l.pop_back l.pop_front() l.assign() l.swap(ll) merge()
6 stack(栈)
stack模版类的定义在<stack>头文件中,stack模版类需要两个模版参数,一个是元素类型,另一个是容器类型,但是只有元素类型是必要的,在不指定容器类型时,默认容器的类型为deque。
1 2 3 4 5 6 7 8 9 stack <int > s;s.push(x); s.pop(); x = s.top(); s.empty(); s.size ();
7 queue(队列)
queue模版类的定义在头文件<queue>中。queue与stack相似, queue模版类也需要两个模版参数,一个元素类型,一个容器类型,元素类型是必须的,容器类型是可选的。
标准库提供queue分为:
queue(队列):queue从队首弹出,先入先出,并且queue只能从队首删除元素,但是两端都能访问。
deque(双向队列):可以访问两端并且可以在队首和队尾删除和插入元素
priority_queue(优先队列):优先队列与队列的差别在于优先队列不是按照入队的顺序出队,而是按照队列中元素的优先权出队列(默认为大者优先,也可以通过指定算子来指定自己的优先顺序);priority_queue模版类有三个模版参数,第一个是元素类型,第二个是容器类型,第三个是比较算子。其中后两者都可以忽略,默认容器为vector,默认算子为less,即小的往前排,大的往后排(出队列时列尾元素先出队)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 queue <int > q;q.push(x); q.pop(); q.front(); q.back(); q.empty(); q.size (); deque <int > dq; dq.empty(); dq.push_front(s); dq.push_back(s); dq.front(); dq.back(); dq.pop_front(); dq.pop_back(); dq.clear (); queue <int > empty;swap(empty, q); priority_queue<int > q; priority_queue<pair<int , int > > qq; priority_queue<int , vector <int >, greater<int > > qqq; q.empty() q.size () q.pop() q.top() q.push(x) class T { public : int x, y, z; T(int a, int b, int c) : x(a), y(b), z(c) {} }; bool operator < (const T &tOne, const T &tTwo){ return tOne.z < tTwo.z; } int main () { priority_queue<T> q; q.push(T(4 , 4 , 3 )); q.push(T(2 , 2 , 5 )); q.push(T(1 , 5 , 4 )); q.push(T(3 , 3 , 6 )); while (!q.empty()){ T t = q.top(); q.pop(); cout << t.x << " " << t.y << " " << t.z << '\n' ; } return 0 ; }
8 map(字典)
map是与字典相关的关联式容器,map模版类的定义在头文件< m a p > <map> < m a p > 中,用有序二叉树表存储类型为pair<const Key, T>的元素对序列。 序列中的元素以const Key部分作为标识, map中所有元素的Key值必须是唯一的,multimap则允许有重复的Key值。unordered_map是无序 map 容器。
将map可以通过一个Key值来快速决定一个元素,因此非常适合于需要按照Key值查找元素的容器。map模版类需要四个模版参数,第一个是键值类型,第二个是元素类型,第三个是比较算子,第四个是分配器类型。其中键值类型和元素类型是必要的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 map <string , int > m;m[key] = value; m.insert(make_pair(key, value)); int i = m[key]; map <string , int >::iterator it = m.find (key); m.erase(key); m.erase(it); m.size (); m.empty(); m.clear (); size_type count (const key_type& k) const ;
9 bitset()
bitset模版类的定义在<bitset>头文件中,用来方便地管理一系列的bit位类。 bitset除了可以访问指定下标的bit位以外,还可以把它们作为一个整数来进行某些统计。bitset模板类需要一个模版参数,用来明确指定含有多少位。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 const int MAXN = 32 ;bitset <MAXN> bt; bitset <MAXN> bt1 (0xf ) ; bitset <MAXN> bt2 (012 ) ; bitset <MAXN> bt3 ("1010" ) ; bitset <MAXN> bt4 (s, pos, n) ; bt.any() bt.none() bt.count() bt.size () bt[pos] bt.test(pos) bt.set () bt.set (pos) bt.reset() bt.reset(pos) bt.flip() bt.flip(pos) bt[pos].flip() bt.to_ulong() bt.to_string() os << bt
10 iterator(迭代器)
iterator(迭代器)是用于访问容器中元素的指示器,从这个意义上说, iterator(迭代器)相当于数据结构中所说的“遍历指针”,也可以把iterator(迭代器)看作是一种泛化的指针。每种STL容器都有自己的iterator(迭代器)子类。
11 algorithm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 max_element(v.begin (),v.end ()); min_element(v.begin (),v.end ()); sort(v.begin (), v.end (), cmp); bool cmp (int a, int b) { return a > b; } sort(v.begin (), v.end (), [](vector <int >& a, vector <int >& b) { return a[1 ] < b[1 ]; }); reverse(v.begin (), v.end ()); void * memset ( void * ptr, int value, size_t num ) ;fill (begin , last, val);memcpy (target, source, sizeof (int )*k);memcpy (target, source, sizeof (source));lower_bound(a, a+n, x); __gcd(int x, int y) accumulate(vect.begin (), vect.end (), 0 );
12 一些常量
name
expresses
value
INT_MIN
Minimum value for an object of type int
-32767
(− 2 1 5 -2^{15} − 2 1 5 +1) or less { -2147483647
(− 2 3 1 -2^{31} − 2 3 1 +1)}
INT_MAX
Maximum value for an object of type int
32767
(2 1 5 2^{15} 2 1 5 -1) or greater {2147483647
(2 3 1 2^{31} 2 3 1 -1)}
UINT_MAX
Maximum value for an object of type unsigned int
65535
(2 1 6 − 1 2^{16}-1 2 1 6 − 1 ) or greater {2 3 2 − 1 2^{32}-1 2 3 2 − 1 }
LLONG_MIN
Minimum value for an object of type long long int
-9223372036854775807
(− 2 6 3 + 1 -2^{63}+1 − 2 6 3 + 1 ) or less
LLONG_MAX
Maximum value for an object of type long long int
9223372036854775807
(2 6 3 − 1 2^{63}-1 2 6 3 − 1 ) or greater
ULLONG_MAX
Maximum value for an object of type unsigned long long int
18446744073709551615
(2 6 4 − 1 2^{64}-1 2 6 4 − 1 ) or greater
13 一些技巧
13.1 ++ 和–的小技巧
a++ 和 a 都是将 a 加 1,但是 a 返回值为 a,而 ++a 返回值为 a+1。如果只是希望增加 a 的值,而不需要返回值,则推荐使用 ++a,其运行速度会略快一些。
Life is painting a picture, not doing a sum.