AoS 和 SoA
将需要同时获取的数据集中放在一起
大概就是说，比如你有 1000 个员工，每个员工有年龄，性别等特征
你取了年龄之后，经常的又取性别，那么你应该考虑
struct Person{int age, bool male} 并存入一个 vector
而不是多个 vector（或者是 map），根据 id，在这个 vector 里取年龄，那个里面取性别
STL
纠结于一个 STL 容器本身的大小是没意义的
这取决于标准库的实现（比如用 MSVC 还是 libstdc++），以及 32 64 位等等，以及 debug 或者 release（debug 的 msvc 多一个迭代器）
而且 STL 的数据又不是存在本身里
vector
在尾部插入、删除，平均为 O(1)，因为不是每次都需要重写分配内存
在其它位置插入、删除 O(n)，和到 vector 尾部的距离成线性，每次都需要重新分配
查找 O(n)，需要遍历一遍，平均是个数的一半
map set
通常实现是红黑树（C++标准没说用什么树实现，但是现实情况是，所有人默认它是红黑树，并且所有标准库都实现为红黑树）
搜索、移除和插入拥有对数复杂度
unordered_set unordered_map
搜索、插入和移除拥有平均常数时间复杂度（最坏为 O(n)）
元素并不以任何特别顺序排序，而是组织进桶中。元素被放进哪个桶完全依赖其值的散列。这允许对单独元素的快速访问，因为一旦计算了散列值，它就指代元素被放入的确切的桶。
不可修改容器元素（即使通过非 const 迭代器），因为修改可能更改元素的散列，并破坏容器（这句话的意思是，不可修改，但是可以删除，再重新插入一个新的）
备注：unordered_set 没有迭代器，可以用迭代器或者基于范围的 for 循环来遍历，如果是迭代器，那么 *it 不可以写入。你如果要换元素，是把原来的删掉，再重新插入。不过遍历速度是这几款容器里最慢的。是否能用基于范围的 for 循环，本质是能不能取到 begin() 迭代器，标准库似乎都能取到
VC 的 unordered_map 内部采取链表结构 + 链地址法解决 hash 冲突，这导致缓存命中率下降。
VS 上，遍历一次。vector >>> map > unordered_map size （说是基于 10,000,000）
Rust：根据 rust 的实现，现代计算机多级缓存机制，导致如果缓存命中，访问连续内存的速度远远大于教科书上 O(1) 的解指针，因为指针的内存不连续，一旦未命中，则耗时大大提高
所以：如果你不是真的需要链表，你要用循环数组的假链表替代，以及 map 也换成 B 树等实现，如果你知道你数据量很小，直接用 vector，即便是搜索，也比 map 那种不连续的快
algorithm
std::unique
对一个 vector 进行连续元素*的去重 ，无法去掉不连续的重复元素。去重后，size 不变，需要自己调整。顺序不变，时间复杂度 O(N)，空间复杂度是 O(1)
那么我们自然想到先排个序，然后再删掉，大概是这样
std::vector<int> v = { 1,2,1,1,3 };
std::sort(v.begin(), v.end());
std::vector<int>::iterator it = std::unique(v.begin(), v.end());
v.erase(it, v.end());
int a = v.size();std::remove
从范围 [first, last) 移除所有满足特定判别标准的元素，并返回范围新结尾的尾后迭代器
移除元素是通过将范围内的元素移动位置，使得不需要被移除的元素会在范围的开头出现的方式实现的
复杂度 N （假设等于操作是 O(1)）。和 std::unique 一样，不会改 size，所以也需要手动删。所谓的“擦除-移除”惯用法
注意：remove 是需要一个值的，并不是无脑删
std::vector<int> v = { 1,2,1,1,3 };
auto it = std::remove(v.begin(), v.end(), 1);
v.erase(it, v.end());std::remove_if
比 remove 灵活一点，大概就是可以根据一个谓词判断（一个返回布尔值的可调用对象（如函数、函数对象、Lambda 表达式））
bool fun(int a)
{
if (a > 1)
{
return true;
}
return false;
}
int main()
{
std::vector<int> v = { 1,2,1,1,3 };
auto it = std::remove_if(v.begin(), v.end(), fun);
v.erase(it, v.end());
int a = v.size();
}常见问题收集
1、给一个 vector，给一些下标，删除这些下标位置的数据
首先，你要对给出的下标进行排序去重（如果给出的下标不是排好序的）
其次，如果就是用 vector 的删除，一个个删除，即使是从大下标开始删，也没用，比如：
a b c d e f 删掉 2 和 4 下标，那么你 f 在删除 4 的时候往前移动一次，在删除 2 的时候又删除一次
关键在于减少元素移动次数和**避免下标失效问题
解决：
（1）交换法：将待删除元素和末尾交换，然后 popback 末尾，依次进行。但是这样整个 vector 的顺序乱了。
（2）双指针覆盖：
一个指针 i 用于遍历 vector，另一个指针 p 是“当下标不删除时，我往前走”
举例： a b c d e f 删除下标 2 3 即 c d
a b c d e f
a b c d e f
a b c d e f
a b c d e f
a b e d e f
a b e f e f
这里还是有个问题，就是如何知道 p 是不是下标，需要一个 set 来便捷的查询，如果删除的很大，那么查询也是耗时间的。即使是你用 std::move 去重新构造一个 vector，你也得这样做。
2、vector 和 set 和 unordered_set 互相转换
std::vector<int> vec;
std::unordered_set<int> uset(vec.begin(), vec.end());
std::set<int> set(vec.begin(), vec.end());大概是这样写即可，不需要重新 for 一下
3、vector 中存储重量级元素，比如一个小 struct
那么它的 push_back 是可以直接传递多个参数的，并且似乎效能更好，无需在外面重新构造一个局部 struct
4、在一个 for 循环里，基于 index，生成 "Prefix" + "i" 字符串
说是直接 std::to_string + 字符串拼接 即可，编译器也有优化
5、大概有 15000 个 int，他们大部分是重复的，去重后大概 150 个
1、把 int 逐个插入到 std::vector 里，再用 std::sort 排序，再用 std::unique 去重
2、把 int 逐个插入到 std::set 里，自动排序并去重了，最后转换为一个 std::vector
3、2 的 set 换成 unordered_set，然后换成 vector 再排个序
性能是 1 > 3 > 2
因为 1 的缓存更友好，3 的话，因为查询性能 O(1)，所以快于了 2 的 O(logK)