[C++ Basic] STL Data Structure

基础杂项

auto的使用

• 当你想要拷贝range的元素时，使用 for(auto x : range).
• 当你想要修改range的元素时，使用 for(auto && x : range)
• 当你想要只读range的元素时，使用 for(const auto & x : range).

容器间的转换 begin end

vector<int>& nums1
unordered_set<int> nums_set(nums1.begin(), nums1.end());

unordered_set<int> result;
return vector<int>(result.begin(), result.end());

迭代器知识

前后第k个元素

• std::prev 函数接受两个参数：一个是指向迭代器的参数，另一个是整数偏移量。它返回从指定迭代器开始向前移动指定偏移量后的迭代器。
• std::next 函数接受两个参数：一个是指向迭代器的参数，另一个是整数偏移量。它返回从指定迭代器开始向前或向后移动指定偏移量后的迭代器。

auto prevIt = std::prev(it);

auto next2It = std::next(it, 2);

auto it2 = it;
advance(it2,k);

advance : 形似index的随机访问

• std::advance 函数的实现方式取决于迭代器的类型。
• 对于随机访问迭代器（后面解释），它会直接使用 += 运算符来实现移动。
• 对于双向迭代器和输入迭代器，它会使用循环来实现移动。
• 例如，以下是 std::advance 的一个简单实现, 这个实现使用了 C++17 的 if constexpr 特性，以便在编译时选择不同的实现方式。：

template <typename InputIt, typename Distance>
void advance(InputIt& it, Distance n) {
    if constexpr (std::is_same_v<std::random_access_iterator_tag,
                typename std::iterator_traits<InputIt>::iterator_category>) {
        it += n; //如果迭代器是随机访问迭代器（后面解释），它会使用 += 运算符来移动；
    } else {
        if (n >= 0) {
            while (n--) {
                ++it; //否则，它会使用循环来移动。
            }
        } else {
            while (n++) {
                --it;
            }
        }
    }
}

随机访问迭代器

• 随机访问迭代器是一种迭代器类型，它支持在常数时间内访问序列中的任何元素。
• 它们还支持指针算术运算，例如 + 和 - 运算符，以及下标运算符 []。
• 例如，对于一个指向数组的随机访问迭代器 it，可以使用以下语法访问第 i 个元素：*(it + i) or it[i]
• STL 中的容器 vector 和 deque 都提供了随机访问迭代器。除此之外，C++ 标准库中的很多算法也要求输入迭代器是随机访问迭代器，例如 std::sort 和 std::nth_element 等。

正向迭代器和反向迭代器

• 由于类型不同经常需要转换
• 对于一个正向迭代器 it，可以使用以下语法将其转换为反向迭代器rit：std::reverse_iterator<Iterator> rit(it);
• 反向迭代器可以使用以下语法转换为正向迭代器：

std::reverse_iterator<Iterator> rit;
Iterator it = rit.base();

反向遍历

• 建议使用rbegin rend。注意++it而不是--it。
• rbegin指向最后一个元素
• rend 指向reverse遍历的后一个元素。

for(auto it = collection.rbegin(); it != collection.rend(); ++it) {
    std::cout << *it << std::endl;
    // std::cout << it->first << ", " << it->second << std::endl;
}

