Container

Feb 10th, 2020 - Now

Container

Vector

Operations	Meanings
constructors	create vectors and initialize them with some data
operators	compare, assign, and access elements of a vector
assign	assign elements to a vector
at, index	returns an element at a specific location
back	returns a reference to last element of a vector
begin	returns an iterator to the beginning of the vector
capacity	returns the number of elements that vector can hold
clear	removes all elements from the vector
empty	returns true if the vector has no elements
end	returns an iterator to the first element of a vector
erase	remove elements from a vector
front	returns a reference to the first element of a vector
insert	inserts elements into the vector
max_size	returns the maximum number of elements that vector can hold
pop_back	removes the last element of a vector
push_back	add an element to the end of the vector
rbegin	returns a reverse iterator to the end of the vector
rend	returns a reverse iterator to the beginning of the vector
reserve	sets the minimum capacity of the vector
resize	changes the size of the vector
size	returns the number of elements in the vector
swap	swaps the contents of this vector with another

Constructor 相关

1. vector<int> array; // 默认为空
2. vector<int> array(n); // 初始化n个0元素
3. vector<int> array(m, x); // m个元素，每个都初始化为x
4. vector<int> a2(a1);
5. vector<int> a2 = a1;
   // 上面两种方式等价，a2初始化为a1的拷贝，其中a1必须与a2类型相同
   // 也就是同为vector<int>类型，a2将具有和a1相同的容量和元素
6. vector<int> a2(a1, a1+6) // 将a1的前六个元素拿来初始化a2 
7. vector<int> {0,1,2,3,4}; // 列表初始化
8. vector<int> a2(a1.begin()+2,a1.end()-1); 
    // a1.end()指向a1的末尾元素下一位置迭代器，第二个参数指向的元素本身不会被拷贝到新数组中，到它的前一个元素截止
    // 例如 a1中元素为{0,1,2,3,4,5}上述操作a2结果为{2,3,4}。
9. vector<vector<int>> matrix(m, vector<int>(n,0)); //构建m*n的二维数组，初始化每个元素为0

常用函数

array.push_back(element);//在末尾插入元素
array.size();//array中的元素个数

**erase**
iterator erase( iterator loc ); //删除 loc 位置上的元素
iterator erase( iterator start, iterator end ); //删除从 start 到 end 位置上的元素，不动 end
e.g. array.erase(array.begin()+i);//删除第i个元素，用begin迭代器加i
// **注意**：vector为了保证数据的连续性，会在每次删除之后将数据整体往前移，即保证头地址不动
// 后面的连续存储，所以如果是迭代器中删除，删除之后记得 iter--; 类似的操作

array.clear(); // 清空数据

TYPE array.back(); // 返回array的最后一个元素
TYPE array.front(); // 返回array的第一个元素

iterator array.begin(); // 返回指向首个元素的迭代器
iterator array.end(); // 返回指向尾部的 **下一个** 的迭代器
// 注意区别上面四个的关系，前两个 back 和 front 是返回元素，可以直接取元素的内容
// 下面两个是返回迭代器，需要前加 * 才能取里面的内容
// 而且 end 返回的是末尾的下一个，back 返回的是末尾

iterator insert( iterator loc, const TYPE& val );  
void insert( iterator loc, size_type num, const TYPE& val );  
void insert( iterator loc, input_iterator start, input_iterator end ); 
e.g. a1.insert(a1.end(),a2.begin(),a2.end());将a2数组所有元素插入到a1数组后面

排序

sort(a.begin(), a.end()); //对a中的元素排序，默认从小到大排
sort(a.begin(), a.end(), cmp); //写成这种形式可以自定义比较函数cmp

//自定义比较函数 cmp
(static) bool cmp(const int &a,const int &b) {   
    return a>b;
}
//在转换字符串等某些场景下需要在函数返回值类型前加static，或者将该函数移到类外面，不然容易报错

//结构体：
struct ss {
    int x,y;
};
//自定义结构体比较函数 cmp
(static) bool cmp(const ss &x,const ss &y) {
    return (x.x != y.x)? x.x<y.x : x.y<y.y; //二维偏序 
}

遍历访问

