cpp
vector, 变长数组，倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序
pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
string，字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址
queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
priority_queue, 优先队列，默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，--
bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反
作者：yxc
链接：https:
来源：AcWing
sort, 排序
struct Point {
int l, r;
bool operator< (const Point& p)const {
return l < p.l;
}
}points[N];
sort(points, points+n);
sort(points, points+n, [] (Point p1, Point p2) {
return p1.l < p2.l;
});
java
ArrayList, 动态数组，基于数组实现
size() 返回元素个数
isEmpty() 返回是否为空
clear() 清空
get(index) 返回指定索引处的元素
add() 向尾部添加一个元素
remove() 移除指定索引处的元素
set(index, element) 修改指定索引处的元素
contains() 检查是否包含某个元素
indexOf() 返回某个元素的索引
HashMap, 哈希映射
put(key, value) 插入一个键值对
get(key) 获取指定键的值
size() 返回映射中键值对的个数
isEmpty() 判断映射是否为空
containsKey(key) 判断是否包含指定的键
containsValue(value) 判断是否包含指定的值
remove(key) 移除指定键的键值对
keySet() 返回所有键的集合
values() 返回所有值的集合
entrySet() 返回所有键值对的集合
HashSet, 哈希集合
add(element) 向集合中添加元素
contains(element) 检查是否包含某个元素
remove(element) 移除指定元素
size() 返回集合中元素的个数
isEmpty() 判断集合是否为空
clear() 清空集合
LinkedList, 双向链表
size() 返回元素个数
isEmpty() 判断链表是否为空
add() 向链表末尾添加元素
addFirst() 在链表头部添加元素
addLast() 在链表尾部添加元素
remove() 移除链表头部元素
removeLast() 移除链表尾部元素
removeFirst() 移除链表头部元素
getFirst() 返回链表头部元素
getLast() 返回链表尾部元素
PriorityQueue, 优先队列，默认是最小堆
add() 插入一个元素
peek() 返回堆顶元素
poll() 弹出堆顶元素
size() 返回队列大小
isEmpty() 判断队列是否为空
Comparator<T> 自定义排序方式，可用于最大堆
Stack, 栈
push() 向栈顶压入一个元素
pop() 弹出栈顶元素
peek() 返回栈顶元素
isEmpty() 判断栈是否为空
size() 返回栈中元素个数
Deque, 双端队列
addFirst() 在队头插入一个元素
addLast() 在队尾插入一个元素
removeFirst() 从队头移除元素
removeLast() 从队尾移除元素
peekFirst() 返回队头元素
peekLast() 返回队尾元素
size() 返回队列大小
isEmpty() 判断队列是否为空
TreeSet, 基于红黑树实现的集合
add(element) 向集合中添加元素
contains(element) 检查是否包含某个元素
remove(element) 移除指定元素
size() 返回集合中元素的个数
isEmpty() 判断集合是否为空
clear() 清空集合
first() 返回最小元素
last() 返回最大元素
TreeMap, 基于红黑树实现的映射
put(key, value) 插入一个键值对
get(key) 获取指定键的值
containsKey(key) 检查是否包含指定键
remove(key) 移除指定键的键值对
size() 返回映射中键值对的个数
isEmpty() 判断映射是否为空
firstKey() 返回最小键
lastKey() 返回最大键
HashMap 和 TreeMap 都是基于键值对的映射，区别在于 TreeMap 按键的自然顺序或指定比较器排序，而 HashMap 不保证顺序。
BitSet, 位集合
BitSet bs = new BitSet(10000); 创建一个容量为10000的位集合
set(index) 设置指定位置的位为1
clear(index) 设置指定位置的位为0
flip(index) 反转指定位置的位
get(index) 获取指定位置的位
cardinality() 返回集合中为1的位的个数
length() 返回位集合的长度
sort, 排序重载compareTo()
class Point implements Comparable<Point> {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public int compareTo(Point other) {
return Integer.compare(this.x, other.x);
}
}
Arrays.sort(points, 0, n);
Arrays.sort(points, (p1, p2) -> Integer.compare(p1.l, p2.l));
ArrayList<Integer> arrayList = new ArrayList<>();
HashMap<String, Integer> hashMap = new HashMap<>();
HashSet<Integer> hashSet = new HashSet<>();
LinkedList<String> linkedList = new LinkedList<>();
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
Stack<Integer> stack = new Stack<>();
Deque<Integer> deque = new LinkedList<>();
TreeSet<Integer> treeSet = new TreeSet<>();
TreeMap<String, Integer> treeMap = new TreeMap<>();
BitSet bitSet = new BitSet(10000);