• 错误的原始写法, 错误原因showedPositive.begin()==(--showedPositive.begin()。
• std设计了一个循环。
• 同样的设计在showedPositive.rend()==(++showedPositive.rend())
• 但是showedPositive.rbegin() != (--showedPositive.rbegin())

for(auto it=--showedPositive.end(); it!=--showedPositive.begin(); it--){

}

bitset

bitset类型存储二进制数位。

初始化

std::bitset<16> foo;
std::bitset<16> bar (0xfa2);
std::bitset<16> baz (std::string("0101111001"));

//foo: 0000000000000000
//bar: 0000111110100010
//baz: 0000000101111001

将数转化为其二进制的字符串表示

int i = 3;
string bin = bitset<16>(i).to_string(); //bin = "0000000000000011"
bin = bin.substr(bin.find('1'));        //bin = "11"

char 与 字符串

元音与index的相互映射

string vowel = "AEIOUaeiou";
if vowel.find(c) != std::string::npos;

voewl[0] = 'A';

string

读取空格分割的

stringstream txt(s);
string word;
while(txt>>word){
    // to do
}

遍历

string s;
for(auto && x : s)

打印string

printf("%s", your_string.c_str()); //不推荐
cout << your_string;

string不同于C语言的char来存储字符串

//复制
str3 = str1;    len = str3.size();
//连接
str1 = str1 + str2;  strcat( str1, str2);
//总长度
len = str3.size();  strlen(s1);

C++ string 成员函数 length() 等同于 size()，但是和 C 库函数 strlen() 有着本质区别

https://blog.csdn.net/K346K346/article/details/79546919

初始化

std::string s0 ("Initial string");

// constructors used in the same order as described above:
std::string s1;
std::string s2 (s0);
std::string s3 (s0, 8, 3);
std::string s4 ("A character sequence");
std::string s5 ("Another character sequence", 12);
std::string s6a (10, 'x');
std::string s6b (10, 42);      // 42 is the ASCII code for '*'
std::string s7 (s0.begin(), s0.begin()+7);

std::cout << "s1: " << s1 << "\ns2: " << s2 << "\ns3: " << s3;
std::cout << "\ns4: " << s4 << "\ns5: " << s5 << "\ns6a: " << s6a;
std::cout << "\ns6b: " << s6b << "\ns7: " << s7 << '\n';

//output
s1: 
s2: Initial string
s3: str
s4: A character sequence
s5: Another char
s6a: xxxxxxxxxx
s6b: **********
s7: Initial

插入insert

在指向位置的右边插入

// inserting into a string
#include <iostream>
#include <string>

int main ()
{
  std::string str="to be question";
  std::string str2="the ";
  std::string str3="or not to be";
  std::string::iterator it;

  // used in the same order as described above:
  str.insert(6,str2);                 // to be (the )question
  str.insert(6,str3,3,4);             // to be (not )the question
  str.insert(10,"that is cool",8);    // to be not (that is )the question
  str.insert(10,"to be ");            // to be not (to be )that is the question
  str.insert(15,1,':');               // to be not to be(:) that is the question
  it = str.insert(str.begin()+5,','); // to be(,) not to be: that is the question
  str.insert (str.end(),3,'.');       // to be, not to be: that is the question(...)
  str.insert (it+2,str3.begin(),str3.begin()+3); // (or )

  std::cout << str << '\n';
  return 0;
} 

尾部插入char

不同的方法

std::string s = "C+";
char ch = '+';

s.push_back(ch);
s += ch; //string::operator+=, which is overloaded for chars and internally calls to the push_back() function.
s.append(1, ch); //1*ch个字符
s.append("abcd"); //后面添加abcd字符串

std::stringstream ss;
ss << s << ch;
ss >> s;

s.insert(s.length(), 1, ch);

截取string

// Copy three characters of s1 (starting
// from position 1)
//第一个参数是要截取的字符串，第二个参数是截取的开始位置，第三个参数是截取长度（可选）1。如果没有指定长度，则子字符串将延续到源字符串的结尾。
string r = s1.substr(1, 3);

// Take any string
string s = "dog:cat";
// Find position of ':' using find()
int pos = s.find(":");
// Copy substring after pos(include pos)
string sub = s.substr(pos);
// Copy substring before pos(not include pos)
string sub = s.substr(0 , pos);

反转reverse string

reverse(greeting.begin(),greeting.end());

寻找子元素位置

// log1 中找空格
int pos1 = log1.find_first_of(" ");

// 判断数字
bool isDigit1 = isdigit(log1[pos1 + 1]);

// 判断是否找到
if(s.find(goal) != string::npos){
}

npos是一个常数，表示size_t的最大值（Maximum value for size_t）。许多容器都提供这个东西，用来表示不存在的位置，类型一般是std::container_type::size_type。

string erase

三种情况

// string::erase
#include <iostream>
#include <string>

int main ()
{
  std::string str ("This is an example sentence.");
  std::cout << str << '\n';
                                           // "This is an example sentence."
  str.erase (10,8);                        //            ^^^^^^^^
  //去除index=10的连续8个元素
  std::cout << str << '\n';
                                           // "This is an sentence."
  str.erase (str.begin()+9);               //           ^
  //去除itr指向的元素
  std::cout << str << '\n';
                                           // "This is a sentence."
  str.erase (str.begin()+5, str.end()-9);  //       ^^^^^
  //去除[first,last).的元素
  std::cout << str << '\n';
                                           // "This sentence."
  return 0;
}

删除最后一个元素

std::string s = "C,C++,Java,";
if (!s.empty()) {
 s.pop_back();
}

if (!s.empty()) {
 s.resize(s.size() - 1);
}

if (!s.empty()) {
 s.erase(std::prev(s.end()));
}

if (!s.empty()) {
 s.erase(s.size() - 1);
}

容器适配器

STL 提供了 3 种容器适配器，分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先权队列适配器。

stack 栈

stack<int> minStack;
minStack = stack<int>();

// 支持初始化，但是注意将整个数组元素推入堆栈，堆栈的顶部元素top将是数组的第一个元素。
std::vector<int> elements = {1, 2, 3, 4, 5};
std::stack<int> myStack(elements.begin(), elements.end());


!minStack.empty()
minStack.pop(); //该函数仅用于从堆栈中删除元素，并且没有返回值。因此，我们可以说该函数的返回类型为void。
minStack.push();
minStack.top();

stack

注意pop仅用于从堆栈中删除元素，并且没有返回值, 一般用法如下

top_value = stIn.top();
stIn.pop();

堆栈，先进先出

empty 该函数用于测试堆栈是否为空。如果堆栈为空，则该函数返回true，否则返回false。
size 该函数返回堆栈容器的大小，该大小是堆栈中存储的元素数量的度量。
top 该函数用于访问堆栈的顶部元素。该元素起着非常重要的作用，因为所有插入和删除操作都是在顶部元素上执行的。
push 该函数用于在堆栈顶部插入新元素。
pop 该函数用于删除元素，堆栈中的元素从顶部删除。
emplace 该函数用于在当前顶部元素上方的堆栈中插入新元素。
swap 该函数用于交换引用的两个容器的内容。

清空

stack不支持clear, 除开一个个pop

std::stack<int> myStack;
// 添加元素到 myStack

myStack = std::stack<int>(); // 清空 myStack, 丢弃原有对象

std::stack<int> emptyStack;
myStack.swap(emptyStack); // 清空 myStack

queue

empty() 如果 queue 中没有元素的话，返回 true。
size() 返回 queue 中元素的个数。

front() 返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
back() 返回 queue 中最后一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。

push(const T& obj) 在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。
emplace() 在 queue 的尾部直接添加一个元素。
push(T&& obj) 以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。
pop() 删除 queue 中的第一个元素。
swap(queue<T> &other_queue) 将两个 queue 容器适配器中的元素进行互换，需要注意的是，进行互换的 2 个 queue 容器适配器中存储的元素类型以及底层采用的基础容器类型，都必须相同。

特点

1. 队列中的数据元素遵循“先进先出”（First In First Out）的原则，简称FIFO结构；
2. 在队尾添加元素，在队头删除元素。

操作

c++ #include< queue> 。定义：queue< int > q;

q.empty()               如果队列为空返回true，否则返回false
q.size()                返回队列中元素的个数
q.pop()                 删除队列首元素但不返回其值
q.front()               返回队首元素的值，但不删除该元素
q.push()                在队尾压入新元素
q.back()                返回队列尾元素的值，但不删除该元素

C++ 清空队列(queue)的几种方法

直接用空的队列对象赋值

queue<int> q1;
// process
// ...
q1 = queue<int>();

使用swap，这种是最高效的，定义clear，保持STL容器的标准。

void clear(queue<int>& q) {
    queue<int> empty;
    swap(empty, q);
}

队列保存一对数

queue<pair<int, int> > gq;
gq.push({ 10, 20 });

pair<int, int> p;
int x,y;
p = gq.front();
x = p.first;
y = p.second;

队列保存结构体

typedef struct
{
    int y;
    int xbegin;
    int xend;
}triple;
queue<triple> threadq[64];
delaytask.push({x1+delay,y-1});
p = threadq[c].front(); 
p.xbegin;
p.xend;

deque 双端队列

deque 容器也擅长在序列尾部添加或删除元素（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。

begin() 返回指向容器中第一个元素的迭代器。
end() 返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。
rbegin() 返回指向最后一个元素的迭代器。
rend() 返回指向第一个元素所在位置前一个位置的迭代器。
cbegin() 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
cend() 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crbegin() 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crend() 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。

size() 返回实际元素个数。
max_size() 返回容器所能容纳元素个数的最大值。这通常是一个很大的值，一般是 232-1，我们很少会用到这个函数。
resize() 改变实际元素的个数。
empty() 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
shrink _to_fit() 将内存减少到等于当前元素实际所使用的大小。

at() 使用经过边界检查的索引访问元素。

front() 返回第一个元素的引用。
back() 返回最后一个元素的引用。
assign() 用新元素替换原有内容。
push_back() 在序列的尾部添加一个元素。
push_front() 在序列的头部添加一个元素。
pop_back() 移除容器尾部的元素。
pop_front() 移除容器头部的元素。

insert() 在指定的位置插入一个或多个元素。
erase() 移除一个元素或一段元素。
clear() 移出所有的元素，容器大小变为 0。
swap() 交换两个容器的所有元素。
emplace() 在指定的位置直接生成一个元素。
emplace_front() 在容器头部生成一个元素。和 push_front() 的区别是，该函数直接在容器头部构造元素，省去了复制移动元素的过程。
emplace_back() 在容器尾部生成一个元素。和 push_back() 的区别是，该函数直接在容器尾部构造元素，省去了复制移动元素的过程。

emplace_back() not support <brace-enclosed initializer list> for this

priority_queue(优先队列)

自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队

#include <queue>

优先级排序原理

缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

声明

priority_queue<Type, Container, Functional>

//自定义降序1
class _c{
public:

 bool operator () (const pair<int, int> &p, const pair<int, int> &q) const
 {
  return p.first < q.first;
 }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, _c> pq;
//自定义降序2
auto cmp = [](pair<int,int>&a, pair<int,int>&b){return a.second<=b.second;};
priority_queue<pair<int,int>,vector<pair<int,int>>, decltype(cmp)> q(cmp);
//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

//默认排序是less，但是在priority_queue是降序。在其余数据结构里都是升序
priority_queue<pair<int, int>> answer;
//example
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> busy;

1. Type 就是数据类型，
2. Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），
3. Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆

基本操作

size() 返回优先队列的大小。
empty() 它验证队列是否为空。基于验证，它返回队列的状态。

top() 此函数用于寻址优先队列的最顶层元素。

emplace() 它在优先队列的顶部插入一个新元素。
push() 它将新元素插入优先队列。
pop() 它将优先级最高的元素从队列中删除。
swap() 它将优先队列的元素与具有相同类型和大小的另一个队列交换。

顺序容器与关联容器

顺序容器包括vector、deque、list、forward_list、array、string，所有顺序容器都提供了快速顺序访问元素的能力。

关联容器包括set、map

关联容器和顺序容器有着根本的不同：关联容器中的元素是按关键字来保存和访问的。与之相对，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。

关联容器不支持顺序容器的位置相关的操作。原因是关联容器中元素是根据关键字存储的，这些操作对关联容器没有意义。而且，关联容器也不支持构造函数或插入操作这些接受一个元素值和一个数量值得操作。

关联容器支持高效的关键字查找和访问。

二叉树

分类

存储方式

链表，或者数组(如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。)

链式结构如下，注意左右孩子节点

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* a = new TreeNode();
a->val = 9;
a->left = NULL;
a->right = NULL;

遍历方式

深度遍历： 前/中/后序遍历。

注意：这里前中后，其实指的就是中间节点/根节点的遍历顺序

heap 堆

堆(Heap)是计算机科学中一类特殊的数据结构的统称。

堆通常是一个可以被看做一棵完全二叉树的数组对象。

堆满足下列性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值。
• 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
• 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
• 堆总是一棵完全二叉树。

STL操作

• make_heap()​​将区间内的元素转化为heap.
• ​push_heap()​​对heap增加一个元素.
• ​​pop_heap()​​对heap取出下一个元素.
• ​sort_heap()​​对heap转化为一个已排序群集.

int myints[] = {10,20,30,5,15};
vector<int> v(myints,myints+5);
vector<int>::iterator it;

make_heap (v.begin(),v.end());//male_heap就是构造一棵树，使得每个父结点均大于等于其子女结点
cout << "initial max heap   : " << v.front() << endl;

pop_heap (v.begin(),v.end());//pop_heap不是删除某个元素而是把第一个和最后一个元素对调后[first,end-1]进行构树，最后一个不进行构树
v.pop_back();//删除最后一个的结点
cout << "max heap after pop : " << v.front() << endl;

v.push_back(99);//在最后增加一个结点
push_heap (v.begin(),v.end());//重新构树
cout << "max heap after push: " << v.front() << endl;

sort_heap (v.begin(),v.end());//把树的结点的权值进行排序，排序后，序列将失去堆的特性
//请在使用这个函数前，确定序列符合堆的特性，否则会报错！

hash_map VS unordered_map

由于在C++标准库中没有定义散列表hash_map，标准库的不同实现者将提供一个通常名为hash_map的非标准散列表。因为这些实现不是遵循标准编写的，所以它们在功能和性能保证上都有微妙的差别。

从C++11开始，哈希表实现已添加到C++标准库标准。决定对类使用备用名称，以防止与这些非标准实现的冲突，并防止在其代码中有hash_table的开发人员无意中使用新类。

所选择的备用名称是unordered_map，它更具描述性，因为它暗示了类的映射接口和其元素的无序性质。

可见hash_map ， unordered_map本质是一样的，只不过 unordered_map被纳入了C++标准库标准。

map vs unordered_map

1. map
2. 内部数据的组织，基于红黑树实现，红黑树具有自动排序的功能，因此map内部所有的数据，在任何时候，都是有序的。其中每个键都是唯一的，可以插入或删除，但不能更改。但是与键关联的值可以更改。
3. 红黑树是一种含有红黑结点并能自平衡的二叉查找/搜索树, 别称平衡二叉B树（symmetric binary B-trees）
4. unordered_map(hash_map)
5. 基于哈希表，数据插入和查找的时间复杂度很低，几乎是常数时间，而代价是消耗比较多的内存。底层实现上，使用一个下标范围比较大的数组来存储元素，形成很多的桶，利用hash函数对key进行映射到不同区域进行保存。
6. 标准库的unordered_map，底层实现是基于hashtable的，其避免冲突的方法是使用开链（seperate chaining）法，这种做法是在每一个表格元素中维护一个list，每个表格元素称之为buket（桶）

                       | map              | unordered_map
---------------------------------------------------------
element ordering       | strict weak      | n/a 
                       |                  |
common implementation  | balanced tree    | hash table
                       | or red-black tree|  
                       |                  |
search time            | log(n)           | O(1) if there are no hash collisions
                       |                  | Up to O(n) if there are hash collisions 
                       |                  | O(n) when hash is the same for any key
                       |                  |     
Insertion time         | log(n)+rebalance | Same as search
                       |                  | 
Deletion time          | log(n)+rebalance | Same as search
                       |                  | 
needs comparators      | only operator <  | only operator ==
                       |                  |
needs hash function    | no               | yes
                       |                  |
common use case        | when good hash is| In most other cases. 
                       | not possible or  | 
                       | too slow. Or when|
                       | order is required| 

map初始化

//c++11以上
map<string,int> m3 = {
    {"string",1}, {"sec",2}, {"trd",3}
    };

map<string,string> m4 = {
{"first","second"}, {"third","fourth"},
{"fifth","sixth"}, {"begin","end"}
};

unordered_map 哈希表

unordered_map<int, int> umap;
umap[a + b]++;

map的value是int，默认为0。可以直接++

unordered_map<int, int> cnt;
++cnt[num];
// c++17 支持
for (auto &[num, c] : cnt) {
}
// 否则
for (auto it = cnt.begin(); it != cnt.end(); ++it) {
    auto& key = it->first;
    auto& value = it->second;
    // 使用 key 和 i 进行操作
}
for (auto &[x, _] : cnt) {
    //sth
}
cnt.at(num) //unordered_map 类模板中，还提供有 at() 成员方法，和使用 [ ] 运算符一样，at() 成员方法也需要根据指定的键，才能从容器中找到该键对应的值；不同之处在于，如果在当前容器中查找失败，该方法不会向容器中添加新的键值对，而是直接抛出out_of_range异常。

插入元素

// insert 不能覆盖元素，已经存在会失败
mapStudent.insert(map<int, string>::value_type (1, "student_one"));
// 数组方式可以覆盖
mapStudent[1] = "student_one";  

可以用pair来获得是否insert成功，程序如下

pair<map<int, string>::iterator, bool> Insert_Pair;

Insert_Pair = mapStudent.insert(map<int, string>::value_type (1, "student_one"));

我们通过pair的第二个变量来知道是否插入成功，它的第一个变量返回的是一个map的迭代器，如果插入成功的话Insert_Pair.second应该是true的，否则为false。

查找是否存在 count

用count函数来判定关键字是否出现，其缺点是无法定位数据出现位置,由于map的特性，一对一的映射关系，就决定了count函数的返回值只有两个，要么是0，要么是1，出现的情况，当然是返回1了

查找是否存在 find

通过 find() 方法得到的是一个正向迭代器，该迭代器的指向分以下 2 种情况：

1. 当 find() 方法成功找到以指定元素作为键的键值对时，其返回的迭代器就指向该键值对；
2. 当 find() 方法查找失败时，其返回的迭代器和 end() 方法返回的迭代器一样，指向容器中最后一个键值对之后的位置。

//查找成功
unordered_map<string, string>::iterator iter = umap.find("Python教程");
cout << iter->first << " " << iter->second << endl;
//查找失败
unordered_map<string, string>::iterator iter2 = umap.find("GO教程");
if (iter2 == umap.end()) {
    cout << "当前容器中没有以\"GO教程\"为键的键值对";
}

删除

mymap.erase ('c');               // erasing by key

set

1. 按关键字有序保存元素：
2. set(关键字即值，即只保存关键字的容器)；
3. multiset(关键字可重复出现的set)；
4. 无序集合：
5. unordered_set(用哈希函数组织的set)；
6. unordered_multiset(哈希组织的set，关键字可以重复出现)。

set就是关键字的简单集合。当只是想知道一个值是否存在时，set是最有用的。

在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。set中元素的值不能直接被改变。set内部采用的是一种非常高效的平衡检索二叉树：红黑树，也称为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树。

set具备的两个特点：

• set中的元素都是排序好的
• set中的元素都是唯一的，没有重复的

常用函数

定义的参数compare可见，为了确定唯一性，需要有个值唯一表示存储的复杂类型

template < class T,                             // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           class Alloc = allocator<T>         // set::allocator_type
           > class set;

//初始化
set<char> vowel {'a','e','i','o','u'};

insert()–在集合中插入元素
emplace() 最大的作用是避免产生不必要的临时变量
erase()–删除集合中的元素
//删除 set 容器中值为 val 的元素
size_type erase (const value_type& val);
//删除 position 迭代器指向的元素
iterator  erase (const_iterator position);
//删除 [first,last) 区间内的所有元素
iterator  erase (const_iterator first, const_iterator last);
//第 1 种格式的 erase() 方法，其返回值为一个整数，表示成功删除的元素个数；
//后 2 种格式的 erase() 方法，返回值都是迭代器，其指向的是 set 容器中删除元素之后的第一个元素。

find()–返回一个指向被查找到元素的迭代器。返回值：该函数返回一个迭代器，该迭代器指向在集合容器中搜索的元素。如果找不到该元素，则迭代器将指向集合中最后一个元素之后的位置end
count()- 查找的bool结果
size()–集合中元素的数目

begin();            // 返回指向第一个元素的迭代器
end();              // 返回指向迭代器的最末尾处（即最后一个元素的下一个位置）
clear();            // 清除所有元素
count();            // 返回某个值元素的个数

swap()–交换两个集合变量

template <class T, class Compare, class Alloc>
  bool operator== ( const set<T,Compare,Alloc>& lhs,
                    const set<T,Compare,Alloc>& rhs ); // 和map类似的，重载相等判断

set::lower_bound(key)

參數：該函數接受單個強製性參數鍵，該鍵指定要返回其lower_bound的元素。

返回值：該函數返回一個指向容器中元素的迭代器，該迭代器等效於在參數中傳遞的k。如果set容器中不存在k，則該函數返回一個迭代器，該迭代器指向剛好大於k的下一個元素。如果參數中傳遞的鍵超過了容器中的最大值，則返回的迭代器等效於s.end()(特殊的迭代器指向最後一個元素)。

find example

//set.find(key)!=set.end() 的判断一般会比count快
auto p = points.find({x, y});
if (p != points.end()) {
 points.erase(p);
 ……
}

// 检查键30是否存在
if (mp.count(30))
 cout << "键30存在\n";
else
 cout << "键30不存在\n";

unordered_set

auto hash_p = [](const pair<int, int> &p) -> size_t {
  static hash<long long> hash_ll;
  return hash_ll(p.first + (static_cast<long long>(p.second) << 32));
 };
unordered_set<pair<int, int>, decltype(hash_p)> points(0, hash_p); //(0,hash_p)分别为迭代器的开始和结束的标记（数组多为数据源）
//多用于数组 set<int> iset(arr,arr+sizeof(arr)/sizeof(*arr));

类似的例子

auto hash = [](const std::pair<int, int>& p){ return p.first * 31 + p.second; };
std::unordered_set<std::pair<int, int>, decltype(hash)> u_edge_(8, hash);

上面的不是用lambda expression隐函数，而是定义函数的写法

struct pair_hash {
    inline std::size_t operator()(const std::pair<int,int> & v) const {
        return v.first*31+v.second;
    }
};
std::unordered_set< std::pair<int, int>,  pair_hash> u_edge_;

How to use unordered_set with custom types?

https://stackoverflow.com/questions/9729390/how-to-use-unordered-set-with-custom-types/9729747#9729747

set map 的区别

map和set都是C++的关联容器，其底层实现都是红黑树（RB-Tree）。由于 map 和set所开放的各种操作接口，RB-tree 也都提供了，所以几乎所有的 map 和set的操作行为，都只是转调 RB-tree 的操作行为。 map和set区别在于：

（1）map中的元素是key-value（关键字—值）对：关键字起到索引的作用，值则表示与索引相关联的数据；Set与之相对就是关键字的简单集合，set中每个元素只包含一个关键字。

（2）set的迭代器是const的，不允许修改元素的值；map允许修改value，但不允许修改key其原因是因为map和set是根据关键字排序来保证其有序性的，如果允许修改key的话，那么首先需要删除该键，然后调节平衡，再插入修改后的键值，调节平衡，如此一来，严重破坏了map和set的结构，导致iterator失效，不知道应该指向改变前的位置，还是指向改变后的位置。所以STL中将set的迭代器设置成const，不允许修改迭代器的值；而map的迭代器则不允许修改key值，允许修改value值。

（3）map支持下标操作，set不支持下标操作。map可以用key做下标，map的下标运算符[ ]将关键码作为下标去执行查找，如果关键码不存在，则插入一个具有该关键码和mapped_type类型默认值的元素至map中，因此下标运算符[ ]在map应用中需要慎用，const_map不能用，只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用，mapped_type类型没有默认值也不应该使用。如果find能解决需要，尽可能用find。

map和multimap的区别

map不允许相同key值存在，multimap则允许相同的key值存在。

set/map 后insert 先输出

由于是有序的，对于int这种能比大小的，默认是输出是从小到大，可以改变。

• set中存放的为数（整数，浮点数......），在set中会按从小到大排列这些数
• 存放指针，都会按照地址排序
• set 中存放的为string，存入的string会按字母表顺序排列
• 至于存放类的话，还可以自己定义排列规则
• 存放结构体？没定义大小关系的类？
• *it 递增的顺序，存储的是指向某元素的指针，则是指针地址递增的顺序。

并差集

核心是

1. 同一个并查集内的元素会指向同一个parent
2. 可以维护并查集总个数Rank
3. 和每个并查集的子集合元素个数
4. 数据结构用数组和map都行

例子是LeetCode 1020

class UnionFind {
public:
    // 初始化未union的数组
    UnionFind(const vector<vector<int>> & grid) {//初始化遍历
        int m = grid.size(), n = grid[0].size();
        this->parent = vector<int>(m * n);
        //this->onEdge = vector<bool>(m * n, false);
        this->rank = vector<int>(m * n, 0);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int index = i * n + j;
                    parent[index] = index;
                    if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                        //onEdge[index] = true;
                    }
                }
            }
        }
    }

    int find(int i) {
        // 原始版本
        return (parent[i] == i)? i : find(parent[i]);
        // “路径压缩”。在执行Find的过程中，将路径上的所有节点都直接连接到根节点上。
        return (parent[i] == i)? i : (parent[i] = find(parent[i]));
    }

    void uni(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            // "按秩合并"。实际上就是在合并两棵树时，将高度较小的树合并到高度较大的树上。
            if (rank[rootx] > rank[rooty]) {
                parent[rooty] = rootx;
            } else if (rank[rootx] < rank[rooty]) {
                parent[rootx] = rooty;
            } else {
                parent[rooty] = rootx;
                rank[rootx]++;
            }
        }
    }

