1.vector

vector是动态数组,是最常用的容器之一，其底层所采用的数据结构非常简单，就只是一段连续的线性内存空间。

vector扩大容量的本质

当 vector 的大小和容量相等（size==capacity）也就是满载时，如果再向其添加元素，那么 vector 就需要扩容。vector 容器扩容的过程需要经历以下 3 步：

• 完全弃用现有的内存空间，重新申请更大的内存空间；
• 将旧内存空间中的数据，按原有顺序移动到新的内存空间中；
• 最后将旧的内存空间释放。

这也就解释了，为什么 vector 容器在进行扩容后，与其相关的指针、引用以及迭代器可能会失效的原因。

由此可见，vector 扩容是非常耗时的。为了降低再次分配内存空间时的成本，每次扩容时 vector 都会申请比用户需求量更多的内存空间（这也就是vector容量的由来，即 capacity>=size），以便后期使用。vector 容器扩容时，不同的编译器申请更多内存空间的量是不同的。以 VS 为例，它会扩容现有容器容量的 50%。

1.1 vecor的构造函数

vector (opens new window)

C++11中六种构造方法

• 1. 构造一个空的vector

std::vector<int> first; // empty vector of ints

• 2. 指定元素个数并初始化

std::vector<int> second (4,100); // four ints with value 100

• 3）借助迭代器

std::vector<int> third (second.begin(),second.end());  // iterating through second

• 4)从一个数组中复制

std::vector<int> fourth (third);

• 5)从数组中构建

int a[5] = {1, 2, 3, 4, 5};
vector<int> res(a, a+5);

1.2 二维数组初始化

vector<vector<int> >num = 
        { {1,1,1,0,1,1},{1,0,1,1,1,1},{1,1,1,0,0,1},{1,0,1,0,0,1},{1,1,1,1,1,1} };

//二维数组初始化
//vector<vector<int>> vec(10, vector<int>(10));
vector<vector<int> >right(num.size(), vector<int>(num[0].size()));

1.3 erase删除数组

删除第几个，删除哪几个，不包括end

// erase the 6th element
myvector.erase (myvector.begin()+5);

// erase the first 3 elements:
myvector.erase (myvector.begin(),myvector.begin()+3);

1.4 pop_back

移除vector向量中最后一个元素

1.5 back

返回vector中最后一个元素的引用

1.6 resize

vector<int> s;
s.resize(3, 2);

将s的大小调整为3并用2填补。

1.7 当vector中的元素是pair时，遍历

unordered_map<char, vector<pair<string, int>>> m;
m['a'].emplace_back("b", 100);
m['a'].emplace_back("c", 200);
m['b'].emplace_back("a", 0.01);
m['c'].emplace_back("a", 0.005);
char key[] = {'a', 'b', 'c'};
for (size_t i = 0; i < 3; i++)
{
    cout << "key= " << key[i] << endl;
    for(auto [v1, v2] : m[key[i]]) {
        cout << v1 << " " << v2 << endl;
    }    
}

1.8 emplace_back

emplace_back() 和 push_back() 一样的是都是在容器末尾添加一个新的元素进去，不同的是 emplace_back() 在效率上相比较于 push_back() 有了一定的提升。

emplace_back() 函数在原理上比 push_back() 有了一定的改进，包括在内存优化方面和运行效率方面。内存优化主要体现在使用了就地构造（直接在容器内构造对象，不用拷贝一个复制品再使用）+强制类型转换的方法来实现，在运行效率方面，由于省去了拷贝构造过程，因此也有一定的提升。2 (opens new window)

• emplace_back在类提供移动构造函数的时候，会调用类的移动构造函数，没有移动复制构造函数调用复制构造函数

• push_back会调用类的复制构造函数

#include <iostream>
#include <vector>

