C++面试STL--2

• 1 STL
• 1.1 STL 中常见的容器及其特性
• • • 1.1.1 顺序容器
    • 1.1.2 关联式容器--set、multiset、map、multimap
    • 1.1.3 容器适配器--stack,queue,priority_queue。
  • 1.2 空间配置器allocator
  • • 1.2.1 两种C++实例化方式
  • 1.3 STL中容器
  • 1.4 迭代器
  • 1.5 迭代器是怎么删除元素的
  • 1.6 STL 中 resize 和 reserve 的区别
  • 1.7 map和unoreder_map的区别
  • 1.8 vector和list的区别，各自适应场景
  • 1.8 简述vector的实现原理
  • 1.8 STL中map的实现
  • • 1.8.1 map和set的区别及实现
  • 1.9 push_back和emplace_back的区别

1 STL

什么是STL：
标准模板库（Standard Template Library,简称STL）简单说，就是一些常用数据结构和算法的模板的集合。

1. 广义上讲，STL分为3类：Algorithm（算法）、Container（容器）和Iterator（迭代器），容器和算法通过迭代器可以进行无缝地连接。
2. 详细的说，STL由6部分组成：容器(Container)、算法（Algorithm）、 迭代器（Iterator）、仿函数（Function object）、适配器（Adaptor）、空间配制器（Allocator）。
   STL的主要六大组成部分：

• 容器(Container)：
  是一种数据结构， 如list, vector, 和deques，以模板类的方法提供。为了访问容器中的数据，可以使用由容器类输出的迭代器。
• 算法（Algorithm）
  是用来操作容器中的数据的模板函数。例如，STL用sort()来对一 个vector中的数据进行排序，用find()来搜索一个list中的对象， 函数本身与他们操作的数据的结构和类型无关，因此他们可以用于从简单数组到高度复杂容器的任何数据结构上。
• 迭代器（Iterator）
  提供了访问容器中对象的方法。例如，可以使用一对迭代器指定list或vector中的一定范围的对象。 迭代器就如同一个指针。事实上，C++ 的指针也是一种迭代器。 但是，迭代器也可以是那些定义了operator*()以及其他类似于指针的操作符方法的类对象;
• 仿函数（Function object）
  仿函数又称之为函数对象， 其实就是重载了操作符的struct,没有什么特别的地方。
• 适配器（Adaptor）
  简单的说就是一种接口类，专门用来修改现有类的接口，提供一中新的接口；或调用现有的函数来实现所需要的功能。主要包括3中适配器Container Adaptor、Iterator Adaptor、Function Adaptor。
• 空间配制器（Allocator）
  ​ 为STL提供空间配置的系统。其中主要工作包括两部分：
  （1）对象的创建与销毁；
  （2）内存的获取与释放。

1.1 STL 中常见的容器及其特性

  容器可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构，都是模板类，分为顺序容器、关联式容器、容器适配器三种类型。

三种容器类型特性分别如下：

1.1.1 顺序容器

容器并非排序的，元素的插入位置同元素的值无关。包含vector、deque、list。
（1）vector 头文件
动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。
（2）deque 头文件
双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成（仅次于vector）。在两端增删元素具有较佳的性能（大部分情况下是常数时间）。
（3）list 头文件
双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。

1.1.2 关联式容器–set、multiset、map、multimap

元素是排序的；插入任何元素，都按相应的排序规则来确定其位置；在查找时具有非常好的性能；通常以平衡二叉树的方式实现。包含set、multiset、map、multimap。
（1）set/multiset 头文件
set 即集合。set中不允许相同元素，multiset中允许存在相同元素。
（2）map/multimap 头文件
map与set的不同在于map中存放的元素有且仅有两个成员变，一个名为first,另一个名为second, map根据first值对元素从小到大排序，并可快速地根据first来检索元素。 键–值。
​ 注意：map同multimap的不同在于是否允许相同first值的元素。

1.1.3 容器适配器–stack,queue,priority_queue。

封装了一些基本的容器，使之具备了新的函数功能，比如把deque封装一下变为一个具有stack功能的数据结构。这新得到的数据结构就叫适配器。包含stack,queue,priority_queue。
（1）stack 头文件
栈是项的有限序列，并满足序列中被删除、检索和修改的项只能是最进插入序列的项（栈顶的项）。后进先出。
（2）queue 头文件 队列。
插入只可以在尾部进行，删除、检索和修改只允许从头部进行。先进先出。
（3）priority_queue 头文件
优先级队列。内部维持某种有序，然后确保优先级最高的元素总是位于头部。最高优先级元素总是第一个出列。

1.2 空间配置器allocator

一般情况下,一个程序包括数据结构和相应的算法，而数据结构作为存储数据的组织形式，与内存空间有着密切的联系。在C++ STL中，空间配置器便是用来实现内存空间(一般是内存，也可以是硬盘等空间)分配的工具，与容器联系紧密，每一种容器的空间分配都是通过空间分配器alloctor实现的。

1.2.1 两种C++实例化方式