private:
    vector<int> parent;
    vector<int> rank;  
    // 如果带合并的元素表示有负数表示，或者不是连续表示的。可以使用map
    map<int, int> parent;//定义一个并查集
    map<int, int> ranks;//定义树的深
};

对于不确定元素个数来初始化的

class DisjointSet {
  public:
    std::unordered_map<BBLID, BBLID> parent;

    BBLID Find(BBLID l) {
        auto it = parent.find(l);
        if (it == parent.end()) {
            parent[l] = l;
        }
        else {
            while (parent[l] != l) {
                // 路径压缩部分
                parent[l] = parent[parent[l]];
                l = parent[l];
            }
        }
        return l;
    }

    void Union(BBLID m, BBLID n) {
        BBLID x = Find(m);
        BBLID y = Find(n);
        parent[x] = y;
    }
};

emplace VS push

push() adds a copy of an already constructed object into the queue as a parameter, it takes an object of the queue's element type.

emplace() constructs a new object in-place at the end of the queue. It takes as parameters the parameters that the queue's element types constructor takes.

If your usage pattern is one where you create a new object and add it to the container, you shortcut a few steps(creation of a temporary object and copying it) by using emplace().

数组

int array[2][3] = {
  {0, 1, 2},
  {3, 4, 5}
    };