class Example {
    public:
        Example() : b(0) {
            std::cout << "Constructor without Value.\n";
        };
        Example(int v) : b(v) {
            std::cout << "Constructor with Value.\n";
        };
        Example(const Example &e):b(e.b) {
            std::cout << "Copy Function Invoked.\n";
        };
        //noexcept关键字告诉编译器，函数中不会发生异常,这有利于编译器对程序做更多的优化。
        Example(Example &&e) noexcept : b(e.b) {
            std::cout << "Move Copy Function Invoked.\n";
        };
    public:
        static int a;
    private:
        int b;
};
int Example::a = 10;

int main(int argc, char **argv)
{
    vector<Example> evec;
    Example ele;
    evec.push_back(ele);
    /**带参数能直接push,不带参数直接调用.push_back会报错。
     * 移动复制构造构造函数被调用了3次
     **/
    evec.push_back(2);
    evec.emplace_back();
    // Constructor without Value.
    // Copy Function Invoked.
    // Constructor with Value.
    // Move Copy Function Invoked.
    // Move Copy Function Invoked.
    // Constructor without Value.
    // Move Copy Function Invoked.
    // Move Copy Function Invoked.  
    return 0;
}

之所以push_back(2)会调用3次移动构造函数和源码有关系：

// 如果 C++ 版本为 C++11 及以上（也就是从 C++11 开始新加了这个方法），使用 emplace_back() 代替
#if __cplusplus >= 201103L
void push_back(value_type &&__x) {
    emplace_back(std::move(__x));
}
#endif

左值转右值，对于右值引用使用std::move，对于万能引用使用std::forward。
std::move()与std::forward()都仅仅做了类型转换(可理解为static_cast转换)而已。真正的移动操作是在移动构造函数或者移动赋值操作符中发生的,关于移动构造函数和复制构造函数的介绍可以参考这里 (opens new window),引入了右值引用，提供了左值转右值的方法，避免了对象潜在的拷贝。而移动构造函数和移动赋值运算符也是通过右值的属性来实现的。直观的来讲，移动构造就是将对象的状态或者所有权从一个对象转移到另一个对象。只是转移，没有内存的搬迁或者内存拷贝所以可以提高利用效率，改善性能。

2.queue

C++ 标准库定义了三种类型的容器适配器： stack、 queue和 priority_queue
queue (opens new window)
queue所有元素的进出都必须符合先进先出的条件，只有queue的顶端元素，才有机会被外界取用，queue不提供遍历功能，也不提供迭代器。

2.1 构造

struct Point {
    int x;
    int y;
    Point(int x, int y):x(x), y(y) {}
};
queue<Point> points;
points.emplace(12, 10);

2.2 emplace

往队列的尾部添加元素，并可调用对象的构造函数初始化

points.emplace(12, 10);

2.3 front

从 queue中获取头部元素

Point p = points.front();

2.4 pop

移除队列中的最头部元素

points.pop();# remove value can be obtained by front;

2.5 push

往队列的末尾追加1个新元素,注意与emplace的区别

Point p = Point(2, 3);
que.push(p);

3.priority_queue

类 priority_queue (opens new window)对元素进行排序，以便最大元素或最小元素始终位于顶部位置。 它支持元素的插入以及顶部元素的检查和删除。 一个很好的类比是人们喜欢按年龄、身高或其他条件排列位置。可以按任意顺序插入元素，但只能从堆顶取元素。

priority_queue是C++标准定义的三个容器适配器之一，其基于堆实现，是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

抛开内部结构，priority_queue实现的功能是从一端插入元素，一端取元素，如同队列一般。而与队列不同的是，其会对插入的元素进行排序，因此从队列头取出的元素不是满足FIFO的原则，而是优先取出最大或最小的元素。
支持的方法有：

方法	功能
empty	是否为空
size	元素个数
top	获取队头元素
push	插入元素
emplace	构造并插入元素
pop	移除队首元素
swap	swap (priority_queue& x) 交换两个队列中的元素

3.1构造priority_queue

priority_queue<Type, Container, Functional>

