STL 泛型编程学习

STL 泛型编程学习

STL标准库六大部件

面向对象编程，将数据和函数放在一个类里面，但是STL将数据（容器）和函数（算法）进行了分离，所以两者在基础观念上就不一样。

  1. 容器：各种数据结构。
  2. 分配器：进行空间配置与管理。
  3. 算法：数据处理方法，如sort，search等。
  4. 迭代器：好比一种泛化的指针，作为数据和函数之间的桥梁。stl容器都有自己的专属迭代器。
  5. 适配器：三种。
  6. 仿函数：类似函数。
    在这里插入图片描述

序列容器：

  • Array ：固定大小数组
  • Vector：可扩容数组
  • Deque：双端数组
  • List：双链表，环状
  • Forward-List：单链表

关联容器：

  • set/multiset：红黑树：高度平衡二叉树
  • map/multimap：红黑树
  • unorderedset/unorderedmultiset：hash表，开链式方法解决冲突
  • unorderedmap/unorderedmultimap：hash表

C++ STL标准库使用模板编程完成的

  1. 面向对象编程：数据和函数操作放在一个类里面。
  2. 模板编程：将数据和函数分开。为了适配各种数据类型，操作符重载，函数模板，占据非常重要性。

模板

函数模板：一个通用函数，其函数类型和形参类型不具体指定，用一个虚拟的类型来代表，此通用函数即为函数模板
模板函数：为函数模板传参，根据实际传入的参数类型生成的一个重载函数即为模板函数，它是函数模板的一次实例化。
当函数重载与模板函数冲突的时候，优先调用普通函数，因为普通函数在编译期间就生成了，模板函数是运行时生成的，先到先得。

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
#include <iostream>

using std::cout;
using std::endl;


// 函数模板：交换两个变量
template<typename T>
void MySwap(T &a,T &b){
    T temp = a;
    a=b;
    b= temp;
}

template<typename T>
void MyPrint(T &a,T &b){
    cout<<"a = "<<a << "b = "<< b<<endl;
} 

int main(){
    int a = 10;
    int b = 20;
    double aa = 10.2;
    double bb = 20.1;
    MyPrint(a,b);
    MyPrint(aa,bb);
    MySwap(a,b);
    MySwap(aa,bb);
    cout<<"======已经完成交换======"<<endl;
    MyPrint(a,b);
    MyPrint(aa,bb);
    return 0;
}

操作符重载

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
#include <iostream>
#include <fstream>

using std::cout;
using std::endl;
using std::ostream;


class Complex{
    double real;
    double image;
public:
    Complex(double real,double image):real(real),image(image){}
    Complex operator+(const Complex& other){
        return Complex(this->real+other.real, this->image+other.image);
    }
    friend ostream& operator<<(ostream& os, const Complex& p);  //声明operator<<为友元函数，可以访问私有成员
};

ostream& operator<<(ostream &cout,const Complex& other){
    cout<<other.real << "," <<other.image<<"i";
    return cout;
}

int main(){
    Complex c1(1.0f,2.2f);
    Complex c2(2.0f,3.2f);
    Complex c3=c1+c2;
    cout<<c3<<endl;
    return 0;
}

右值引用与移动构造

移动语义能提高复制对象性能：移动构造在进行复制构造的时候，只需要把指针指向原数据，然后把原数据的指针置空，再设置数据大小。相比复制构造要去动态分配内存、再递归调用每个元素的复制构造函数的速度快得多。
右值引用是C++语法层面表示移动语义的机制：std::move()可以把任意类型转为右值引用，右值引用不过是另一个类型，没有那么神秘，当参数类型为右值引用时，函数移动它的资源，即为“移动语义”。在汇编代码的层面来看，左值或右值引用的representation都是一个内存地址，如同指针一般；而在C++语法层面，通过区分两种引用类型，程序员能更好地利用右值。

1
2
std::vector<int> vec_orange = { 1, 42, 23, 7, 13 };
std::vector<int> vec_red = std::move(vec_orange); //移动

移动语义意味着把对象持有的资源或内容转移给另一个对象。

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
class my_vector
{
    int* data_;
    size_t size_;
    size_t capacity_;

public:
    // 复制构造函数
    my_vector(const my_vector& oth) :
        size_(oth.size_), 
        capacity_(oth.capacity_)
    {
        data_ = static_cast<int*>(malloc(sizeof(int) * size_));
        for (size_t i = 0; i < size_; ++i) {
            data_[i] = oth.data_[i];
        }
    }