// 迭代器 iterator 访问
// it 是指向容器的迭代器指针，可以直接通过 ++,-- 移动
// *it 取指针指向的元素的内容
int main() {
    vector<int> s;
    s.push_back(1);
    for (vector<int>::iterator it=s.begin(); it!=s.end(); it++)
        cout << *it<<endl;
    return 0;
}

// 数组下标访问
int main() {
    vector<int> s;
    s.push_back(1);
    for (int i=0; i<s.size(); i++)
        cout << s[i]<<endl;
    return 0;
}

修改内容 访问下标方式：

// 直接取是访问 vector 里面的内容，并没有修改的权限，需要加引用才能修改
if(abc.begin()!=abc.end()) {
    for (unsigned int i = 0;i<abc.size();i++) {
            abc[i] = i+1;
    }
    cout<<"原始数据："<<endl;
    vector_out(abc);
    auto &val2 = abc.back(); // val2为指向最后一个元素的引用
    val2 = 2;
    cout<<"变量为引用类型，修改后："<<endl;
    vector_out(abc);
    auto val3 = abc.back(); // 仅是abc.back()的一个拷贝
    val3 = 10;
    cout<<"变量不是一个引用,修改无效："<<endl;
    vector_out(abc);
}

迭代器方式：

// 普通的迭代器 iterator 可以直接修改，直接 (*it)然后修改即可
// 特殊的放置修改的迭代器 const iterator 可以避免发生误修改，即只能读
// c++11 中的 foreach 其实用的就是迭代器

1. 
for (auto e : lists) {
    e[0] = 100; // 修改失败，因为是值传递的 iterator
} 
2. 
for (auto& e : lists) {
    e[0] = 100; // 修改成功，因为是引用传递的 iterator
}
3. 
for (const auto& e : lists) {
    e[0] = 100; // 修改失败，const 决定了是 read-only，加不加 & 无影响 
}
4. 
for (vector<int>::iterator it=lists.begin();it!=lists.end();it++) {
    (*it)[0] = 100; // 修改成功，因为 iterator 直接指向的是地址
}
5. 
for (vector<int>::const_iterator it=lists.begin();it!=lists.end();it++) {
    (*it)[0] = 100; // 修改失败，因为 const_iterator 是 read-only
}

去除重复值

e.g.

vector<T> vec;
initialize(vec);
...

sort(vec.begin(), vec.end());  // 要先进行排序
vector<T>::iterator dup_head = unique(vec.begin(), vec.end());  // 然后使用unique返回一个iterator
vec.erase(dup_head, vec.end());  // 从返回的 dup_head 开始删除后面的所有元素

几个注意的地方：  
0. 其作用是将容器中重复的元素都移动到队尾，具体实现方式是从第一个参数开始遍历，看当前元素是否和上一个元素相同，相同则移动到对位，所以在使用 unique 之前先要进行 **排序操作**  
1. 第一个参数为开始的元素的iterator   
2. 第二个参数为末尾的下一个iterator  
3. 返回值是一个iterator指向重复序列的第一个元素  
4. 只是做了一个遍历所以容器内的元素个数不发生改变，只是位置发生了变化  

为什么扩容选择 1.5X or 2X https://www.drdobbs.com/c-made-easier-how-vectors-grow/184401375 https://www.zhihu.com/question/36538542/answer/67929747 由于扩容时会发生空间的重新配置，因此指向原vector的迭代器会失效， 因此注意当迭代器遍历的时候尽量不要插入新数据

vector 还提供 reference front() 和 reference back() 函数， 返回第一个/最后一个值的引用，因此 v.front() 和 *v.front() 值是一样的

erase() 会引起数据的拷贝

List

List 内部指针为 void* 类型指针，且有 prev 和 next，是一个双向链表 因此迭代器返回的是 bidirectional iterator

由于 List 不会引起空间的重新配置，因此在插入和拼接时不会发生迭代器失效 内部对迭代器的 ++/-- 进行了运算符重载使得其向前向后移动更加方便

List 内部刻意内置了一个空接点 node 并指向自身成环，这样的好处是：

1. 一个 node 即可表示整个链表

2. node 所在位置即链表的 end()，更加符合前闭后开区间的要求

3. 判断 empty() 更加方便：node->next == node

List 的 insert 会 insert 到当前迭代器的位置上，从结果来看即从迭代器开始数据后移 如： 1,2,3,4,5 在 *(ite)=3 时 insert(ite, 0) 会得到 1,2,0,3,4,5 的结果