数组初始化为0

//直接初始化为0
int a[SIZE]={0};

#include<string.h>
int a[SIZE];
memset(a, 0, sizeof(a));
memset(a, 0, sizeof(int)*1000);//这里的1000是数组大小，需要多少替换下就可以了。 

注意 memset是按照字节进行赋值，即对每一个字节赋相同值。除开0和-1，其他值都是不安全的，不会赋值期望的值。比如int是四个字节。

• memset（a，127，sizeof（a）），全部初始化为int的较大值，即2139062143(int 最大值为2147483647)；
• memset（a，128，sizeof（a）），全部初始化为一个很小的数，比int最小值略大，为-2139062144。

calloc & malloc

//区分
//calloc() 函数是动态申请内存函数之一，相当于用malloc函数申请并且初始化一样，calloc函数会将申请的内存全部初始化为0。
int *res = (int*)calloc(numsSize, sizeof(int)); 
//方法二：
int *res = (int*)malloc(numsSize * sizeof(int));
memset(res, 0, numsSize * sizeof(int));
//错误写法： memset(res, 0, sizeof(res)); res是指针变量，不管 res 指向什么类型的变量，sizeof( res ) 的值都是 4。

new

int *p = new int();//此时p指向内存的单变量被初始化为0
int *p = new int (5);//此时p指向内存的单变量被初始化为5
int *p = new int[100]()//此时p指向数组首元素，且数组元素被初始化为0
//c++11 允许列表初始化，因此也有了以下几种形式形式
int *p = new int{}//p指向的单变量被初始化为0
int *p = new int{8}//p指向变量被初始化为8
int *p = new int[100]{}//p指向的数组被初始化为0
int *p = new int[100]{1,2,3}//p指向数组的前三个元素被初始化为1，2，3，后边97个元素初始化为0；