    // 移动构造函数
    // std::exchange(obj, new_val)的作用是返回obj的旧值，并把new_val赋值给obj
    // 在移动oth的内容后，要把它置于一个有效状态。
    my_vector(my_vector&& oth) :
        data_(std::exchange(oth.data_, nullptr)),
        size_(std::exchange(oth.size_, 0)), 
        capacity_(std::exchange(oth.capacity_, 0))
    {}    
};

C++智能指针std::unique_ptr，不可复制，只能移动。

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
template <typename T>
class my_unique_ptr
{
    T* ptr_;
public:
    // 移动构造函数
    my_unique_ptr(my_unique_ptr&& oth) :
        ptr_(std::exchange(oth.ptr_, nullptr)) {}

    // 移动赋值函数
    my_unique_ptr& operator=(my_unique_ptr&& rhs)
    {
        if (this != &rhs) {
            if (ptr_) { // 释放当前拥有的指针
                delete ptr_;
            }
            ptr_ = std::exchange(rhs.ptr_, nullptr); // 夺取rhs的指针
        }
        return *this;
    }

    // 禁用复制构造函数、复制赋值函数
    my_unique_ptr(const my_unique_ptr&) = delete;
    my_unique_ptr& operator=(const my_unique_ptr&) = delete;
};

空间配置器allocator

  1. SGI STL 的每一个容器都已经指定缺省的空间配置器是 alloc，标准的allocator只是在做简单的封装，效率不高，在插入比较小的元素类型的时候，实际上会浪费很多的空间。
  2. 为了提高效率，SGI STL在对象的生成和释放过程中，对象构造和析构由std负责，但是内存的申请与释放，由SGI STL负责。（GNU 2.9版本）
  3. SGI的设计原则：
    a. 向 system heap 要求空间，也就是堆空间。
    b. 考虑多线程 (multi-threads) 状态。
    c. 考虑内存不足时的应变措施。
    d. 考虑过多“小型区块”可能造成的内存碎片 (fragment) 问题。使用两级空间配置器。
  4. 两级空间配置器：
    a. 当配置区空间大小超过 128bytes 时，称为足够大，使用第一级配置器，直接使用 malloc() 和 free()。处理内存不足的情况。
    b. 当配置区块不大于 128bytes 时，为了降低额外负担，直接使用第二级配置器，采用复杂的 memory pool 处理方式。维护16个链表，内存池以malloc配置而得。
  5. 二级配置器的内存池：每次配置一块内存，并维护对应的自由链表，负责空间配置和回收，内存链表上内存大小是8的倍数，共16个。
  6. GNU4.9版本以后的allocator，反而用成了普通的new和delete。

迭代器Iterator

  1. 为什么需要Iterator？ 因为算法和容器之间的处理过程需要迭代器起到一个润滑的作用。
  2. 例如，vector的print和list的print算法，中间需要执行的步骤就是往后走，如果不用迭代器，print算法需要针对vector进行不同的设计，因为vector可以随机访存，可以直接读取内存的下一块地址，但是list不可以，需要用指针进行操作，为了使list也可以用++这个符号，就要使用迭代器完成这个功能。
  3. 当算法变的复杂的时候，需要迭代器完成更多的数据格式，移动方式等等问题的时候，迭代器就需要具备五个必须得条件，完成特性萃取，告诉算法当前数据的迭代器特性是怎么样的，算法从而得出一个最优化的方案。

下面的代码可以单独打印数组和链表

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// 实现一个简单的双向循环List
template<typename T>
struct List_Node{
    List_Node<T>* prev;
    List_Node<T>* next;
    T val;
};
template <typename T>
struct MyList{
    typedef List_Node<T>* pointer;
    MyList(){
        node = new List_Node<T>;
        node->next = node;
        node->prev = node;
    }

    pointer begin(){
        return node->next;
    }

    pointer end(){
        return node;
    }

    void insert(pointer position, T val){
        pointer tmp = new List_Node<T>;
        tmp->val = val;
        tmp->next = position->next;
        tmp->prev = position;
        position->next->prev = tmp;
        position->next = tmp;
    }

    void erase(pointer position){
        position->next->prev = position->prev;
        position->prev->next = position->next;
        delete position;
    }

    void push_back(T val){
        insert(node->prev, val);
    }

    void pop_back(){
        erase(node->prev);
    }

private:
    pointer node; //双向循环链表，代表链表尾节点
};