Type为数据类型， Container为保存数据的容器，Functional为元素比较方式。

如果不写后两个参数，那么容器默认用的是vector，比较方式默认用operator<，也就是优先队列是大顶堆，队头元素最大。
例如

// https://www.cplusplus.com/reference/queue/priority_queue/priority_queue/
// constructing priority queues
#include <iostream>       // std::cout
#include <queue>          // std::priority_queue
#include <vector>         // std::vector
#include <functional>     // std::greater

class mycomparison
{
  bool reverse;
public:
  mycomparison(const bool& revparam=false)
    {reverse=revparam;}
  bool operator() (const int& lhs, const int&rhs) const
  {
    if (reverse) return (lhs>rhs);
    else return (lhs<rhs);
  }
};

int main ()
{
  int myints[]= {10,60,50,20};

  std::priority_queue<int> first;
  std::priority_queue<int> second (myints,myints+4);
  std::priority_queue<int, std::vector<int>, std::greater<int> >
                            third (myints,myints+4);
  // using mycomparison:
  typedef std::priority_queue<int,std::vector<int>,mycomparison> mypq_type;

  mypq_type fourth;                       // less-than comparison
  mypq_type fifth (mycomparison(true));   // greater-than comparison

  return 0;
}

4.Map

map (opens new window)

默认情况下，C++是根据map的key来排序的。

4.1构造

c++11中， map有5种构造函数

• （1)默认构造函数

map<char, int> dict;
dict['a'] = 95;
dict['c'] = 97;
dict['b'] = 96;

• (2)借助其他map构建，包括开始和结尾

map<char, int> dict1(dict.find('a'), dict.end())

4.2遍历map

// 1
for (std::map<char,int>::iterator it=mymap.begin(); it!=mymap.end(); ++it)
{
    std::cout << it->first << " => " << it->second << '\n';
}
// 2.
for(auto m : map)
{
    cout << m.first << ": " << m.second << endl;
}

4.3与unordered_map比较

• map：<br>
  优点：有序性，这是map结构最大的优点，**其元素是按照key的字典顺序排列的,而不是插入顺序.**的有序性在很多应用中都会简化很多的操作.红黑树，内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高
  缺点： 空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间
  适用处：对于那些有顺序要求的问题，用map会更高效一些
  特点：基于红黑树实现，查找效率时O(logN)
• unordered_map：<br/>
  优点： 因为内部实现了哈希表，因此其查找速度非常的快
  缺点： 哈希表的建立比较耗费时间
  适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map,基于哈希算法实现，由散列函数查找，查找的时间复杂度是常数级O(1)

4.4方法

• count:统计key出现的此数,不存在返回0

5.set

set (opens new window)

首先set，不像map那样是key-value对，它的key与value是相同的。关于set有两种说法，第一个是STL中的set，用的是红黑树；第二个是hash_set，底层用得是hash table。红黑树与hash table最大的不同是，红黑树是有序结构，而hash table不是。但不是说set就不能用hash，如果只是判断set中的元素是否存在，那么hash显然更合适，因为set 的访问操作时间复杂度是log(N)的，而使用hash底层实现的hash_set是近似O(1)的。然而，set应该更加被强调理解为“集合”，而集合所涉及的操作并、交、差等，即STL提供的如交集set_intersection()、并集set_union()、差集set_difference()和对称差集set_symmetric_difference()，都需要进行大量的比较工作，那么使用底层是有序结构的红黑树就十分恰当了，这也是其相对hash结构的优势所在。

5.1构造

5种构造函数

• (1)默认

std::set<int> first;                           // empty set of ints

• (2)从数组构建

int myints[]= {10,20,30,40,50};
std::set<int> second (myints,myints+5);        // range

• (3)从其他set构建

std::set<int> third (second);                  // a copy of second

• (4)取其他set/vector的一部分

std::set<int> fourth (second.begin(), second.end());  // iterator ctor.