• 一种是直接利用构造函数,直接构造类对象，如 Test test()；
• 通过new来实例化一个类对象，如 Test *pTest = new Test；
  内存分配主要有三种方式：
  （1） 静态存储区分配：内存在程序编译的时候已经分配好，这块内存在程序的整个运行空间内都存在。如全局变量,静态变量等。
  （2） 栈空间分配：程序在运行期间，函数内的局部变量通过栈空间来分配存储（函数调用栈），当函数执行完毕返回时，相对应的栈空间被立即回收。主要是局部变量。
  （3）堆空间分配：程序在运行期间，通过在堆空间上为数据分配存储空间，通过malloc和new创建的对象都是从堆空间分配内存，这类空间需要程序员自己来管理，必须通过free()或者是delete()函数对堆空间进行释放，否则会造成内存溢出。

从内存空间分配的角度来对这两种方式的区别，就比较容易区分:
（1）对于第一种方式来说，是直接通过调用Test类的构造函数来实例化Test类对象的,如果该实例化对象是一个局部变量，则其是在栈空间分配相应的存储空间。
（2）对于第二种方式来说,就显得比较复杂。这里主要以new类对象来说明一下。new一个类对象,其实是执行了两步操作：首先,调用new在堆空间分配内存,然后调用类的构造函数构造对象的内容；同样，使用delete释放时，也是经历了两个步骤：首先调用类的析构函数释放类对象，然后调用delete释放堆空间。

1.3 STL中容器

STL中常用的容器有vector、deque、list、map、set、multimap、multiset、unordered_map、unordered_set、stack、queue和priority_queue。

1. map、set、multimap、multiset。四种容器采用红黑树实现，红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为:
   插入: O(logN)
   查看: O(logN)
   删除: O(logN)
2. unordered_map、unordered_set、unordered_multimap、 unordered_multiset 四种容器采用哈希表实现，不同操作的时间复杂度为：
   插入: O(1)，最坏情况O(N)
   查看: O(1)，最坏情况O(N)
   删除: O(1)，最坏情况O(N)

1.4 迭代器

STL中迭代器的作用，有指针为何还要迭代器？
Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。
迭代器的作用：
（1）用于指向顺序容器和关联容器中的元素
（2）通过迭代器可以读取它指向的元素
（3）通过非const迭代器还可以修改其指向的元素
迭代器用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v; //一个存放int元素的数组，一开始里面没有元素
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    vector<int>::const_iterator i; //常量迭代器
    for (i = v.begin(); i != v.end(); ++i) //v.begin()表示v第一个元素迭代器指针，++i指向下一个元素
        cout << *i << ","; //*i表示迭代器指向的元素
    cout << endl;

    vector<int>::reverse_iterator r; //反向迭代器
    for (r = v.rbegin(); r != v.rend(); r++)
        cout << *r << ",";
    cout << endl;

    vector<int>::iterator j; //非常量迭代器
    for (j = v.begin();j != v.end();j++)
        *j = 100;
    for (i = v.begin();i != v.end();i++)
        cout << *i << ",";
    return 0;
}

/*    运行结果：
          1,2,3,4,
          4,3,2,1,
          100,100,100,100,
*/                

1.5 迭代器是怎么删除元素的

1. 对于序列容器vector，deque来说，使用erase后，后边的每个元素的迭代器都会失效，后边每个元素都往前移动一位，erase返回下一个有效的迭代器；
2. 对于关联容器map，set来说，使用了erase后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素，不会影响下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可；
3. 对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的迭代器，因此上面两种方法都可以使用。
   容器上迭代器分类：

1.6 STL 中 resize 和 reserve 的区别

首先两个概念：
（1）capacity：该值在容器初始化时赋值，指的是容器能够容纳的最大的元素的个数。还不能通过下标等访问，因为此时容器中还没有创建任何对象。
（2）size：指的是此时容器中实际的元素个数。可以通过下标访问0-(size-1)范围内的对象。
resize和reserve区别主要有以下几点：
resize和reserve的区别：
（1）resize既分配了空间，也创建了对象；reserve表示容器预留空间，但并不是真正的创建对象，需要通过insert（）或push_back（）等创建对象。
（2）resize既修改capacity大小，也修改size大小；reserve只修改capacity大小，不修改size大小。
（3）两者的形参个数不一样。 resize带两个参数，一个表示容器大小，一个表示初始值（默认为0）；reserve只带一个参数，表示容器预留的大小。

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> a;
    cout<<"initial capacity:"<<a.capacity()<<endl;
    cout<<"initial size:"<<a.size()<<endl;

    /*resize改变capacity和size*/
    a.resize(20);
    cout<<"resize capacity:"<<a.capacity()<<endl;
    cout<<"resize size:"<<a.size()<<endl;


    vector<int> b;
     /*reserve改变capacity,不改变resize*/
    b.reserve(100);
    cout<<"reserve capacity:"<<b.capacity()<<endl;
    cout<<"reserve size:"<<b.size()<<endl;
return 0;
}

/*    运行结果：
          initial capacity:0
        initial size:0
        resize capacity:20
        resize size:20
        reserve capacity:100
        reserve size:0
*/    