template <typename T>
void printVec(T begin, T end){
    while(begin!=end){
        cout<<*begin<<endl;
        begin++;
    }
}

template <typename T>
void printList(T begin, T end){
    while(begin!=end){
        cout<<begin->val<<endl;
        begin=begin->next;
    }
}

int main(){
    int v[5] = {1,2,3,4,5};
    printVec(v,v+5);

    MyList<int> list;
    list.push_back(10);
    list.push_back(10);
    list.push_back(20);
    list.pop_back();
    printList(list.begin(),list.end());
    list.push_back(20);
    printList(list.begin(),list.end());
    return 0;
}

想要一个函数既能打印数组，又能打印链表，这个时候就要用到迭代器
迭代器就是连接容器和算法的桥梁: 1.链表和数组就是容器 2.打印函数就可以理解为算法。他们的连接方式是不同的。迭代器就在它们中间加了一个中间层。

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
template<typename T>
struct List_Node{
    List_Node<T>* prev;
    List_Node<T>* next;
    T val;
};

template <typename T>
struct List_iterator{
    typedef List_iterator<T> iterator;
    typedef T value;
    typedef T& reference;
    List_Node<T>* node;

    List_iterator():node(nullptr){}
    List_iterator(List_Node<T>* node):node(node){}

    // 前缀++ ++i
    iterator& operator++() {
        node = node->next;
        return *this;
    }
    
    // 后缀++ i++ 不能加引用
    iterator operator++(int) {
        iterator tmp=*this;
        node = node->next;
        return tmp;
    }

    iterator& operator--() {
        node = node->prev;
        return *this;
    }

    iterator& operator--(int) {
        iterator tmp=*this;
        node = node->prev;
        return tmp;
    }

    bool operator== (iterator& other){
        return this->node == other->node;
    }

    bool operator!= (iterator& other){
        return this->node != other->node;
    }

    iterator* operator-> (){
        return this;
    }

    reference operator*(){
        return node->val;
    }
};



// 实现一个简单的双向循环List
template <typename T>
struct MyList{
    typedef List_Node<T>* pointer;
    typedef List_iterator<T> iterator;
    MyList(){
        node = new List_Node<T>;
        node->next = node;
        node->prev = node;
    }

    iterator begin(){
        return node->next;
    }

    iterator end(){
        return node;
    }

    void insert(iterator position, T val){
        pointer tmp = new List_Node<T>;
        tmp->val = val;
        tmp->next = position.node->next;
        tmp->prev = position.node;
        position.node->next->prev = tmp;
        position.node->next = tmp;
    }

    void erase(iterator position){
        position.node->next->prev = position.node->prev;
        position.node->prev->next = position.node->next;
        delete position.node;
    }

    void push_back(T val){
        insert(--end(), val);
    }

    void pop_back(){
        erase(--end());
    }

private:
    pointer node; //双向循环链表，代表链表尾节点
};



template <typename T>
void printContainer(T begin, T end){
    while(begin!=end){
        cout<<*begin<<endl;
        ++begin;
    }
}

int main(){
    int v[5] = {1,2,3,4,5};
    printContainer(v,v+5);

    MyList<int> list;
    list.push_back(10);
    list.push_back(10);
    list.push_back(20);
    list.pop_back();
    printContainer(list.begin(),list.end());
    list.push_back(20);
    printContainer(list.begin(),list.end());
    return 0;
}

type traits 类型萃取

  1. 迭代器是算法与容器之间的桥梁，如果算法需要知道操作的容器里面的数据类型？
1
2
vector<int>:: iterator
sort(vec.begin(), vec.end()); // 怎么判断数据类型？
  1. 算法需要迭代器提供的东西，由萃取器负责获取，还是一种中间层思想：萃取需要的5种数据类型：
1
2
3
4
5
typedef ptrdiff_t				   difference_type;
   typedef std::bidirectional_iterator_tag	 iterator_category;
   typedef _Tp				value_type;
   typedef _Tp*				pointer;
   typedef _Tp&				reference;

iterator_category：迭代器的分类，指它的移动性质，表示迭代器的类型（如输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器等）。这个信息可以方便算法采用最佳的移动方式。
value_type：迭代器指向的值类型。告诉算法是int 还是 string？
difference_type：迭代器之间的距离类型，通常使用ptrdiff_t。是inter？还是
pointer：指向value_type的指针类型。
reference：value_type的引用类型。

  1. 萃取机：中间层：统一指针和Iterator class的特性问题。

