STL
- 1.#include < vector>
- 2.#include < queue>
- 3.#include < stack>
- 4.#include < deque>
- 5.#include < set>(有顺序的表)
- multiset( 单调队列 )
- 6.#include < map> 哈希表 改变的是角标
- 7. pair 只有一个元素
- 8. string，字符串
- STL的遍历
- 常用库函数
- 例题
1.#include < vector>
vector是变长数组，支持随机访问，不支持在任意位置O(1)插入。为了保证效率，元素的增删一般应该在末尾进行。
一、声明
#include 头文件
vector<int> a; 相当于一个长度动态变化的int数组vector<int> b[233]; 相当于第一维长233，第二位长度动态变化的int数组struct rec{…}; vector<rec> c; 自定义的结构体类型也可以保存在vector中
二、作用
1. size/empty（每个stl都有）
size函数返回vector的实际长度（包含的元素个数）empty函数返回一个bool类型，表明vector是否为空。二者的时间复杂度都是O(1)。
所有的STL容器都支持这两个方法，含义也相同，之后我们就不再重复给出。
2. clear
clear函数把vector清空
3. push_back() 和 pop_back()（都是在尾部操作）
a.push_back(x) 把元素x插入到vector a的尾部。b.pop_back() 删除vector a的最后一个元素。
4. front/back(返回值是元素)
front函数返回vector的第一个元素，等价于*a.begin() 和 a[0]。
back函数返回vector的最后一个元素，等价于*- -a.end() 和 a[a.size() – 1]。
5. vector比较
a是4个3
b是3个4
所以 字典序是 b大
6. [] 随机提取
7. 迭代器(就是vector的指针)
迭代器
迭代器就像STL容器的“指针”，可以用星号“*”操作符解除引用。
一个保存int的vector的迭代器声明方法为：
vector::iterator it;
vector的迭代器是“随机访问迭代器”，可以把vector的迭代器与一个整数相加减，其行为和指针的移动类似。可以把vector的两个迭代器相减，其结果也和指针相减类似，得到两个迭代器对应下标之间的距离。
begin/end(返回值是地址)
begin函数返回指向vector中第一个元素的迭代器。例如a是一个非空的vector，则*a.begin()与a[0]的作用相同。
所有的容器都可以视作一个“前闭后开”的结构，end函数返回vector的尾部，即第n个元素再往后的“边界”。*a.end()与a[n]都是越界访问，其中n=a.size()。
下面两份代码都遍历了vector\<int>a，并输出它的所有元素。
for (int I = 0; I < a.size(); I ++)
cout << a[i] << endl;
for (vector<int>::iterator it = a.begin(); it != a.end(); it ++)
cout << *it << endl;
//用auto！！！
for (auto it = a.begin(); it != a.end(); it ++)
cout << *it << endl;
三、4种遍历方式
1. 直接限定个数
2. a.size
3. iterator
4. auto
2.#include < queue>
头文件queue主要包括循环队列queue和优先队列priority_queue两个容器。
一、 作用
1. size()
2. empty()
3. push() 向队尾插入一个元素
4. front() 返回队头元素 （可以接收返回值！）
5. back() 返回队尾元素
6. pop() 弹出队头元素 （没有返回值）
二、声明
queue<int> q;
struct rec { … }; queue<rec> q; //结构体rec中必须定义小于号
三、循环队列
1. push(elem);//往队尾添加元素
2. pop();//从队头移除第一个元素
3. back();//返回最后一个元素
4. front();//返回第一个元素
5. empty();//判断队列是否为空
6.size();//返回队列的大小
四、优先队列priority_queue（自动排序）
一、声明
优先队列的功能强大在哪里呢？ 四个字：自动排序。
优先队列声明的基本格式是： priority_queue<结构类型> 队列名; 比如：
priority_queue<int> q;
/*默认是大根堆*/
priority_queue<double> q;
priority_queue<int,vector<int>,greater<int> > q;
//注意后面两个“>”不要写在一起，“>>”是右移运 算符
/*小根堆*/
priority_queue<int,vector<int>,less<int> > q;
/*大根堆*/
二、操作
1. q.size(); //返回q里元素个数
2. q.empty(); //返回q是否为空，空则返回1，否则返回0
3. q.push(k); //在q的末尾插入k
4. q.pop(); //删掉q的第一个元素
5. q.top(); //返回q的第一个元素（也就是堆顶）
6. q.back(); //返回q的末尾元素
3.#include < stack>
一、操作
1. size()
2. empty()
3. push() 向栈顶插入一个元素
4. top() 返回栈顶元素
5. pop() 弹出栈顶元素
4.#include < deque>
双端队列deque是一个支持在两端高效插入或删除元素的连续线性存储空间。它就像是vector和queue的结合。与vector相比，deque在头部增删元素仅需要O(1)的时间；与queue相比，deque像数组一样支持随机访问。
一、操作
1. size()
2. empty()
3. clear()
4. front() / back()
5. push_back() / pop_back()
6. push_front() / pop_front()
7. begin() / end()
8. 随机提取[]
5.#include < set>(有顺序的表)
头文件set主要包括set和multiset两个容器，分别是“有序集合”和“有序多重集合”，即前者的元素不能重复，而后者可以包含若干个相等的元素。set和multiset的内部实现是一棵红黑树，它们支持的函数基本相同。
声明
set<int> s;
struct rec{…}; set<rec> s; // 结构体rec中必须定义小于号
multiset<double> s;
size/empty/clear
与vector类似
迭代器（用于遍历）
set和multiset的迭代器称为“双向访问迭代器”，不支持“随机访问”，支持星号(*)解除引用，仅支持”++”和- -“两个与算术相关的操作。
设it是一个迭代器，例如set\<int>::iterator it;
若把it++，则it会指向“下一个”元素。这里的“下一个”元素是指在元素从小到大排序的结果中，排在it下一名的元素。同理，若把it–，则it将会指向排在“上一个”的元素。
begin/end
返回集合的首、尾迭代器，时间复杂度均为O(1)。
s.begin() 是指向集合中最小元素的迭代器。
s.end() 是指向集合中最大元素的下一个位置的迭代器。换言之，就像vector一样，是一个“前闭后开”的形式。因此**–s.end()是指向集合中最大元素的迭代器**。
insert（按顺序插入）
s.insert(x)把一个元素x插入到集合s中，时间复杂度为O(logn)。
在set中，若元素已存在，则不会重复插入该元素，对集合的状态无影响。
find(返回值是地址)
s.find(x) 在集合s中查找等于x的元素，并返回指向该元素的迭代器。若不存在，则返回s.end()。时间复杂度为O(logn)。
lower_bound/upper_bound
这两个函数的用法与find类似，但查找的条件略有不同，时间复杂度为 O(logn)。
s.lower_bound(x) 查找大于等于x的元素中最小的一个，并返回指向该元素的迭代器。
s.upper_bound(x) 查找大于x的元素中最小的一个，并返回指向该元素的迭代器。
erase
设it是一个迭代器，s.erase(it) 从s中删除迭代器it指向的元素，时间复杂度为O(logn)
设x是一个元素，s.erase(x) 从s中删除所有等于x的元素，时间复杂度为O(k+logn)，其中k是被删除的元素个数
count（用于multiset）
s.count(x) 返回集合s中等于x的元素个数，时间复杂度为 O(k +logn)，其中k为元素x的个数。
multiset( 单调队列 )
6.#include < map> 哈希表 改变的是角标
map容器是一个键值对key-value的映射，其内部实现是一棵以key为关键码的红黑树。Map的key和value可以是任意类型，其中key必须定义小于号运算符。
声明
map<key_type, value_type> name;
例如：
map<long, long, bool> vis;
map<string, int> hash;
map<pair<int, int>, vector> test;
size/empty/clear/begin/end均与set类似。
Insert/erase
与set类似，但其参数均是pair<key_type, value_type>。
也可以直接用 map[i] = n 这样的一个代码表示 Map的map中增加了一个key值为i，value值为n的数据
find
h.find(x) 在变量名为h的map中查找key为x的二元组。
返回值是
如果找到了 返回自己的地址
如果没找到 返回map.end()的地址
所以 返回值为 end()表明没找到
操作符
h[key] 返回key映射的value的引用，时间复杂度为O(logn)。
[]操作符是map最吸引人的地方。我们可以很方便地通过h[key]来得到key对应的value，还可以对h[key]进行赋值操作，改变key对应的value。
6.2 size/empty/clear/begin/end
均与set类似。
7. pair 只有一个元素
通过角标，可以找到它的两种属性
（某一个事物，有多种属性）
一、声明
pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
三种属性
8. string，字符串
1. size()/length() 返回字符串长度
2. empty()
3. clear()
4. substr(起始下标，(子串长度)) 返回子串
5. c_str() 返回字符串所在字符数组的起始地址
STL的遍历
for (int i = 0; i < a.size(); i++)
for (auto i = a.begin(); i != a.end(); i++) 需要对i解引用
for (aotu x : a) 直接是元素，不是地址
常用库函数
(1)reverse 翻转
翻转一个vector：
reverse(a.begin(), a.end());
翻转一个数组，元素存放在下标1~n：
reverse(a + 1, a + 1 + n);
(2)unique 去重（全部去重）
返回去重之后的尾迭代器（或指针），仍然为前闭后开，即这个迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后的元素个数。
把一个vector去重：
int m = unique(a.begin(), a.end()) – a.begin();
把一个数组去重，元素存放在下标1~n：
int m = unique(a + 1, a + 1 + n) – (a + 1);
（3）sort
对两个迭代器（或指针）指定的部分进行快速排序。可以在第三个参数传入定义大小比较的函数，或者重载“小于号”运算符。
从大到小排序
bool cmp(int a, int b) //a是否应该排到b的前面
{return a > b; }
sort(a + 1, a + 1 + n, cmp);
从小到大排序
bool cmp(int a, int b) {return a < b; }
sort(a + 1, a + 1 + n, cmp);
结构体排序
方法一：直接用cmp函数
方法二：在结构体中构造函数
x越小的结构体越小，x相等y越小的结构体越小
struct rec{ int id, x, y; }
vector<rec> a;
bool operator < (const rec &a, const rec &b)
{
return a.x < b.x || a.x == b.x && a.y < b.y;
}
sort(a.begin(), a.end());
x越大的结构体越大
例题
1. 数字在排序数组中出现的次数
class Solution {
public:
int getNumberOfK(vector<int>& nums, int k) {
int cnt = 0;
for (int x : nums)
if (x == k)
cnt ++ ;
return cnt;
}
};
2. 0到n-1中缺失的数字 （set应用）
哈希表（unordered_set）
insert(x)
erase(x)
有序的所以 begin（）就是值
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
unordered_set<int> S;
for (int i = 0; i <= nums.size(); i ++ )
S.insert(i);
for (auto x : nums) S.erase(x);
return *S.begin();
}
};
二分（表具有二段性，可以用二分）
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
if (nums.empty()) return 0;
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] != mid) r = mid;
else l = mid + 1;
}
if (nums[r] == r) r ++ ;
return r;
}
}；
3. 调整数组顺序使奇数位于偶数前面
vector的 size（）
class Solution {
public:
void reOrderArray(vector<int> &array) {
int l = 0, r = array.size() - 1;
while (l < r) {
while (l < r && array[l] % 2 == 1) l ++ ;
while (l < r && array[r] % 2 == 0) r -- ;
if (l < r) swap(array[l], array[r]);
}
}
};
4. 从尾到头打印链表
vector的 push_back()
vector(a.rbegin(),a.rend())
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> printListReversingly(ListNode* head) {
vector<int> res;
while (head) {
res.push_back(head->val);
head = head->next;
}
return vector<int>(res.rbegin(), res.rend());
}
};
5.用两个栈实现队列
1.a.pop() 后 a.size()会变得
class MyQueue {
public:
/** Initialize your data structure here. */
stack<int> stk, cache;
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
stk.push(x);
}
void copy(stack<int> &a, stack<int> &b) {
while (a.size()) {
b.push(a.top());
a.pop();
}
}
/** Removes the element from in front of queue and returns that element. */
int pop()
{
while (s1.size() > 1)
s2.push(s1.top()), s1.pop();
int t = s1.top;
s1.pop();
while (s2.size())
s1.push(s2.top()), s2.pop();
return t;
}
/** Get the front element. */
int peek() {
copy(stk, cache);
int res = cache.top();
copy(cache, stk);
return res;
}
/** Returns whether the queue is empty. */
bool empty() {
return stk.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* bool param_4 = obj.empty();
*/
6. 最小的k个数
sort排序 参数是地址
class Solution {
public:
vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
sort(input.begin(), input.end());
vector<int> res;
for (int i = 0; i < k; i ++ ) res.push_back(input[i]);
return res;
}
};
7. 和为S的两个数字
定义一个哈希表
开始遍历原vector，如果遍历点之前，
判断哈希表是否有对应值，没有值，那么增到哈希表里
S.count() （哈希表中寻找数据）
class Solution {
public:
vector<int> findNumbersWithSum(vector<int>& nums, int target) {
unordered_set<int> S;
for (auto x : nums)
{
if (S.count(target - x)) return {x, target - x};
S.insert(x);
}
}
};
8. 排列数组
next_permutation
vectot
class Solution {
public:
vector<vector<int>> permutation(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
do res.push_back(nums); while (next_permutation(nums.begin(), nums.end()));
return res;
}
};
9. 二进制中1的个数
n=n&(n-1)
lowbit(x) = x & -x，返回x的最后一位1
class Solution {
public int NumberOf1(int n){
int count=0;
while(n!=0){
n=n&(n-1);
count++;
}
return count;
}
}