Common Data Structures and Methods in C++ STL

1. vector (Dynamic Array)

1.1 Include

#include<vector>

1.2 Creation

• Create an empty vector

vector<int> vct;

• Create a vector with a fixed length

vector<int> vct(10);

• Create a vector with a fixed length and initialize all elements with a given value

vector<int> vct(10, 1);

• Create a vector with specified elements

vector<int> vct{1, 2, 3, 4, 5};

• Create a vector using iterators

vector<int> tmp{1, 2, 3, 4, 5};
vector<int> vct(tmp.begin(), tmp.end());

1.3 Methods

• Append elements at the end: push_back, emplace_back

  push_back() creates a temporary object first, then copies or moves it to the container.
  emplace_back() (introduced in C++11) constructs the object directly at the end.

  vct.push_back(1);
  vct.emplace_back(1);

• Insert elements at a specific position: insert, emplace

  Similarly, emplace is a new feature in C++11.

  vct.insert(pos, val); // insert val at pos
  vct.insert(vct.begin()+2, 1); // insert 1 at index 2
  vct.insert(vct.begin()+2, 3, 1); // insert three 1s at index 2

• Remove the last element: pop_back

  vct.pop_back();

• Remove elements at a specific position: erase

  vct.erase(vct.begin()+2); // remove element at index 2
  vct.erase(vct.begin()+2, vct.begin()+5); // remove elements from index 2 to 4

• Clear the vector

  vct.clear();

2. stack

2.1 Include

#include<stack>

2.2 Construct a stack object

stack<int> st;

2.3 Methods

• Push onto stack: push

  st.push(1);
  st.emplace(1);

• Pop from stack: pop

  st.pop(); // void function, only removes the top

• Get the top element: top

  int a = st.top();

• Check if empty: empty

  if(!st.empty()){
      ...
  }

3. queue

3.1 Include

#include<queue>

3.2 Construct a queue object

queue<int> q;

3.3 Methods

• Enqueue: push, emplace

  q.push(1);
  q.emplace(1);

• Dequeue: pop

  q.pop();

• Get front and back: front, back

  int a = q.front();
  a = q.back();

4. deque (Double-ended Queue)

4.1 Include

#include<deque>

4.2 Construct a deque object

deque<int> dq;
deque<int> dq(len, val);

4.3 Methods

• Insert at front: push_front, emplace_front

  dq.push_front(1);
  dq.emplace_front(1);

• Insert at back: push_back, emplace_back

  dq.push_back(1);
  dq.emplace_back(1);

• Remove from front/back: pop_front, pop_back

  dq.pop_front();
  dq.pop_back();

• Access front/back: front, back

  int a = dq.front();
  int b = dq.back();

• Clear the deque

  dq.clear();

5. set

5.1 Include

#include<set>

5.2 Construct a set

set<int> s;

5.3 Methods

• Insert elements: insert, emplace

  s.insert(1);
  s.emplace(1);

• Remove elements: erase

  s.erase(1); // remove element with value 1

• Find elements: count, find

  if(s.count(1)){ // returns 1 if exists, otherwise 0
      ...
  }
  if(s.find(1) != s.end()){ // returns iterator if exists, otherwise end()
      ...
  }

• Clear the set

  s.clear();

6. map (Key-Value Mapping)

6.1 Include

#include<map>

6.2 Construct

map<char, int> mp;

6.3 Methods

• Insert elements: insert, emplace

  mp.insert(pair<char, int>('a', 1));
  mp.emplace('a', 1);

中文原文

C++的STL库常用数据结构及方法

1. vector可变数组

1.1 引入

#include<vector>

1.2 创建

• 创建空vector

vector<int> vct;

• 创建一定长度的vector

vector<int> vct(10);

• 创建一定长度的vector，并且给所有元素赋初始值

vector<int> vct(10, 1);

• 创建一个指定元素值的vector

vector<int> vct{1, 2, 3, 4, 5};

• 使用迭代器创建vector

vector<int> tmp{1, 2, 3, 4, 5};
vector<int> vct(tmp.begin(), tmp.end());

1.3 方法

• 向尾部添加元素push_back, emplace_back

  push_back()会先创建一个临时对象，然后复制或移动到容器尾部。emplace_back是C++ 11新引入的方法，直接在容器尾部创建这个对象。

  vct.push_back(1);
  vct.emplace_back(1);

• 向某一位置插入元素insert，emplace

  同理，emplace是C++ 11新特性

  vct.insert(pos, val);//在pos位置插入元素val
  vct.insert(vct.begin()+2, 1);//在下标为2处插入1
  vct.insert(vct.begin()+2, 3, 1);//在下标为2处插入3个1

• 删除尾部元素pop_back

  vct.pop_back();

• 删除指定位置的元素erase

  vct.erase(vct.begin()+2);//删除下标为2的元素
  vct.erase(vct.begin()+2, vct.begin()+5);//删除下标为2到4的元素

• 清空vector

  vct.clear();

2. stack栈

2.1 引入

#include<stack>

2.2 构造stack对象

stack<int> st;

2.3 方法

• 入栈push

  st.push(1);
  st.emplace(1);

• 出栈pop

  st.pop();//void函数，仅出栈操作

• 获取栈顶top

  int a = st.top();

• 判空empty

  if(!st.empty()){
      ...
  }

3. 队列queue

3.1 引入

#include<queue>

3.2 构造queue对象

queue<int> q;

3.3 方法

• 入队push，emplace

  q.push(1);
  q.emplace(1);

• 出队pop

  q.pop();

• 获取队头、队尾元素front，back

  int a = q.front();
  a = q.back();

4. 双向队列deque

4.1 引入

#include<deque>

4.2 构造deque对象

deque<int> dq;
deque<int> dq(len, val);

4.3 方法

• 前端插入元素push_front，emplace_front

  dq.push_front(1);
  dq.emplace_front(1);

• 后端插入元素push_back，emplace_back

  dq.push_back(1);
  dq.emplace_back(1);

• 前后端出队pop_front，pop_back

  dq.pop_front();
  dq.pop_back();

• 访问元素front，back

  int a = dq.front();
  int b = dq.back();

• 清空clear

  dq.clear();

5. 集合set

5.1 引入

#include<set>

5.2 构造set

set<int> s;

5.3 方法

• 插入元素insert，emplace

  s.insert(1);
  s.emplace(1);

• 删除元素erase

  s.erase(1);//删除值为1的元素

• 查找元素count，find

  if(s.count(1)){//若存在则返回1，否则返回0
      ...
  }
  if(s.find(1) != s.end()){//若存在则返回迭代器，否则返回end()
      ...
  }

• 清空clear

  s.clear();

6. 键值映射map

6.1 引入

#include<map>

6.2 构造

map<char, int> mp;

6.3 方法

• 插入元素insert, emplace

  mp.insert(pair<char, int>('a', 1));
  mp.emplace('a', 1);