vector

vector是变长数组，支持随机访问，不支持在任意位置O(1)插入。为了保证效率，元素的增删一般应该在末尾进行

声明

  1. #include <vector>   //头文件
  2. vector<int> a;      //创建一个名为a的动态int数组
  3. vector<int> b[10];  //创建第一维长10，第二位长度动态变化的int数组
  4. struct rec{};
  5. vector<rec> c;      //创建一个自定义结构体的动态数组

函数

  • size 返回vector长度
  • empty 返回vector是否为空
  • clear 清空vector
  • 迭代器
    • vector<int>::iterator it;
  • begin 返回vector第一个元素的迭代器
  • end 返回vector最后一个元素后面的迭代器
  • front 返回第一个元素
  • back 返回最后一个元素
  • push_back() 在vector末尾插入元素
  • pop_back() 删除vector最后一个元素

queue

头文件queue主要包括循环队列queue和优先队列priority_queue两个容器

声明

  1. queue<int> q;                                    //创建一个名为q的队列
  2. struct rec{};queue<rec> q;                       //结构体rec中必须定义小于号
  3. priority_queue<int> q;                           //大根堆(root为最大值)
  4. priority_queue<int,vector<int>,greater<int>> q;  //小根堆(root为最小值)
  5. priority_queue<pair<int,int>> q;

函数

  • 循环队列 queue
    • push 从队尾插入
    • pop 从队头弹出
    • front 返回队头元素
    • back 返回队尾元素
  • 优先队列 priority_queue
    • push 把元素插入堆
    • pop 删除堆顶元素
    • top 查询堆顶元素(最值)

stack

头文件stack包含栈

声明

  1. stack<int> a;           //创建一个名为a的int栈

函数

  • push 向栈顶插入元素
  • pop 弹出栈顶元素
  • top 返回栈顶元素

deque

双端队列deque是一个支持在两端高效插入或删除元素的连续线性存储空间。它就像是vector和queue的结合。与vector相比，deque在头部增删元素仅需要O(1)的时间；与queue相比，deque像数组一样支持随机访问

声明

  1. deque<int> dq;             //创建一个名为dq的双端队列

函数

  • begin 返回队头迭代器
  • end 返回队尾迭代器
  • front 返回队头元素
  • back 返回队尾元素
  • push_back 从队尾入队
  • push_front 从队头入队
  • pop_back 从队头出队
  • pop_front 从队头出队
  • clear 清空队列

set

头文件set主要包括set和multiset两个容器，分别是“有序集合”和“有序多重集合”，即前者的元素不能重复，而后者可以包含若干个相等的元素。set和multiset的内部实现是一棵红黑树，它们支持的函数基本相同

声明

  1. set<int> s;
  2. struct rec{};set<rec> s;       // 结构体rec中必须定义小于号
  3. multiset<double> s;

函数

  • size 返回集合大小
  • empty 返回集合是否为空
  • clear 清空集合
  • set::iterator it; 迭代器 只支持++和—算术操作
  • begin 返回集合中最小元素的迭代器
  • end 返回集合中最大元素的下一个位置的迭代器
  • insert 把元素插入到集合中，若元素已存在，不会重复插入
  • find(x) 在集合中查找等于x的元素，并返回指向该元素的迭代器，若不存在则返回end()
  • lower_bound(x) 查找大于等于x的元素中最小的阉割，并返回指向该元素的迭代器
  • upper_bound(x) 查找大于x的元素中最小的阉割，并返回指向该元素的迭代器
  • erase 若参数为迭代器，则删除迭代器指向的元素，若参数为元素，则删除所有等于该元素的元素，时间复杂度为O(k+logn),k为被删除元素个数
  • count(x) 返回集合中等于x的元素个数，时间复杂度为O(k+logn),k为x元素的个数

map

map容器是一个键值对key-value的映射，其内部实现是一棵以key为关键码的红黑树。Map的key和value可以是任意类型，其中key必须定义小于号运算符

声明

  1. map<key_type,value_type> name;
  2. //例如
  3. map<long,bool> vis;
  4. map<string,int> hash;
  5. map<pair<int,int>,vector<int>> test;

函数

  • size 返回map大小
  • empty 返回map是否为空
  • clear 清空map
  • begin 返回map中最小元素的迭代器
  • end 返回map中最大元素的下一个位置的迭代器
  • insert 在map里插入一个元素，参数为pair
  • erase 在map里删除一个元素
  • find(x) 在map里面查找key为x的二元组
  • [] 返回key映射的value的引用，时间复杂度为O(logn)