标准模板库

概述

容器：数据结构

​ 序列式容器 vector、list

​ 关联式容器 set ,map

​ 无序关联式容器 unordered_set , unordered_map

迭代器：理解为广义指针

算法：本质就是一个个函数，可以利用迭代器访问容器中的元素，堆容器中的元素做处理

适配器：起到适配的作用。（就是两个东西不适配，进行一种转换）

分为：容器的适配器： stack priority_queue

​ 迭代器的适配器

​ 函数适配器： bind、mem_fn

函数对象：起定制化操作的

空间配置器；管理空间的申请与释放

补充：按shift+%可以在匹配括号之间跳转

vector

容器的初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//vector 的各种构造方式
void test(){
    vector<int> vec;//无参构造函数
    //vector<int> vec();//error, 这变成声明了一个函数了 例如 int func(); 一摸一样
    
    
    vector<int> vec2(10，1);//第一个参数 count 第二个参数value ，构造结果 10个1，不写第二个参数，就是10个0，value的默认值是0
    
    int arr[10] = {1,2,3,4,5,6,7,8,9,10};
    //vector<int> vec3(arr,arr+9);//是左闭右开的区间，
    vector<int> vec3(arr,arr+10);//传递迭代器范围的元素
    
 
    
    //4.拷贝构造与移动构造
    
    
    //5.使用大括号的形式
    vector<int> vec5{1,2,3,4,5,6,7};
    // = 也可以加上
    vector<int> vec5 = {1,2,3,4,5,6,7};
    
}

容器的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
   for(int i = 0; i < vec.size(); ++i){
       cout << vecp[i] << " ";
   }

	//取vector类型的迭代器
    vector<int>::iterator it;
    for(it = vec3.begin();it !- vec3.end(); ++it){
        cout << *it << " ";
    }
    cout << endl;

	//增强for循环，底层是依靠迭代器实现的
    for(auto & elem : vec){
        cout << elem << " ";
    }


//将打印抽象出来处理为一个函数
template <class Container>
void display(const Container &con){
    for(auto &elem: con){
        cout << elem << " ";
    }
    cout << endl;
}

插入元素

1
2
3
4
5
6
vector<int> vec = {1,2,3,4,5};

vec.push_back(6);
display(vec);
vec.pop_back();
display(vec);

向任意位置插入元素

可能会崩溃

vector不支持头插，因为vector是一端开口的数据结构，所以vector的头部是固定的，不能进行插入与删除（具体是因为，在头部插入或者删除一个元素那么后面的元素都要进行移动）

取首元素的首地址

1
2
&*vec.begin();
int *pdata = number.data();

底层剖析

vector底层实现原理：

底层是由三个指针来实现的，分别是头指针，指向容器大小末尾的下一个位置的指针，以及指向存储存储的最后一个元素的后一个位置的指针

deque

初始化

同vector

遍历

同vector

插入元素

尾插同vector

头插

1
2
3
4
deque<int> deq = {1,2,3,4,5,6};

deq.push_front(7);
display(deq);

deque是双端开口的，所以可以头插，也可以尾插

在任意位置插入元素迭代器不会跟着第一次指向的元素跑，而是，如果迭代器一开始指向的元素位于deque的前半部分，插入元素迭代器所指元素不会变，如果指向的元素位于后半部分，那么元素都是向后移动的，而且insert是往迭代器所指元素的前一个位置插入元素的，所以指向后半部分的时候，这个元素也需要往后移，所以迭代器所指的元素是可能发生变化的。

deque的实现原理

deque中的迭代器不是一个简单的指针，而是一个类类型，该类类型重载指针所有的基本操作，包括：解引用，箭头，前置++和后置++等等

deque是由多个小片段组成的，片段与片段之间是不连续的，但是片段内部是连续的，这些小片段是由中控器进行控制的，所以对外deque是一个连续的，对内deque是不连续的

小片段申请下全是空的？ 会不会有别人的数据，头插怎么搞的

list

初始化

同vector

遍历

list没有提供下标访问运算符

1
2
3
for(size_t i = 0; i < list.size(); ++i){
    cout << list[i] << " ";//error 不支持下标访问运算符
}

插入元素

头插同deque

尾插同vecotr

在任意位置插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
auto it = li.begin();
it++;
li.insert(it,5);//在迭代器所指位置插入5


li.insert(it,4,22);//插入4个22

vector<int> vec = {12,34,56,78};
li.insert(it,vec.begin(),vec.end());


li.insert(it,{6,454,31});
//并且迭代器是跟着之前指着的元素一起走的

初始化总结：三种序列式容器vector deque,list都有五种初始化方式

遍历总结：对于vector和deque而言，遍历的方式是完全一样的，但是对于list，是不支持下标操作的。

插入总结：deque和list可以头插尾插，vector不可以头插可以尾插

晚上的练习

练习1：STL包括哪些组件？各自具有哪些特点？

A:STL包括六大组件：分别是

容器，迭代器，算法，适配器。函数对象，空间适配器

各自的特点：

容器：用于存储数据，提供不同的访问和操作方式，以满足不同的需求

算法：STL算法提供了大量的通用算法，用于对容器中的数据进行各种操作和处理，如排序搜索合并等