Unique 操作是 移除连续且相同的值，对于不连续的值无法删除 如： 1,2,3,3,4,3 unique 操作后得到 1,2,3,4,3

transfer(iterator position, iterator begin, iterator end) 迁移操作是内部非公开函数 用来辅助 List 的 splice, merge, reverse, sort 等 具体作用是将 [begin(), end()) 的值 移动 插入到 position 处 由于 STL::sort 仅支持 RandomAccessIterator 因此需要调用自己的 member function list.sort() list.sort() 深度解析：https://www.cnblogs.com/avota/archive/2016/04/13/5388865.html

deque

双向 vector，实现极其繁琐，本质为维护指向buffer的指针，在buffer中进行操作 相比于 vector 而言，在前端插入不会引起数据的移动，作为 stack 和 queue 的底层支持 但是排序操作会非常费时，考虑到不同的 buffer 之间的指针的移动

stack & queue

stack：先进后出，底层用 deque，禁用了其前端出入的特性 queue：先进先出，底层用 deque，禁用了其前端入后端出的特性 两者都可以用 list 作为底层实现，方式为 stack<int, list> 两者都不提供迭代器，因为只有单一出口方式 stack：top() 返回顶部的值，pop() 无返回值 queue：front() 返回前端的值，back() 返回后端的值，push() 将元素从后端加入，pop() 将元素从前端取出

Priority_queue

Operations	Meanings
constructors	create priority_queue and initialize them with some features
empty	returns true if the vector has no elements
size	returns the number of elements in the vector
pop	removes the top element of a priority queue, no return value
push	adds an element to the end of the priority queue
top	returns the top element of the priority queue

排序

1. 自带的排序
priority_queue <int, vector<int>, less<int>> p;
priority_queue <int, vector<int>, greater<int>> q;

// 这里的 less 和 greater 只适用于cpp能够识别的数据类型
// 换而言之，不支持自定义的结构体，支持 int, float, string, pair<int, int>等等
// 对于 pair 而言，就是先比较 first，再比较 second 的值

// less 和 greater 是设置递增递减，记忆时可以理解为趋势
// less 即变小的趋势 —— 递减，从大到小
// greater 即变大的趋势 —— 递增，从小到大

2. 自定义的排序——结构体内重载运算符实现（推荐）
priority_queue <Node, vector<Node>, greater<Node>> p
struct Node {
    int first, second;
    Node(int first, int second) : first(first), second(second) {}
    bool operator<(const Node& x) const { // 一定要注意这里两个const
        return (first==x.first)? second>x.second:first<x.first;
    }
};


3. 自定义的排序——结构体函数实现
priority_queue <int, vector<int>, cmp> q;

// 这里的cmp是自己定义的一个结构体函数，如：
class Node{ 
public: 
    int x,y;
    Node(int x, int y) : x(x), y(y) {}
};

class Solution {
public:
struct cmp
{
    bool operator () (const Node &x,const Node &y) const
    {
        return x.x<y.x;
    }
};

int main() {
    xxxxx

    priority_queue <int, vector<int>, cmp> q; // declaration

}
}
// 上面的结构体函数就可以将自定义的 Node 按照 x 进行从小到大的排序

4. 自定义的排序——结构体外重载运算符实现
// 我们知道，priority_queue 的维护实际上就是在一直比较元素大小并交换位置
// c++ 作为面向对象语言有重载运算符的特性，如果我们将结构体的大小比较做定义
// 那么就可以让机器识别我们的结构体类型了

struct Node {
        int x,y,z;
        Node(int x, int y, int z) : x(x), y(y), z(z) {}
};

// 重载小于符号，使得 less<Node> 生效
bool operator<(const Node a, const Node b) {
        return (b.x==a.x)? b.y>a.y:b.x>a.x;
}

// 重载大于符号，使得 greater<Node> 生效
bool operator>(const Node a, const Node b) {
        return (b.x==a.x)? b.y<a.y:b.x<a.x;
}

// 在声明的时候就可以直接使用原生的 less 和 greater 了
priority_queue(Node, vector<Node>, less<Node>) p; // 从小到大
priority_queue(Node, vector<Node>, greater<Node>) p; // 从大到小

map/unordered_map

两者的对比：