可以扩容的动态数组vector

vector插入的方法：C++11之后，会直接调用emplace_back();

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
	vector<int> vec;
    vec.push_back(1); // 运行到下面


void
      push_back(const value_type& __x) //添加左值时，这个函数会被调用，
      {
	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
	  {
	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
				     __x); //_Alloc_traits::construct完成的，它通常会调用元素类型的复制构造函数。
	    ++this->_M_impl._M_finish;
	  }
	else
	  _M_realloc_insert(end(), __x);
      }

#if __cplusplus >= 201103L //C++11及以后的版本，push_back提供了一个接受右值引用参数的重载版本。
      void
      push_back(value_type&& __x)
      { emplace_back(std::move(__x)); }
      //push_back会调用emplace_back，并将右值引用传递给它。在emplace_back内部，元素会被直接在vector的内存中构造，使用的是元素类型的移动构造函数。
      //对于可移动的对象，可以避免复制构造函数的调用，而是利用移动构造函数来构造新元素，通常这会更高效，因为它可以转移资源而不是复制资源。
}


emplace_back代码：

vector<_Tp, _Alloc>::
      emplace_back(_Args&&... __args)
      {
	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
	  {
	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
				     std::forward<_Args>(__args)...);
	    ++this->_M_impl._M_finish;
	  }
	else
	  _M_realloc_insert(end(), std::forward<_Args>(__args)...);

可以看到这里在元素个数小于vector容量的时候，直接在尾部进行插入，否则就会调用realloc进行扩容。
而 _M_realloc_insert中会调用_M_check_len函数进行容量计算：
const size_type __len =_M_check_len(size_type(1), "vector::_M_realloc_insert");

size_type
      _M_check_len(size_type __n, const char* __s) const
      {
	if (max_size() - size() < __n)
	  __throw_length_error(__N(__s));

	const size_type __len = size() + std::max(size(), __n); // 这里就是若扩容两倍还不够，就把插入的内容大小加上原来大小。
	return (__len < size() || __len > max_size()) ? max_size() : __len;
      }
 
扩容之后进行拷贝

vector的扩容机制：

  • 有的是1.5倍扩容
  • 有的是2倍扩容，但是它这个扩容的过程并不是绝对的，如果原本是五个，但是后面要插入20个，扩容到10个也不够，就扩容到25个，刚好满足这次添加20个的需要。

vector的迭代器就是一个指针。

双端开口的容器deque

  1. stack和queue基于deque进行实现的。
  2. deque两端开口，可以push_front push_back()；连续容器，支持随机访问内存。
  3. deque由一段一段定量的连续空间构成，串接在deque控制中心上，维护其整体连续的假象，控制中心是一个vector，增长按照普通的vector增长方式进行。
  4. deuque本身就有40个字节。
  5. deque做了大量的运算符重载去完成，模拟一种连续的假象。要特别注意边界区的考虑。
    在这里插入图片描述
  6. stack 堆，queue 队列：底层都是deque。都不提供遍历，因为没有迭代器。
  7. 优先队列： 默认采用大根堆排列，可以按照优先级进行输出。

Set/Map

  1. 二叉搜索树：节点值大于左子树每个节点的值，小于右子树每个节点的值。
  2. 平衡二叉搜索树：保证树的深度为O(logN)。任何节点的左右子树高度相差最多为1.
  3. 红黑树是一种广泛使用的平衡二叉搜索树：

    每个节点都有颜色，非黑即红。
    根节点为黑。
    父子两节点不能同时为红。
    任意节点到NULL的任何路径，所含黑节点数必须相同。

  4. set和map底层用的红黑树，插入的时间复杂度是logN。
  5. set的key必须独一无二，multiset的key可以重复。set的迭代器是const类型，不允许改变内容。
1
2
3
typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
		       key_compare, _Key_alloc_type> _Rep_type;
      _Rep_type _M_t;  // Red-black tree representing set.

unordered_set/unordered_map

  1. 底层采用hash表，采用开链式方法解决冲突。

参考列表
https://www.bilibili.com/video/BV1Ga41177x8
https://zhuanlan.zhihu.com/p/347977300
https://www.bilibili.com/video/BV1pG4y197GW

语言基础
#C++ #读书笔记
STL 泛型编程学习
https://cauccliu.github.io/2024/03/26/STL泛型编程学习/
Author
Liuchang
Posted on
March 26, 2024
Licensed under