迭代器：迭代器用于遍历和访问容器中的元素，提供了一种统一的访问接口，使得算法能够与不同类型的容器无缝配合使用

函数对象：函数对象是可调用的对象，可以像函数一样使用，用于提供比一般函数更灵活的操作

空间适配器：空间适配器用于现有组件之间提供接口的转换，使得一些组件可以用于其他用途

迭代器：用来遍历和访问容器中元素和抽象概念

练习二Q:STL中的容器包括哪些？各自具有哪些特点？

A:STL中的容器包括：

序列式容器：

vector:动态数组，支持快速随机访问 动态增长和缩小，尾部插入和删除元素高效

deque:双端队列，支持快速在两端进行插入和删除操作 支持快速随机访问，但中间插入和删除的效率较低

list:双向链表，支持在任何位置进行高效插入和删除操作 不支持随机访问，访问和迭代效率受元素数量影响

关联式容器：

set:基于红黑树实现的集合，元素自动排序 不允许重复元素

map:键值对组成，基于红黑树实现的关联数组 键自动排序

无序容器：

unordered_set 基于哈希表实现的集合，元素无序存储 不允许有重复的元素

unordered_map 基于哈希表实现的关联数组，键值对无序存储 不允许重复键

练习三Q:序列式容器包括哪些？他们之间有哪些异同？

A:序列式容器包括：

vector，deque, list

三个容器的构造函数基本一致，

但是list不支持下标访问遍历数组，而vector 和 deque可以

插入元素，vector不支持push_front 而deque和list可以，

vector容器使用insert插入元素后，容器内的元素可能会变成随机值

deque容器使用vector插入元素后，如果迭代器所指的位置是容器元素的前半部分，那么迭代器在插入元素前后不会改变，而如果迭代器所指的位置是容器元素的后半部分，那么迭代器在插入元素之后就会发生改变

list容器插入元素后，迭代器所指的元素不会发生改变

练习四Q:

下面程序有什么错误？

1
2
3
4
5
6
list<int> lst; 
list<int>::iterator iter1 = lst.begin(), iter2 = lst.end(); 
while(iter1 < iter2)
{    
     //....
}

A:问题出在while(iter1 < iter2 )上，list容器不支持随机访问，因此迭代器不能进行< <= > >=这些操作，只能进行== ，!=这些操作

练习五Q:创建和初始化vector的方法，每种都给出一个实例？当然也可以把deque与list写出来

A:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>

using namespace std;

template <class T>
void print(const T &rhs){
    for(auto & elem:rhs){
        cout << elem << " ";
    }
    cout << endl;
}



void test(){
    vector<int> vec1;

    vector<int> vec2{1,2,3,4};
    vector<int> vec3 = {1,2,3,4};

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

    vector<int> vec5(vec4);
    vector<int> vec6(vector<int>{1,2,3});

    vector<int> vec7(10,1);

    print(vec1);
    print(vec2);
    print(vec3);
    print(vec4);
    print(vec5);
    print(vec6);
    print(vec7);
}


int main()
{
    test();
    return 0;
}

第六题Q:如果c1与c2是两个容器，下面的比较操作有什么限制？

if(c1 < c2)

A:如果要进行这样的操作，那么c1和c2不可是list容器，因为list容器不支持比较大小的操作

第七题Q:使用模板实现一个快速排序算法

1
2
3
4
5
6
7
8
9
10
11
12
template<typename T,typename Compare=std::less<T>> 
class MyQsort 
{ 
public:     
    MyQsort(T *arr, size_t size, Compare com);     
    void quick(int left, int right, Compare &com);     
    int partition(int left, int right, Compare &com);     
    void print(); 
private:    
    vector<T> _vec; 
};

A:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <vector>
using namespace std;

template <class T, class Compare=less<T>>
class MyQsort{
public:
    MyQsort(T *arr, size_t size, Compare com);
    void quick(int left, int right, Compare &com);
    int partition(int left, int right, Compare & com);
    void print();
private:
    vector<T> _vec;
};

template <class T,class Compare>
MyQsort<T,Compare>::MyQsort(T *arr, size_t size, Compare com)
{
    _vec.reserve(size);
    _vec(arr,arr+size);
}

template <class T,class Compare>
void MyQsort<T,Compare>::quick(int left, int right, Compare &com){
    if(left < right){
        int index = partition(left, right, com);
        partition(left, index - 1, com);
        partition(index + 1 , left, com);
    }
}

template <class T, class Compare>
int MyQsort<T, Compare>::partition(int left, int right, Compare &com){
    int val = _vec[left];
    while(left < right){
        while(left < right && _vec[right]>= val) --right;
        _vec[left] = _vec[right];
        while(left < right && _vec[left] <= val) ++left;
        _vec[right] = _vec[left];
    }
    _vec[left] = val;
    return left;
}

template <class T, class Compare>
void MyQsort<T,Compare>::print(){
    for(auto &e : _vec){
        cout << e << " ";
    }
    cout << endl;
}

void test(){
    int arr[5] = {5,4,3,2,1};
    MyQsort<int> mqs(arr,5);
    mqs.quick(0,5);
    mqs.print();
}


int main()
{
    test();
    return 0;
}