特性	map	unordered_map
内部组织	红黑树	哈希表
组织特性	自动排序	插入查找迅速
运行效率	较低	较高
占用内存	较低	较高
时间大头	查询删除	插入
使用场景	要求内部有序稳定的查找速率,内存需要考虑	不需要容器内有序,快速查找删除,不担心内存占用

RB_tree

红黑树查找的时间复杂度为 O(lgn) 的证明： https://blog.csdn.net/cxyj666/article/details/88636854

hash_table

桶+红黑树解决哈希冲突

multimap/multiset

允许出现重复 key 的 map/set，区别在于底层调用了 insert_equal() 而不是 insert_unique()

Map

Operations	Meanings
begin	returns an iterator to the beginning of the vector
clear	removes all elements from the vector
count	returns the number of occurrences of key in the map
empty	returns true if the vector has no elements
end	returns an iterator to the first element of a vector
equal_range	pair<iterator, iterator> equal_range( const key_type& key ) return two iterators one to the first element that contains key another to a point just after the last element that contains key.
erase	remove elements from a vector
find	returns an iterator to key if found or an iterator to the end of the map if not found
insert	inserts elements into the vector
key_comp	returns the function that compares keys
lower_bound	returns an iterator to the first element which has a value greater than or equal to key
max_size	returns the maximum number of elements that vector can hold
rbegin	returns a reverse iterator to the end of the vector
rend	returns a reverse iterator to the beginning of the vector
size	returns the number of elements in the vector
swap	swaps the contents of this vector with another
upper_bound	returns an iterator to the first element in the map with a key greater than key.
value_comp	returns the function that compares values

Map 的内部使用红黑树实现，保证了时刻的有序性，所以其自带用比较函数实现的一些功能，如: lower_bound() 和 upper_bound()。特别要注意不要被英文名弄乱，lower_bound() 其实就是大于等于，upper_bound() 就是大于。

在 Leetcode No.699 中使用到 lower_bound() 来寻找最前相交的方块。

STL_Feature

iterator & reverse_iterator

迭代器和反向迭代器 他们居然不是同一个类 在实现上面反向迭代器完全就是根据迭代器实现的，反向迭代器从尾部元素开始，到首元素的前一个(空元素)结束，反向迭代器++相当于内部维护的迭代器--。 但是，因为 reverse_iterator 和iterator 不是一个东西，所以很多地方传入的参数需要的是 迭代器类型，而不是 反向迭代器类型，就需要通过新建一个迭代器然后取遍历到达反向迭代器所指元素。

具体使用的话在 LeetCode 218 SkyLine 中用过一次。

使用 iterator 安全删除容器元素

当我们想要在遍历的时候删除容器内的元素时，由于对iterator的特性不熟悉容易导致iterator乱飘出现漏删或者跳跃的问题，这里统一一下方法：

map<int, int> mp;
for (auto it = mp.begin(); it != mp.end(); ) {
    if (it->first xxx) {
        mp.erase(it++); 
    }
}

it++ 的操作既保留了当前需要删除的迭代器指向的副本，又将it指向了正确的下一个迭代器的位置，美哉。

Reference

1. 《CPP STL Reference Manual》

2. C++ STL算法系列4---unique , unique_copy函数

Algorithm

lower_bound & upper_bound

lower_bound 插入使得依然有序的最早位置 upper_bound 插入使得依然有序的最晚位置 E.g. 1 2 2 2 3 插入 2 lower_bound: 1 | 2 2 2 3 upper_bound: 1 2 2 2 | 3 Caution: 自定义comp函数要严格小于，小于等于会出现问题

sort

https://mp.weixin.qq.com/s/6h1R6UoDDZwfIkBEAt63ew 包含 __introsort_loop 内省排序 和 __final_insertion_sort 插入排序 内省排序会根据元素的长度给出一个快速排序的深度限制 超过深度限制时会直接使用堆排序结束剩下的部分 当内省排序的数组长度小于 threshold==16 时返回给插入排序解决剩下的部分 快速排序使用了尾递归的方式减少了一半的递归调用，具体地只对后半部分进行递归操作，前半部分留给while循环操作 堆排序函数详解 https://www.jianshu.com/p/22fe785d607b copy_backward也是一种整体移动的优化，避免了one by one的调整移动，底层调用memmove来高效实现。