vector
- 可变长集合
- 根据源码，vector自身完全杜绝浅拷贝
- 初始化：
1
2
3
4
5
6
| vector<T> v1;
vector<T> v2(v1);
vector<T> v2 = v1;
vector<T> v3(n, val);
vector<T> v4{a, b, c};
vector<T> v5 = {a, b, c};
|
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
| vec.push_back(val);
vec.pop_back();
vec.empty();
vec.size();
vec.max_size();
vec.clear();
vec.front();
vec.back();
vec.begin();
vec.end();
vector<T>::reverse_iterator ritor = vec.rbegin();
vector<T>::reverse_iterator r_itor_2 = vec.rend();
vec[n];
v1 == v2;
vec.erase(pos);
vec.erase(pos_1, pos_2);
vec.insert(pos, val);
vec.insert(pos, n, val);
vec.insert(pos, beg, end);
for (auto &i : vec) {...}
vec_2.assign(vec.begin(), vec.end());
vec_2.assign(n, val);
swap(vec_1, vec_2); v1.swap(v2);
|
string
1
2
3
4
| string s1;
string s2 = s1;
string s3 = "2333";
string s4(10, 'c');
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| s.empty();
s.size();
s[n];
s1 + s2;
s.append("2333");
s.replace(11, 3, "123456");
s1 == s2; s1 != s2;
s1.compare(s2);
to_string(val);
stoi(str);
for (auto &c : s) {...}
|
1
2
3
4
5
6
7
8
9
10
11
| #include<cctype>
isalnum(c);
isalpha(c);
isdigit(c);
islower(c);
isupper(c);
ispunct(c);
isxdigit(c);
tolower(c);
toupper(c);
|
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
| const char *cp = "Hello World!!!";
char noNULL[] = { 'H', 'i', 'w', 'k' };
string str("233333333");
string s1(cp);
string s2(cp, n);
string s3(noNULL);
string s4(noNULL, n);
string s(str, pos);
string s(str, pos, len);
str.substr(pos, n);
s.insert(s.size(), 5, '!');
s.erase(s.size() - 5, 5);
const char *cp = "Stately, plump Buck";
s.assign(cp, 7);
s.insert(s.size(), cp + 7);
string s = "some string", s2 = "some other string";
s.insert(0, s2);
s.insert(0, s2, 0, s2.size());
string name("AnnaBelle");
auto pos1 = name.find("Anna");
string numbers("0123456789"), name("r2d2");
auto pos = name.find_first_of(numbers);
auto pos2 = name.find_first_of(numbers, 2);
|
list
参考博文
- 环形双向链表
- 但不能循环访问，头节点和尾节点之间有一个end()存在。
1
2
3
4
5
| list<int> test_cycle = { 1,2,3,4,5 };
auto itor = test_cycle.end();
itor = ++itor;
int res = *itor;
return 0;
|
1
2
3
4
5
| list<T> c0;
list<T> c1(3);
list<T> c2(5, 2);
list<T> c4(c2);
list<T> c5(c1.begin(), c1.end());
|
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
| c.begin();
c.end();
c.rbegin();
c.rend();
c.assign(n, num);
c.assign(beg, end);
c.front();
c.back();
c.empty();
c.size();
c.max_size();
c.clear();
c.insert(pos, num);
c.insert(pos, n, num);
c.insert(pos, beg, end);
c.erase(pos);
c.push_back(num);
c.pop_back();
c.push_front(num);
c.pop_front();
c.resize(n);
c.resize(n, num);
c.swap(c2); swap(c1, c2);
c1.merge(c2);
c1.merge(c2, comp);
bool comp(int first, int second) {
return first < second;
}
list<int> list1{ 1, 3, 5 };
list<int> list2{ 2, 4, 6 };
list1.merge(list2, comp);
c1.splice(c1.beg, c2);
c1.splice(c1.beg, c2, c2.beg);
c1.splice(c1.beg, c2, c2.beg, c2.end);
c1.remove(val);
c1.remove_if(comp);
bool comp(int val) {
return val > 5;
}
list<int> list1{ 1, 3, 5, 7, 9 };
list1.remove_if(comp);
c1.reverse();
c1.unique();
c.sort();
c.sort(comp);
bool comp(int val1, int val2) {
return n1 > n2;
}
c.sort(comp);
|
forward_list
- 单向链表，头文件 #include<forward_list>
- 成员函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| f.front();
f.begin();
f.end();
f.cbegin();
f.cend();
f.push_front(val);
f.insert_after(itor, val);
f.insert_after(pos_itor, temp_itor1, temp_itor2);
f.pop_front();
f.clear();
f.erase_after(itor);
f.erase_after(itor1, itor2);
|
deque
参考博文
-
vector是单向开口连续线性空间；deque是双向开口连续线性空间，允许常数时间内对头部插删。
-
deque迭代器并非普通指针，其复杂度高于vector。除非必要，否则应尽量使用vector。（deque的空间由一段一段的定量连续空间构成，deque采用一块map作为主控，这个map是一块连续空间，其中每个元素都是指针，指向另一段较大的连续空间，称为缓冲区。 参考博文）
-
对deque进行排序，应先复制到vector，排序，再复制回deque。
-
构造函数（顺序容器基本都差不多）：
1
2
3
4
5
| deque<T> a;
deque<T> a(10);
deque<T> a(10, 1);
deque<T> b(a);
deque<T> b(beg, end);
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| deq[n];
deq.front();
deq.back();
deq.size();
deq.max_size();
deq.resize();
deq.empty();
deq.push_front(val);
deq.push_back(val);
deq.insert(pos, val);
deq.insert(pos, n, val);
deq.insert(pos, pos1, pos2);
deq.pop_front();
deq.pop_back();
deq.erase(pos);
deq.erase(pos1, pos2);
deq.clear();
deq.assign(n, val);
deq.swap(deq2);
deq.begin();
deq.end();
deq.rbegin();
deq.rend();
|
-
顺序容器适配器：stack，queue，priority_queue。
-
适配器是一种机制，能使某种事物的行为看起来像另一种事物。
-
默认情况下stack和queue是基于deque实现的，priority_queue是基于vector实现的。
-
所有适配器都要求容器具有添加和删除元素的能力，因此适配器不能构造在array上。所有适配器都要求容器具有访问尾元素的能力，因此适配器不能构造在forward_list上。
-
stack可使用除array和forward_list外的任何容器进行构造；queue可构造在list和deque上，但不能构造在vector上；priority_deque需有随机访问的能力，因此可构造在vector和deque上，但不能构造在list上。
-
适配器虽构造于底层容器，但只能使用适配器本身的操作，不能使用底层容器的操作。
stack
- 栈，后进先出，无遍历行为，无迭代器，单口
- 常用操作：
1
2
3
4
5
6
7
8
9
| stack<T> s;
stack<T> s(c);
stack<T, vector<T>> str_stk;
s.empty();
s.pop();
s.size();
s.push(val);
s.top();
swap(a, b); a.swap(b);
|
queue
-
队列，先进先出，无遍历行为，无迭代器，双口
-
常用操作：
1
2
3
4
5
6
7
| queue<T> q;
q.push(val);
q.pop();
q.front();
q.back();
q.empty();
q.size();
|
priority_queue
- 优先级队列，自动排序，最高优先级的排在最前面（默认最大值）。多个元素具有相同优先级时，先来的排在前面。
- 无遍历行为，无迭代器
- 构造：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| priority_queue<T> pri_q;
priority_queue<int, vector<int>, greater<int>> pri_q;
priority_queue<int, vector<int>, less<int>> pri_q;
struct node {
int x;
bool operator<(const node& a) const {
return x < a.x;
}
};
priority_queue<node> pri_q;
struct compare {
bool operator()(const ListNode* l, const ListNode* r) {
return l->val > r->val;
}
};
priority_queue<ListNode*, vector<ListNode*>, compare> pri_q;
|
1
2
3
4
5
6
| pri_q.size();
pri_q.empty();
pri_q.push(val);
pri_q.pop();
pri_q.top();
pri_q.back();
|
heap
- 非STL基本容器，一般由vector构成，待后续整理。
关联式容器
map、set、multimap(关键字可重复)、multiset(关键字可重复)、unordered_map(哈希函数实现)、unordered_set(哈希函数实现)、unordered_multimap(哈希函数实现，关键字可重复)、unordered_multiset(哈希函数实现，关键字可重复)
-
set、map可用于去重。
-
关联容器没有头尾，只有最大最小值。因此不存在push_back()、push_front()、pop_back()、pop_front()。
-
关联容器的迭代器是双向迭代器，非随机访问迭代器。
-
map迭代器解引用是一个pair；set迭代器解引用是元素值
-
set：获取某元素的迭代器后，只能读不能写，即不可修改set中的元素值。
-
map：按键排序，元素为pair，键不允许重复。不可修改键，只能修改值。
-
使用迭代器遍历set、multiset、map、multimap时，迭代器默认按关键字升序遍历元素。
有关各容器排序实现，待整理重载后，继续整理！！！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| int main() {
vector<int> res_less;
map<int, char, less<int>> my_map;
my_map.insert({ 1, 'a' });
my_map.insert({ 2, 'b' });
my_map.insert({ 3, 'c' });
my_map.insert({ 4, 'd' });
my_map.insert({ 5, 'e' });
map<int, char, less<int>>::const_iterator citor = my_map.cbegin();
while (citor != my_map.cend()) {
res_less.push_back(citor->first);
++citor;
}
return 0;
}
|
- map元素获取
- pair: .first .second
- map迭代器: ->first ->second
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| map<string, int> my_map;
my_map.insert({ "1", 1 });
my_map.insert({ "2", 2 });
my_map.insert({ "3", 3 });
my_map.insert({ "4", 4 });
my_map.insert({ "5", 5 });
map<string, int>::iterator itor = ++my_map.begin();
string res1 = itor->first;
int res2 = itor->second;
pair<string, int> res3 = *itor;
string res4 = (*itor).first;
int res5 = (*itor).second;
return 0;
|
1
2
3
4
5
6
7
8
|
map<int, string> myMap;
myMap.insert(make_pair(1, "111"));
pair<map<int, string>::iterator, bool> res = myMap.insert(make_pair(1, "222"));
bool ret = res.second;
int key = res.first->first;
string value = res.first->second;
return 0;
|
-
对于容器中不存在的元素，map、unordered_map下标操作可将该元素添加到容器；vector等容器将报错异常。
因下标运算符可能插入一个新元素，因此只能对非const的map使用下标操作。
set类型不支持下标操作，无意义。
不能对multimap、unordered_multimap进行下标操作，存在重复值。
- 与list相同，增删元素后原迭代器仍有效。
- find查找元素：应使用关联容器自己的find方法(iter2 = iset.find(3)😉(结果若不存在，返尾后迭代器.end())，这会比STL提供的find方法快得多**(iter1 = find(iset.begin(), iset.end(), 3)😉**，因为STL提供的find方法是简单的循环搜索。
- 初始化
1
2
3
4
5
6
| set<string> exclude = {"the", "but", "and", "2333"};
map<string, int> word_count;
map<string, string> another = {{"Joyce", "James"}, {"Austen", "Jane"}, {"Dickens", "Charles"}};
set<int> iset(ivec.cbegin(), ivec.cend());
multiset<int> miset(ivec.cbegin() ivec.cend());
|
1
2
3
4
5
6
| pair<T1, T2> p;
pair<T1, T2> p(val_1, val_2);
pair<T1, T2> p = {val_1, val_2};
make_pair(val_1, val_2);
return pair<string, int> ();
return {"2333", 123};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
vector<int> ivec = {2, 4, 6, 8, 2, 4, 6, 8};
set<int> set2;
set2.insert(ivec.cbegin(), ivec.cend());
set2.insert({1, 3, 5, 7, 1, 3, 5, 7});
map<string, int> word_count;
word_count.insert({word, 1});
word_count.insert(make_pair(word, 1));
word_count.insert(pair<string, int>(word, 1));
c.insert(v);
c.emplace(args);
|
1
2
3
| c.erase(p);
c.erase(b ,e);
c.erase(k);
|
1
2
3
4
5
6
7
8
9
10
11
12
| set<int> iset = {0, 1, 2, 3, 4, 5};
iset.find(1);
iset.count(1);
c.lower_bound(k);
c.upper_bound(k);
c.equal_range(k);
|
杂货
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
| #include<string>
#include<vector>
#include<iostream>
using namespace std;
struct Gift
{
Gift() : name(""), price(0) {}
Gift(string name, int price) :name(name), price(price) {}
Gift(const Gift &gift) :name(gift.name), price(gift.price) {}
~Gift() {}
bool operator<(const Gift &gift) const {
return price < gift.price;
}
string name;
int price;
};
int main() {
vector<Gift> myVec;
myVec.reserve(20);
myVec.push_back(Gift("C++", 50));
myVec.emplace_back("Java", 40);
myVec.insert(myVec.begin() + 1, Gift("C#", 30));
myVec.emplace(myVec.begin() + 1, "Python", 20);
vector<Gift>::const_iterator itor = myVec.begin();
for (; itor != myVec.end(); ++itor) {
cout << (*itor).name << endl;
}
return 0;
}
|