1.7 map和unoreder_map的区别

map和unordered_map的区别在于他们的实现基理不同。

1. map实现机理
   ​ map内部实现了一个红黑树（红黑树是非严格平衡的二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树有自动排序的功能，因此map内部所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找、删除、添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉树（又名二叉查找树、二叉排序树）存储的，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值。使用中序遍历可将键值按照从小到大遍历出来。
2. unordered_map实现机理
   unordered_map内部实现了一个哈希表（也叫散列表），通过把关键码值映射到Hash表中一个位置来访问记录，查找时间复杂度可达O（1），其中在海量数据处理中有着广泛应用。因此，元素的排列顺序是无序的。

1.8 vector和list的区别，各自适应场景

vector和list区别在于底层实现机理不同，因而特性和适用场景也有所不同。

1. vector：一维数组
   ​ 特点：元素在内存连续存放，动态数组，在堆中分配内存，元素连续存放，有保留内存，如果减少大小后内存也不会释放。
   ​ 优点：和数组类似开辟一段连续的空间，并且支持随机访问，所以它的查找效率高其时间复杂度O(1)。
   ​ 缺点：由于开辟一段连续的空间，所以插入删除会需要对数据进行移动比较麻烦，时间复杂度O（n），另外当空间不足时还需要进行扩容。
2. list：双向链表
   ​ 特点：元素在堆中存放，每个元素都是存放在一块内存中，它的内存空间可以是不连续的，通过指针来进行数据的访问。
   ​ 优点：底层实现是循环双链表，当对大量数据进行插入删除时，其时间复杂度O(1)。
   ​ 缺点：底层没有连续的空间，只能通过指针来访问，所以查找数据需要遍历其时间复杂度O（n），没有提供[]操作符的重载。
3. 应用场景
   ​ vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随即访问，而不在乎插入和删除的效率，使用vector。
   ​ list拥有一段不连续的内存空间，如果需要高效的插入和删除，而不关心随机访问，则应使用list。

1.8 简述vector的实现原理

1. 新增元素
   Vector通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，在插入新增的元素。

//新增元素 
void insert(const_iterator iter,const T& t )
    {  
        int index=iter->begin();
        if (index<size_)
       {
           if (size_==capacity_)
           {
                int capa=calculateCapacity();
                newCapacity(capa);
           }
           memmove(buf+index+1,buf+index,(size_-index)*sizeof(T)); 
           buf[index]=t;
           size_++;
       } 
   }

2. 删除元素
   删除最后一个元素pop_back()和通过迭代器删除任意一个元素erase(iter)。

3. 迭代器iteraotr
   迭代器iteraotr是STL的一个重要组成部分,通过iterator可以很方便的存储集合中的元素.STL为每个集合都写了一个迭代器, 迭代器其实是对一个指针的包装,实现一些常用的方法,如++,–,!=,==,*,->等, 通过这些方法可以找到当前元素或是别的元素。

1.8 STL中map的实现

map是关联式容器，它们的底层容器都是红黑树。map 的所有元素都是 pair，同时拥有实值（value）和键值（key）。pair 的第一元素被视为键值，第二元素被视为实值。所有元素都会根据元素的键值自动被排序。不允许键值重复。

1. map的特性如下：
   （1）map以RBTree作为底层容器；
   （2）所有元素都是 键+值 存在；
   （3）不允许键重复；
   （4）所有元素是通过键进行自动排序的；
   （5）map的键是不能修改的，但是其键对应的值是可以修改的。

1.8.1 map和set的区别及实现

1. set是一种关联式容器，其特性如下：
   （1）set以RBTree作为底层容器
   （2）所得元素的只有key没有value，value就是key
   （3）不允许出现键值重复
   （4）所有的元素都会被自动排序
   （5）不能通过迭代器来改变set的值，因为set的值就是键，set的迭代器是const的
2. map和set一样是关联式容器，其特性如下：
   （1）map以RBTree作为底层容器
   （2）所有元素都是键+值存在
   （3）不允许键重复
   （4）所有元素是通过键进行自动排序的
   （5）map的键是不能修改的，但是其键对应的值是可以修改的
   综上所述，map和set底层实现都是红黑树；map和set的区别在于map的值不作为键，键和值是分开的。

1.9 push_back和emplace_back的区别

如果要将一个临时变量push到容器的末尾，push_back()需要先构造临时对象，再将这个对象拷贝到容器的末尾，而emplace_back()则直接在容器的末尾构造对象，这样就省去了拷贝的过程。

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

class A {
public:
    A(int i){
        str = to_string(i);
        cout << "构造函数" << endl; 
    }
    ~A(){}
    A(const A& other): str(other.str){
        cout << "拷贝构造" << endl;
    }

public:
    string str;
};

int main()
{
    vector<A> vec;
    vec.reserve(10);
    for(int i=0;i<10;i++){
        vec.push_back(A(i)); //调用了10次构造函数和10次拷贝构造函数,
//        vec.emplace_back(i);  //调用了10次构造函数,一次拷贝构造函数都没有调用过
    }