0. 前言
由于自己使用Python居多,对C++并不太熟悉,但是最近在刷算法题,所以这里简单整理总结一下C++常用数据结构的操作函数,以便方便查阅检索。
1. C++标准库常用数据结构
常用数据结构如下:
- string
- vector
- list
- queue和priority_queue
- set
- map
- stack
2. 常用数据结构操作示例
1. string
//header file : <string>
//declaration
string s = "hello world!";
// visit by subscript
char c = s[2];//l
const char cc = s.at(6);//w
// get the length of the string
int length = s.length();//12
int size = s.size();//12
// the string is empty or not
bool is_empty = s.empty();//0
// concat strings
string t = "c++";
s.append(t);//hello world!c++
s += "Python!";//hello world!c++Python!
// get substring
string sub_str = s.substr(0, 5);//hello
// find substring
int pos = s.find("world");//6
// insert operation
s.insert(0, "Hi!");//Hi!hello world!c++Python!
// compare operation
string other = "NLP";
bool cmp = other < s;//0
// visit element by iterator
for (auto i: s) {
cout << i << endl;
}
2. vector
// header file :<vector>
// declaration
vector<int> vec {2, 3, 4}; //[2, 3, 4]
// size of vector
int size = vec.size(); //3
// the vector is empty or not
bool is_empty = vec.empty(); // 0
// visit by subscript
auto e = vec.at(2);//4
int m = vec[1];//3
cout << e << m << endl;
// append element at back
vec.push_back(5); // [2, 3, 4, 5]
// delete the last element
vec.pop_back();//[2, 3, 4]
// insert an element by iterator
vec.insert(vec.begin(), 1); //[1, 2, 3, 4]
// visit the first element and the last element
cout << vec.front() << vec.back() << endl; // 14
// visit by iterator
auto iter = vec.begin();
while (iter != vec.end()) {
cout << *iter << endl;
iter += 1;
}
// delete element by iterator
auto item = vec.erase(vec.end() -2);
cout << *item << endl;//4
for (auto i: vec) {
cout << i << endl;
}
3. queue
// header file: <queue>
//declaration, can't initiate with assignment statement.
queue<int> que;
// add element to the back of queue
for (int i = 0; i < 3; i++) {
que.push(i);
} //que: {0, 1, 2}
// get the size of queue
int size = que.size();//3
// if the queue is empty or not
bool is_empty = que.empty();//0
// delete the element at the first position
que.pop();//que: {1, 2}
// get the first element
auto first = que.front();//1
// get the last element
auto last = que.back();//2
cout << first << last << endl;
4. map
//header file :<map>
//declaration
map<int, int> m;
//add element to map
for (int i = 0; i < 3; i++) {
m[i] = i + 2;
}
m.insert({5, 8});
//visit the element by auto+for
for (auto i: m) {
printf("%d : %d\n", i.first, i.second);
}
//whether the map is empty or not
bool is_empty = m.empty();//0
//get the size of map
int size = m.size();//4
// get the count of element
int count = m.count(2);//1
// search item by key
auto item = m.find(count);
printf("%d : %d\n", item->first, item->second);
// if not find, the value would equal to map.end()
auto ss = m.find(9);
cout << (ss == m.end()) << endl;//1
// get element by [] operator
int sk = m[10];//0 if the key not exists, then init
cout << sk << endl;//0
map<string, string> str_map;
str_map.insert({"hello", "world"});
cout << "begin" << str_map["python"] << "end" << endl;//beginend
5. set
// header file :<set>
// declaration
set<int> ss;
// insert element
ss.insert(3);
// whether element is in the set or not
bool is_in = ss.count(4);//0
// get the size fo set
int size = ss.size();//1
// whether the set is empty or not
bool is_empty = ss.empty();//0
cout << is_in << size << is_empty << endl;
6. stack
// header file: <stack>
//declaration
stack<int> stk;
// insert element
stk.push(3);
stk.push(4);
// get the top element
int top = stk.top();//4
// get the size of stack
int size = stk.size();//2
// out of the stack, no return
stk.pop();
cout << top << size << stk.top() << endl;//423
7. list
//header file: <list>
//declaration
list<int> lst;
// add element at back
lst.push_back(4);//{4}
lst.push_back(5);//{4, 5}
// add element at front
lst.push_front(3);//{3, 4, 5}
for (auto i: lst) {
cout << i << endl;
}
// get the size of list
int size = lst.size();//3
// delete element, the iterator of list doesn't implement the + or - operator
// since C++17, we can use advance(lst.begin(), 2) to get the iterator of specific position easily
lst.erase(++lst.begin());//{3, 5}
printf("front:%d, back:%d", lst.front(), lst.back());//front:3, back:5
8. priority_queue
priority_queue
并没有提供迭代器访问,只可以访问top
元素。
//header file: <queue>
//declaration
priority_queue<int> pq;
// push data to pq
for (int i = 1; i < 7; i++) {
pq.push(i);
}
// whether the pq is empty or not
bool is_empty = pq.empty();//0
// get the size of pq
int size = pq.size();//6
// get the top element
int top = pq.top();//6
// remove the top element
pq.pop();
cout << pq.top() << endl;//5