the principal behind cplusplus

一些C++背后的原理。

在刷题或者平时学习期间遇到的函数，看看它们的原理都是啥。

1. algorithms库里的reverse 在leetcode中遇到的reverse函数，比自己反转vector快太多了。

看了C++网站上的解释，他的原理其实就是swap，它调用的是iter_swap函数，将两个值的位置互换。因为只用了一半的值，所以效率比我之前自己反转的要高。

Complexity： Linear in half the distance between first and last: Swaps elements.

2. unordered_map和普通的map的区别。

先看下C++网站上的解释。

Map: Maps are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order.

Unordered maps are associative containers that store elements formed by the combination of a key value and a mapped value, and which allows for fast retrieval(检索) of individual elements based on their keys.

unordered_map 是哈希表（无序，散列式的存储方式），而map是红黑树（有序，一种二叉查找树）。unordered_map在查找时比map的效率快，但在迭代遍历中比map慢，而且遍历时候的顺序与创建时插入的顺序不一致。map的空间占用率高，因为相比于哈希表，红黑树每一个节点都需要保留红/黑性质，父节点，子节点。

3. 函数swap在c++11和c++98里有明显的不同。
   C++98
   

   so to exchange two vectors we essentially created three. There were three dynamic allocations and a lot of expensive objects copied, and any of those operations could throw, possibly leaving the arguments in an indeterminate state

1
2
3
4

template <class > void swap ( & a, & b )
{
  T c(a); a=b; b=c;
}

C++11

so to exchange two vectors we essentially created three. There were three dynamic allocations and a lot of expensive objects copied, and any of those operations could throw, possibly leaving the arguments in an indeterminate state

1
2
3
4
5
6
7
8

template <class > void swap (& a, T& b)
{
  T c(std::move(a)); a=std::move(b); b=std::move(c);
}
template <class T, size_t N> void swap (T (&a)[N], T (&b)[N])
{
  for (size_t i = 0; i<N; ++i) swap (a[i],b[i]);
}

can safely and efficiently move them around without copying.

4. 优先队列
5. map的iterator可以双向遍历