vector<int> vec = {1, 2, 3, 4};
set<int> ns(vec.begin(), vec.end());

6 unordered_set

基于hash算法实现，元素无序，查找更快O(1)。

6.1构造方法

 std::unordered_set<std::string> first;                                // empty
  std::unordered_set<std::string> second ( {"red","green","blue"} );    // init list
  std::unordered_set<std::string> third ( {"orange","pink","yellow"} ); // init list
  std::unordered_set<std::string> fourth ( second );                    // copy
  std::unordered_set<std::string> fifth ( cmerge(third,fourth) );       // move
  std::unordered_set<std::string> sixth ( fifth.begin(), fifth.end() ); // range

6.2 find

const_iterator find ( const key_type& k ) const;

7.stack

stack 栈是一种LIFO(后进先出last in first out)的数据结构, 它在stl 函数中是通过其它容器，如队列实现的，stack不能使用iterator迭代器。

7.1构造函数

7种构造函数

• 1.基于vector构建

vector<int>tmp(2, 100);
tmp[1] = 200;
stack<int, vector`<int>`> st(tmp);

7.2 top

获取栈顶元素的引用

7.3 pop

移除栈顶元素

7.4 push\emplace

• push往栈顶追加元素
• emplace构造并往栈顶追加元素

7.5 size

栈中元素的个数

7.6 empty

栈是否为空

7.7 swap

交换两个栈中元素

  std::stack<int> foo,bar;
  foo.push (10); foo.push(20); foo.push(30);
  bar.push (111); bar.push(222);

  foo.swap(bar);

8.list

基于双向链表实现，能够实现线性O(1)时间的插入和删除，与 forward_list很像，forward_list是基于单向链表实现的。list根据迭代器来插入，提取，移动元素的效率比 array\vector\deque效率要高，在元素需要频繁移动时如排序性能表现比较好。

缺点：

• 1.因其内存是不连续的，所以不能通过下标获取元素，如取第2个元素等，必须使用迭代器从begin()开始访问
• 2.因链表需要存储链接信息，故需额外的空间，list元素个数较大时影响无法忽略

8.1splice

void splice (const_iterator position, list& x, const_iterator i);

将元素从一个list移动到另一个list, list::splice() 是一个很强大的功能，它可在任意位置在O（1）时间复杂度拼接两个 list，这正是 list 的优势。

8.2emplace

template <class... Args>
  iterator emplace (const_iterator position, Args&&... args);

std::list< std::pair<int,char> > mylist;

mylist.emplace ( mylist.begin(), 100, 'x' );
mylist.emplace ( mylist.begin(), 200, 'y' );

在position处插入新构造的元素，还有emplace_front,emplace_back方法

8.3.size()

list的size函数调用了stl algorithm中的distance函数，故时间复杂度是O(N)

9.pair

pair (opens new window)

9.1构造函数

std::pair <std::string,double> product1;
product1 = std::make_pair(std::string("lightbulbs"),0.99);   // using make_pair (move)
std::pair <std::string,double> product2 ("tomatoes",2.30);   // value init
std::pair <std::string,double> product3 (product2);          // copy constructor
std::pair <std::string,double> pair4 = make_pair(10, "this"); // make_pair

10.总结

• 内存连续存放的 插入: O(N) 查看: O(1) 删除: O(N) 比如：vector、deque
• 内存链表存放的 插入: O(1) 查看: O(N) 删除: O(1) 比如：list
• 内存红黑树存放的 插入: O(logN) 查看: O(logN) 删除: O(logN) 比如：map、set、multimap、multiset
• 内存哈希表存放的 插入: O(1)，最坏情况O(N) 查看: O(1)，最坏情况O(N) 删除: O(1)，最坏情况O(N) unordered_map、unordered_set、unordered_multimap、 unordered_multiset

(adsbygoogle = window.adsbygoogle || []).push({});

参考资料

• cplusplus (opens new window)