new 三维数组

建议老实用vector

int ***array;
// 假定数组第一维为 m， 第二维为 n， 第三维为h
// 动态分配空间
array = new int **[m];
for( int i=0; i<m; i++ )
{
    array[i] = new int *[n];
    for( int j=0; j<n; j++ )
    {
        array[i][j] = new int [h];
    }
}
//释放
for( int i=0; i<m; i++ )
{
    for( int j=0; j<n; j++ )
    {
        delete[] array[i][j];
    }
    delete[] array[i];
}
delete[] array;

Leetcode support VLA

• The C++ standard does not officially support Variable Length Arrays (VLA), but some compilers, such as g++ and Clang++, may accept it as valid syntax as an extension to the language.
• leetcode uses g++ 5.4.0 compiler for C++ compilation. It supports variable length array definitions. After ISO C99 specification, arrays with variable length declarations are allowed.
• The storage is allocated at the point of declaration and deallocated when the block scope containing the declaration exits.
• And memory consumption differ significantly.

class Solution {
public:
    int minimizeConcatenatedLength(vector<string>& words) {
        int n = words.size();
        int f[n][26][26];

pair

pair<T1, T2> p1;            //创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化。
pair<T1, T2> p1(v1, v2);    //创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2。
make_pair(v1, v2);          // 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。
p1 < p2;                    // 两个pair对象间的小于运算，其定义遵循字典次序：如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。
p1 == p2；                  // 如果两个对象的first和second依次相等，则这两个对象相等；该运算使用元素的==操作符。
p1.first;                   // 返回对象p1中名为first的公有数据成员
p1.second;                 // 返回对象p1中名为second的公有数据成员

array

array也位于名称空间std中,与数组同样,array对象的长度也是固定的,也使用栈(静态内存分配),而不是自由存储区,所以其效率与数组相同,但更方便,更安全.

array<typeName, nElem> arr;

# include <array>
using namespace std;
array<int, 5> ai;
array<double, 4> ad = {1.1,1.2,1.2,1.3};

//通过如下创建 array 容器的方式，可以将所有的元素初始化为 0 或者和默认元素类型等效的值：
std::array<double, 10> values {};
//使用该语句，容器中所有的元素都会被初始化为 0.0。

//二维
std::array<std::array<int, 2>, 3> m = { {1, 2}, {3, 4}, {5, 6} };

单链表 （自定义）

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

ListNode* head = new ListNode(5);

或者
ListNode* head = new ListNode();
head->val = 5;

while(result != nullptr && result->val == val){
 //多使用nullptr 
 ListNode* tmp_free = result;
 result = result->next;
 delete tmp_free; // 注意释放空间
}

nullptr是一个关键字，可以在所有期望为NULL的地方使用。

• 与NULL一样，可与任何指针类型相比较。
• 与NULL不同，只能被赋值给指针类型，它不能隐式转换，也不能与整型相比较。与NULL通常被定义为整数0的宏定义 之间来区分。

list 双向链表

STL list 容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。

• 特点：
• 可以看到，list 容器中各个元素的前后顺序是靠指针来维系的，每个元素都配备了 2 个指针，分别指向它的前一个元素和后一个元素。其中第一个元素的前向指针总为 null，因为它前面没有元素；同样，尾部元素的后向指针也总为 null。
• vector是连续的容器，而list是非连续的容器，即vector将元素存储在连续的存储器中，而list存储在不连续的存储器中。
• 优点
• list 容器具有一些其它容器（array、vector 和 deque）所不具备的优势，
• 可以在序列已知的任何位置快速插入或删除元素（时间复杂度为O(1)）。
• 并且在 list 容器中移动元素，也比其它容器的效率高。
• 缺点
• 不能像 array 和 vector 那样，通过位置直接访问元素。
  • 举个例子，如果要访问 list 容器中的第 6 个元素，它不支持容器对象名[6]这种语法格式，正确的做法是从容器中第一个元素或最后一个元素开始遍历容器，直到找到该位置。
• 应用场景：需要对序列进行大量添加或删除元素的操作，而直接访问元素的需求却很少，这种情况建议使用 list 容器存储序列。

list<pair<unordered_set<string>, int>> lst;
unordered_map<string, list<pair<unordered_set<string>, int>>::iterator> nodes;

auto cur = nodes[key], nxt = next(cur); //对迭代器使用next
nodes[key] = lst.emplace(nxt, s, cur->second + 1);

*lst.rbegin()->first.begin(); //链表最后元素的first也就是unordered_set<string>的第一个

emplace & emplace_front

C ++ List emplace()函数在指定位置插入新元素，并且列表的大小增加一。

语法 iterator emplace(iterator pos, value_type val); 参数

pos：它定义了要插入新元素的位置。

val：要在指定位置插入的新值。

返回值

它返回指向新构造元素的迭代器。

vector

构造函数

vector(int nSize)   //创建一个vector,元素个数为nSize

//指定值初始化，ilist5被初始化为包含7个值为3的int
vector(int nSize,const t& t)//创建一个vector，元素个数为nSize,且值均为t
vector<int> ilist5(7,3);
//区分列表初始化, 包含7 和 3两个元素
vector<int> ilist5{7,3};

//改变大小
vals.reserve(cnt.size());

二维vector, 两个维度的长度都未知时：

vector<vector<bool>> name (xSize, vector<bool>(ySize, false));
//leetcode假如写在函数外，class public下，第二维度为空
vector<vector<int>> alphaIndexList{26, vector<int>(0)}; 
//指针使用
vector<int>* todo;
todo= &alphaIndexList[i];
int n = todo->size(); // (*todo).size();
for(auto &x: *todo)

二维vector, 已知某一个维度的大小:

vector<int> alphaIndexList[26];
alphaIndexList[i].push_back(x);

返回表示

vector<int> func() {
    //sth
    return {it->second, i}; //no []
    //or
    return {};
}

元素排序

如果需要元素有序，考虑stable_sort

//默认是从低到高，加入std::greater<int>() 变成从高到低排序
sort(nums.begin(),nums.end(),std::greater<int>());

//vector of pair
vector<pair<int, char>> arr = {{a, 'a'}, {b, 'b'}, {c, 'c'}};

//c++14 
std::sort(v.begin(), v.end(), [](auto &left, auto &right) {
    return left.second < right.second;
});

//C++11 using lambdas
sort(arr.begin(), arr.end(), 
 [](const pair<int, char> & p1, const pair<int, char> & p2) {
  return p1.first > p2.first;
 }
);

//origin 
struct sort_pred {
    bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {
        return left.second < right.second;
    }
};
std::sort(v.begin(), v.end(), sort_pred());

增加函数

void push_back(const T& x)      :向量尾部增加一个元素X
void emplace_back(const T& x)
iterator insert(iterator it,const T& x)   :向量中迭代器指向元素前增加一个元素x
result.insert(result.begin()+p,x);     :在result的index为p的位置插入元素
iterator insert(iterator it,int n,const T& x) :向量中迭代器指向元素前增加n个相同的元素x
iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据

删除函数

iterator erase(iterator it)     :删除向量中迭代器指向元素
iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
void pop_back()        :删除向量中最后一个元素
void clear()        :清空向量中所有元素

遍历查找函数

reference at(int pos)  :返回pos位置元素的引用
reference front()   :返回首元素的引用
reference back()   :返回尾元素的引用
iterator begin()   :返回向量头指针，指向第一个元素
iterator end()    :返回向量尾指针，指向向量最后一个元素的下一个位置
reverse_iterator rbegin() :反向迭代器，指向最后一个元素
reverse_iterator rend()  :反向迭代器，指向第一个元素之前的位置

upper_bound(prefix_sum.begin(),prefix_sum.end(),a) : 查找满足prefix_sum[i]<=a的最大i

判断函数

bool empty() const   :判断向量是否为空，若为空，则向量中无元素

大小函数

int size() const  :返回向量中元素的个数
int capacity() const :返回当前向量所能容纳的最大元素值
int max_size() const :返回最大可允许的vector元素数量值

#include <algorithm> 
// C++ vector 容器裡使用 std::max_element 找最大值（或者min_element）的範例，std::max_element 會回傳一個迭代器，這個迭代器會指向該容器範圍內最大值的元素，
vector<int>::iterator result = std::max_element(v.begin(), v.end());
int index = result - v.begin();
int value = (*result)

片段的截取

vector<int> Arrs {1,2,3,4,5,6,7,8,9}; // 假设有这么个数组,要截取中间第二个元素到第四个元素：2，3，4
vector<int>::const_iterator First = Arrs.begin() + 1; // 找到第二个迭代器
vector<int>::const_iterator Second = Arrs.begin() + 3; // 找到第三个迭代器
vector<int> Arrs2(First, Second); // 将值直接初始化到Arrs2

迭代器是指可在容器对象上遍访的对象

或者assign()功能函数实现截取

assign() 功能函数是vector容器的成员函数。原型：

1:void assign(const_iterator first,const_iterator last);//两个指针，分别指向开始和结束的地方 2:void assign(size_type n,const T& x = T()); //n指要构造的vector成员的个数， x指成员的数值，他的类型必须与vector类型一致！

vector<int> Arrs {1,2,3,4,5,6,7,8,9}; // 假设有这么个数组,要截取中间第二个元素到第四个元素：2，3，4
vector<int>::const_iterator First = Arrs.begin() + 1; // 找到第二个迭代器
vector<int>::const_iterator Second = Arrs.begin() + 3; // 找到第三个迭代器
vector<int> Arr2;
Arr2.assign(First,Second); //使用assign() 成员函数将Arrs对应位置的值存入Arrs2数组中

迭代器的使用

#include <algorithm> 
double max = *max_element(vector.begin(), vector.end());
cout<<"Max value: "<<max<<endl;

vector<int>::iterator i;  //定义正向迭代器
for (i = v.begin(); i != v.end(); ++i) {  //用迭代器遍历容器
    cout << *i << " ";  //*i 就是迭代器i指向的元素
    *i *= 2;  //每个元素变为原来的2倍
}
cout << endl;
//用反向迭代器遍历容器
for (vector<int>::reverse_iterator j = v.rbegin(); j != v.rend(); ++j)
    cout << *j << " ";

迭代器之间的减法是被允许的，两个迭代器相减返回是它们之间的距离，这个距离是一个符号类整型（signed），意味着两个迭代器之间相减可能是正数、零或者负数。

其他赋值函数

void swap(vector&)    :交换两个同类型向量的数据
void assign(int n,const T& x) :设置向量中前n个元素的值为x
void assign(const_iterator first,const_iterator last):向量中[first,last)中元素设置成当前向量元素

#include <algorithm> //或者#include <bits/stdc++.h>
reverse(a.begin(), a.end());
std::reverse(a,a+5);  //转换0～5下标的元素

fill(ForwardIt first, ForwardIt last, const T& value) //fill函数的作用是：将一个区间的元素都赋予val值。函数参数：fill(first,last,val);//first为容器的首迭代器，last为容器的末迭代器，val为将要替换的值。
fill_n(OutputIt first, Size count, const T& value) //fill_n函数的作用是：给你一个起始点，然后再给你一个数值count和val。把从起始点开始依次赋予count个元素val的值。

vector具体实现

（1）扩容

vector的底层数据结构是数组。

当vector中的可用空间耗尽时，就要动态第扩大内部数组的容量。直接在原有物理空间的基础上追加空间？这不现实。数组特定的地址方式要求，物理空间必须地址连续，而我们无法保证其尾部总是预留了足够空间可供拓展。一种方法是，申请一个容量更大的数组，并将原数组中的成员都搬迁至新空间，再在其后方进行插入操作。新数组的地址由OS分配，与原数据区没有直接的关系。新数组的容量总是取作原数组的两倍。

（2）插入和删除

插入给定值的过程是，先找到要插入的位置，然后将这个位置（包括这个位置）的元素向后整体移动一位，然后将该位置的元素复制为给定值。删除过程则是将该位置以后的所有元素整体前移一位。

（2）vector的size和capacity

size指vector容器当前拥有的元素个数，capacity指容器在必须分配新存储空间之前可以存储的元素总数，capacity总是大于或等于size的。

size() – 返回目前存在的元素数。即： 元素个数
capacity() – 返回容器能存储 数据的个数。 即：容器容量
reserve() --设置 capacity 大小
resize() --设置 size ，重新指定有效元素的个数 ，区别与reserve()指定 容量的大小
clear() --清空所有元素，把size设置成0，capacity不变

针对capacity这个属性，STL中的其他容器，如list map set deque，由于这些容器的内存是散列分布的，因此不会发生类似realloc()的调用情况，因此我们可以认为capacity属性针对这些容器是没有意义的，因此设计时这些容器没有该属性。

在STL中，拥有capacity属性的容器只有vector和string。

为何map和set的插入删除效率比用其他序列容器高？

因为对于关联容器来说，不需要做内存拷贝和内存移动。说对了，确实如此。map和set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。

插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点就OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。

std::map的优势: 内存池的管理

自己实现的map需要自己去new一些节点，当节点特别多， 而且进行频繁的删除和插入的时候，内存碎片就会存在，而STL采用自己的Allocator分配内存，以内存池的方式来管理这些内存，会大大减少内存碎片，从而会提升系统的整体性能。

为什么有时unordered_map, 性能比map差

注意到很多代码使用 std::unordered_map 因为“哈希表更快”。但是对于小map，具有很高的内存开销。

网上有许多map和unorderd_map的比较，但是都是大例子。

下载一个，比较N比较小时的速度。前面是插入，后面是读取时间。编译g++ -std=c++11 -O3 map.cpp -o main

$ ./main
insert N=15,cost=               9e-06 sec
[] N=15,cost=                   5e-06 sec
insert N=15,cost=               3e-06 sec
getall find not N=15,cost=      1.2e-05 sec
getall find N=15,cost=          1.4e-05 sec
getall find not N=15,cost=      1e-05 sec
getall cout N=15,cost=          1.3e-05 sec
getall cout not N=15,cost=      1.3e-05 sec

insert N=15,cost=               6e-06 sec
[] N=15,cost=                   2e-06 sec
insert N=15,cost=               3e-06 sec
getall find not N=15,cost=      1.9e-05 sec
getall find N=15,cost=          2e-05 sec
getall find not N=15,cost=      1.9e-05 sec
getall cout N=15,cost=          3.7e-05 sec
getall cout not N=15,cost=      2e-05 sec

insert N=15,cost=               3e-06 sec
[] N=15,cost=                   2e-06 sec
insert N=15,cost=               1e-06 sec
getall find not N=15,cost=      2e-05 sec
getall find N=15,cost=          1.8e-05 sec
getall find not N=15,cost=      1.9e-05 sec
getall cout N=15,cost=          1.8e-05 sec
getall cout not N=15,cost=      1.9e-05 sec

insert N=15,cost=               5e-06 sec
[] N=15,cost=                   1e-06 sec
insert N=15,cost=               2e-06 sec
getall find not N=15,cost=      7e-06 sec
getall find N=15,cost=          8e-06 sec
getall find not N=15,cost=      7e-06 sec
getall cout N=15,cost=          8e-06 sec
getall cout not N=15,cost=      1e-05 sec

可见创建 unorderd_map快于map。

map find没命中会很快，差不多unorderd_map。

但是map命中会慢很多。1.2e-05 >> 2e-06

array,vector与数组的区别

共同点

（1.）都和数组相似，都可以使用标准数组的表示方法来访问每个元素（array和vector都对下标运算符[ ]进行了重载）

（2.）三者的存储都是连续的，可以进行随机访问

不同点

（0.）数组是不安全的，array和vector是比较安全的（有效的避免越界等问题）

（1.）array对象和数组存储在相同的内存区域（栈）中，vector对象存储在自由存储区（堆）malloc和new的空间也是在堆上，原因是栈的空间在编译代码的时候就要确定好，堆空间可以运行时分配。

（2.）array可以将一个对象赋值给另一个array对象，但是数组不行

（3.）vector属于变长的容器，即可以根据数据的插入和删除重新构造容器容量；但是array和数组属于定长容器

（4.）vector和array提供了更好的数据访问机制，即可以使用front()和back()以及at()（at()可以避免a[-1]访问越界的问题）访问方式，使得访问更加安全。而数组只能通过下标访问，在写程序中很容易出现越界的错误

（5.）vector和array提供了更好的遍历机制，即有正向迭代器和反向迭代器

（6.）vector和array提供了size()和Empty()，而数组只能通过sizeof()/strlen()以及遍历计数来获取大小和是否为空

（7.）vector和array提供了两个容器对象的内容交换，即swap()的机制，而数组对于交换只能通过遍历的方式逐个交换元素

（8.）array提供了初始化所有成员的方法fill（）

（9.）由于vector的动态内存变化的机制，在插入和删除时，需要考虑迭代的是否有效问题

（10.）vector和array在声明变量后，在声明周期完成后，会自动地释放其所占用的内存。对于数组如果用new[ ]/malloc申请的空间，必须用对应的delete[ ]和free来释放内存

vector 存储可变大小类型

• vector是变长的连续存储，
• 对于简单的类型，是直接存储
• 对于复杂的类，存储的是，该元素的信息（比如新构造元素的begin地址,end地址,capacity信息)

vector<vector<int>> v2d(3,vector<int>(0));      // 间隔 6 个int
// vector<set<int>> v2d(3);                     // 间隔 12 个int 
// vector<unordered_set<int>> v2d(3);           // 间隔 14 个int 
// vector<map<int,int>> v2d(3);                 // 间隔 12 个int 
// vector<unordered_map<int,int>> v2d(3);       // 间隔 14 个int 

const int STEP = 6;
for(int i = 0; i<v2d.size(); i++){
    cout << " " << &v2d[i] << endl;
    for(int j=0; j<STEP; j++)
        cout << " " << hex << *(int *)((void *)(&v2d[i])+j*4);
    cout << endl;
}

// add elements to v2d[0]
const int ADDNUM = 10;
for(int i = 0; i<ADDNUM; i++){
    v2d[0].emplace_back(2);
    // v2d[0].insert(i);
    // v2d[0][i]=i*i;
}

// check the space change
cout << "Ele[0] size : " << v2d[0].size() << endl;
for(int i = 0; i<v2d.size(); i++){
    cout << " " << &v2d[i] << endl;
}

//check ele[0] location
cout << endl;
for(int i = 0; i<ADDNUM; i++){
    cout << " " << &v2d[0][i];
}

hash

哈希

#include<functional> 
auto hash_p = [](const pair<int, int> &p) -> size_t {
            static hash<long long> hash_ll;
            return hash_ll(p.first + (static_cast<long long>(p.second) << 32));//64位高低一半存储x和y
        };

static_cast 用于良性类型转换，一般不会导致意外发生，风险很低。

hash <K> 模板专用的算法取决于实现，但是如果它们遵循 C++14 标准的话，需要满足一些具体的要求。这些要求如下：

• 不能拋出异常
• 对于相等的键必须产生相等的哈希值
• 对于不相等的键产生碰撞的可能性必须最小接近 size_t 最大值的倒数

C++11技巧

https://shaojiemike.notion.site/C-11-a94be53ca5a94d34b8c6972339e7538a

map VS unordered_map 时间比较

/**
比较map、hash_map和unordered_map的执行效率以及内存占用情况
**/
#include "parallel-hashmap/parallel_hashmap/phmap.h"
#include <sys/types.h>
#include <unistd.h>
#include <sys/time.h> 
#include <iostream>
#include <fstream>
#include <string>
#include <map>
// #include <ext/hash_map>
#include <tr1/unordered_map>
#include <unordered_map>

#include <cstring>

using namespace std;

// using namespace __gnu_cxx;

using namespace std::tr1;

#define N 15  //分别测试N=100,000、N=1,000,000、N=10,000,000以及N=100,000,000
#define LOOP 50

//分别定义MapKey=map<int,int>、hash_map<int,int>、unordered_map<int,int>
typedef map<int,int> MapKey;          //采用map
//typedef hash_map<int,int> MapKey;     //采用hash_map
typedef std::unordered_map<int,int> MapKey1;  //采用unordered_map
typedef tr1::unordered_map<int,int> MapKey2;  //采用unordered_map
typedef phmap::flat_hash_map<int,int> MapKey3;  //采用unordered_map





int GetPidMem(pid_t pid,string& memsize)
{
 char filename[1024];

 snprintf(filename,sizeof(filename),"/proc/%d/status",pid);

 ifstream fin;

 fin.open(filename,ios::in);
 if (! fin.is_open())
 {
  cout<<"open "<<filename<<" error!"<<endl;
  return (-1);
 }

 char buf[1024];
 char size[100];
 char unit[100];

 while(fin.getline(buf,sizeof(buf)-1))
 {
  if (0 != strncmp(buf,"VmRSS:",6))
   continue;

  sscanf(buf+6,"%s%s",size,unit);

  memsize = string(size)+string(unit);
 }

 fin.close();

 return 0;
}


template<typename T>
void testMap(T MyMap){
 struct timeval begin;

 struct timeval end;
 gettimeofday(&begin,NULL);

 for(int i=0;i<N;++i){
  MyMap.insert(make_pair(i,i));
 }

 gettimeofday(&end,NULL);

 cout<<"insert N="<<N<<",cost=\t\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 MyMap.clear();

 gettimeofday(&begin,NULL);

 for(int i=0;i<N;++i){
  MyMap[i]=i;
 }

 gettimeofday(&end,NULL);

 cout<<"[] N="<<N<<",cost=\t\t\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 MyMap.clear();

 gettimeofday(&begin,NULL);

 for(int i=0;i<N;++i){
  MyMap.insert(make_pair(i,i));
 }

 gettimeofday(&end,NULL);

 cout<<"insert N="<<N<<",cost=\t\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 gettimeofday(&begin,NULL);

 for(int t=0; t<LOOP; t++)
 for(int i=N;i<2*N;++i){
  MyMap.find(i);
 }

 gettimeofday(&end,NULL);

 cout<<"getall find not N="<<N<<",cost=\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;


 gettimeofday(&begin,NULL);

 for(int t=0; t<LOOP; t++)
 for(int i=0;i<N;++i){
  MyMap.find(i);
 }

 gettimeofday(&end,NULL);

 cout<<"getall find N="<<N<<",cost=\t\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 gettimeofday(&begin,NULL);

 for(int t=0; t<LOOP; t++)
 for(int i=N;i<2*N;++i){
  MyMap.find(i);
 }

 gettimeofday(&end,NULL);

 cout<<"getall find not N="<<N<<",cost=\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 gettimeofday(&begin,NULL);

 for(int t=0; t<LOOP; t++)
 for(int i=0;i<N;++i){
  MyMap.count(i);
 }

 gettimeofday(&end,NULL);

 cout<<"getall cout N="<<N<<",cost=\t\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 gettimeofday(&begin,NULL);

 for(int t=0; t<LOOP; t++)
 for(int i=N;i<2*N;++i){
  MyMap.count(i);
 }

 gettimeofday(&end,NULL);

 cout<<"getall cout not N="<<N<<",cost=\t"<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;

 cout<<endl;

}

int main(int argc, char *argv[])
{

 MapKey map;
 MapKey1 map1;
 MapKey2 map2;

 MapKey3 map3;

 testMap<MapKey>(map);
 testMap<MapKey1>(map1);
 testMap<MapKey2>(map2);
 testMap<MapKey3>(map3);


 string memsize;

 GetPidMem(getpid(),memsize);

 cout<<memsize<<endl;

 return 0;
}

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html

【C++容器】数组和vector、array三者区别和联系 https://blog.51cto.com/liangchaoxi/4056308

https://blog.csdn.net/y601500359/article/details/105297918

———————————————— 版权声明：本文为CSDN博主「stitching」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qq_40250056/article/details/114681940

———————————————— 版权声明：本文为CSDN博主「FishBear_move_on」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/haluoluo211/article/details/80877558

———————————————— 版权声明：本文为CSDN博主「SOC罗三炮」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/luolaihua2018/article/details/109406092

———————————————— 版权声明：本文为CSDN博主「鱼思故渊」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/yusiguyuan/article/details/40950735