八、C++STL 6大组件-你必知必会的编程利器

STL这部分推荐直接看《C++ primer》的9到11章内容，有非常详细的接口列表，还有很多例子。附录里还有常用的泛型算法，适合经常看一下

vector容器

底层数据结构：动态开辟的数组，每次以原来空间大小的2倍进行扩容的

vector<int> vec;

deque双端队列和list链表

初始的元素放在队列的中间，方便后续添加元素。外部有一个mapper保存队列，队满的时候会对mapper扩容，队列放在扩容后的mapper的sizeof（原来mapper）/2的位置。

deque容器：

list容器：

vector、deque、list对比

vecotr和deque之间的区别？

• deque底层内存是否是连续的？ 不是。deque是由一个二维数组构成的。每一个第二维是连续的，第一维数据不是连续的。
• 前中后插入删除的时间复杂度：中间和末尾是O(1），前面插入deque是O(1)，vector是O(n)
• 对于内存的使用效率： vector的低，需要的内存空间必须是连续的。deque可以分块进行存储，不需要内存空间必须是连续的。
• 由于deque的第二维内存空间不是连续的，所以在deuqe中间进行元素的insert或者erase，造成元素移动的时候臂vector要慢

vector和list之间的区别？

• list底层是双向循环链表
• list的增加删除是O(1),vector增加删除是O(n)

详解容器适配器

无序关联容器

unordered_set:

unordered_map:

map的operator[]重载有两个功能：一是查询，二如果key不存在，会插入一对数据

unordered_map<int,string> mp1;
mp1.insert(make_pair(12,"asf"));//生成pair类型
mp1.insert({123,"asfsaf"});

有序关联容器

底层是红黑树结构。

自定义类型如何在有序容器中排序：要在自定义类型中提供小于运算符的重载

容器的迭代器

函数对象

函数对象就是C语言里的函数指针

把有operator（）小括号运算符重载函数的对象，称作函数对象或者称作仿函数。

好处：

• 通过函数对象调用operator（），可以省略函数的调用开销，比通过函数指针调用函数（不能够inline内联调用）效率高。
• 因为函数对象使用类生成的，所以可以添加相关的成员变量，用来记录函数对象使用时的更多的信息。

template<typename T>
bool mygreater(T a, T b) {
    return a > b;
}

template<typename T>
bool myless(T a, T b) {
    return a < b;
}

template<typename T>
class Myless{//函数对象
public:
    bool operator()(T a,T b){
        return a<b;
    }
};

template<typename T, typename Compare>
bool compare(T a, T b, Compare comp) {//使用函数指针或者函数对象调用前面定义的两个函数
    return comp(a, b);//在使用函数指针的时候无法声明为inline函数，效率低
}

int main() {
    cout << compare(10, 30, mygreater<int>)<<endl;
    cout<<compare(20,10,Myless<int>())<<endl;
    return 0;
}

函数对象的一些其他用法：用于priority_queue和set：

priority_queue<int,vector<int>,Mygreater<int>> queue1;
priority_queue<int> queue2;

for(int i=0;i<20;i++){
    queue1.push(rand()%100);
    queue2.push(rand()%100);
}

for(int i=0;i<20;i++){
    cout<<queue1.top()<<" ";
    queue1.pop();
}
cout<<endl;

for(int i=0;i<20;i++){
    cout<<queue2.top()<<" ";
    queue2.pop();
}
cout<<endl;

/* 输出结果：
2 5 18 21 27 34 35 41 47 61 62 67 69 69 71 78 81 91 92 95
99 95 94 91 82 67 64 58 53 45 42 38 36 27 26 24 16 12 4 0*/

//set:
set<int> set1;
set<int,Mygreater<int>> set2;

for(int i=0;i<20;i++){
   set1.insert(rand()%100);
   set2.insert(rand()%100);
}

for(int a:set1){
    cout<<a<<" ";
}
cout<<endl;

for(int a:set2){
    cout<<a<<" ";
}
cout<<endl;

/* 输出结果
3 6 16 22 23 29 37 40 41 46 47 53 62 64 70 73 88 90 93
78 68 64 59 57 50 48 44 42 41 35 33 29 11 6 5 1*/

泛型算法和绑定器