# c++ stl learn

**Repository Path**: zoulizhi/c--stl-learn

## Basic Information

- **Project Name**: c++ stl learn
- **Description**: stl源码学习。。。。。。。。。。。。。。。。。
- **Primary Language**: C++
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2023-03-30
- **Last Updated**: 2023-04-14

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# c++ stl learn

ps:该分析基于minw64 6.4.0  c++

# 1、容器分类

常用容器包括:array,vector,deque,list,set类型,map类型,queue,stack。每种容器所具有的算法如下所示：

<img src="README.assets/20210418214654935.png" alt="img" style="zoom:200%;" /> 

## 1.1顺序容器

顺序容器支持下标寻址访问元素。

### 1.1.1 std::array

​     std::array除了有传统数组支持随机访问、效率高、存储大小固定等特点外，还支持迭代器访问、获取容量、获得原始指针等高级功能。

### 1.1.2 std::vector

​        是封装动态大小数组的序列容器。支持自动增长，而且，它的增长是一次增长一定的大小，而不是每次都增长1 相对效率较高。支持随机访问，可以像数组一样寻址。

### 1.1.3 std::queue

​      （双端队列）是一个索引序列容器，允许在其开始和结束时快速插入和删除。此外，deque两端的插入和删除不会使指向其余元素的指针或引用失效。

### 1.1.4 std::list

​        list是一个容器，它支持从容器中的任意位置对元素进行固定时间的插入和移除。不支持快速随机访问。它通常实现为双链表

## 1.2 有序关联容器

### 1.2.1 std::set

set是一个关联容器，它包含一组Key类型的唯一对象。使用键比较函数Compare进行排序。搜索、删除和插入操作具有对数复杂性。 不支持随机寻址。

### 1.2.2 std::multiset

std：：multiset是一个关联容器，其中包含一组Key类型的已排序对象。与set不同，允许多个具有等效值的键。使用键比较函数Compare进行排序。搜索、插入和删除操作具有对数复杂性。

### 1.2.3 std::map

map是一个排序的关联容器，它包含具有唯一键的键值对。使用比较函数Compare对键进行排序。搜索、删除和插入操作具有对数复杂性。实现为红黑树。

### 1.2.4 std::multimap

Multimap是一个关联容器，它包含一个键值对的排序列表，同时允许使用同一个键的多个条目。排序是根据应用于键的比较函数Compare来完成的。搜索、插入和删除操作具有对数复杂性。
不支持随机寻址。

## 1.3无序关联容器

### 1.3.1 unordered_map

是一个关联容器，其中包含具有唯一键的键值对。元素的搜索、插入和删除具有平均不变的时间复杂度。在内部，元素不是按任何特定顺序排序的，而是按bucket组织的。元素放入哪个bucket完全取决于其密钥的散列。这允许对单个元素进行快速访问，因为一旦计算了哈希，它就引用了元素放入的确切bucket。

### 1.3.2 unordered_multimap

### 1.3.3 unordered_set

是一个关联容器，其中包含一组Key类型的唯一对象。搜索、插入和删除具有平均不变的时间复杂度。
在内部，元素不是按任何特定顺序排序的，而是bucket桶组织的。元素放入哪个bucket完全取决于其值的哈希。这允许对单个元素进行快速访问，因为一旦计算了哈希，它就引用了元素放入的确切bucket。
不能修改容器元素（即使是通过非常量迭代器），因为修改可能会更改元素的哈希并损坏容器。

# 2、stl 组成

  stl组成包括算法，容器，迭代器， 仿函数，适配器，空间配置器 。



# 3、容器源码分析

## 3.1 list

​      分析以\# include <profile/list>中的list进行分析，该list调用的是#include<bits/stl_list.h>中的list

### 3.1.1 构造方法

```c++
 list<int> mlist(4,12);
  __gnu_cxx::malloc_allocator<int> all;
  list<int, __gnu_cxx::malloc_allocator<int>> mlist2(8,12,all);
 list<int, __gnu_cxx::malloc_allocator<int>> mlist3(mlist2);
```

​    list的构造方法有12个，默认为list().比较常用的构造方法有：

```c++
list()
list(const allocator_type& __a)
list(size_type __n, const allocator_type& __a = allocator_type())
list(size_type __n, const value_type& __value,const allocator_type& __a = allocator_type())
list(const list& __x)
list(const list& __x, const allocator_type& __a)

-a 指定的是分配器的种类
-n 指定的是容器初始化的大小
-value 指定的是默认的值
-x 复制已有的list

```

### 3.1.2 赋值运算

代码

 **普通函数 > 特化的模板函数 > 模板函数** 

```c++
#include<iostream>
#include<unordered_map>
# include <list>
#include<iterator>
using namespace std;

template<typename T> void fuzhi(T &t1,T&&  t2){
     cout << "模板优先"<<endl;
    t1 = t2;
};
void fuzhi(list<int> &t1,list<int> &&  t2){
    cout << "函数优先"<<endl;
    t1 = t2;
};

int main(){
    cout<<"hello"<<endl;
    list<int> mlist(4,12);
    list<int> mlist2;
    fuzhi(mlist2,move(mlist));
    list<int>::iterator it = mlist.begin();
    *it = 14;
    for(list<int>::iterator it = mlist2.begin();it!=mlist2.end();it++){
       cout<<*it<<endl;
    }
    cout<<"hello"<<endl;

     for(list<int>::iterator it = mlist.begin();it!=mlist.end();it++){
       cout<<*it<<endl;
    }
    return 0;
}
```

```c++
  list.tcc
  /**经过调试发现，赋值运算调用的是list.tcc中的“=”，调用的是_M_assign_dispatch，实现浅拷贝**/
  template<typename _Tp, typename _Alloc> list<_Tp, _Alloc>& list<_Tp, _Alloc>::
  operator=(const list& __x)
    {
      if (this != std::__addressof(__x))
	{
#if __cplusplus >= 201103L
	  if (_Node_alloc_traits::_S_propagate_on_copy_assign())
	    {
              auto& __this_alloc = this->_M_get_Node_allocator();
              auto& __that_alloc = __x._M_get_Node_allocator();
              if (!_Node_alloc_traits::_S_always_equal()
	          && __this_alloc != __that_alloc)
	        {
		  // replacement allocator cannot free existing storage
		  clear();
		}
	      std::__alloc_on_copy(__this_alloc, __that_alloc);
            }
#endif
	  _M_assign_dispatch(__x.begin(), __x.end(), __false_type());
	}
      return *this;
    }
```

### 3.1.3 assign运算 （拷贝/替换/范围赋值）

```c++
   #该例子会擦除mlist2中多余的部分
    list<int> mlist(4,12);
    list<int> mlist2(8,12);
    mlist2.assign(mlist.begin(),mlist.end());
```



```c++
    void
      assign(size_type __n, const value_type& __val)
      { _M_fill_assign(__n, __val); }
    void
	assign(_InputIterator __first, _InputIterator __last)
	{ _M_assign_dispatch(__first, __last, __false_type()); }

 template<typename _Tp, typename _Alloc>
    void
    list<_Tp, _Alloc>::
    _M_fill_assign(size_type __n, const value_type& __val)
    {
      iterator __i = begin();
      for (; __i != end() && __n > 0; ++__i, --__n)
        *__i = __val;
      if (__n > 0)
        insert(end(), __n, __val);
      else
        erase(__i, end());
    }

  template<typename _Tp, typename _Alloc>
    template <typename _InputIterator>
      void
      list<_Tp, _Alloc>::
      _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
			 __false_type)
      {
        iterator __first1 = begin();
        iterator __last1 = end();
        for (; __first1 != __last1 && __first2 != __last2;
	     ++__first1, ++__first2)
          *__first1 = *__first2;
        if (__first2 == __last2)
          erase(__first1, __last1);
        else
          insert(__last1, __first2, __last2);
      }
```

### 3.1.4    get_allocator() const _GLIBCXX_NOEXCEPT

获取分配器

### 3.1.5 其他运算

```
 1 bool empty()  //判断是否为空
 
 2 size_type  size() //返回当前list的元素个数
 
 3 size_type max_size() //list的最大插入个数
 
 4 void resize(size_type __new_size); //重新设置大小
 
 5 //如果当前列表数据小于设置尺寸，则追加给定的_x
 void resize(size_type __new_size, const value_type& __x);
 
 6 void push_front(const value_type& __x) //前插
 
 7 void emplace_front(_Args&&... __args) //前插
 8  void pop_front() //后删
 
 9 //指定位置插入
 iterator emplace(const_iterator __position,_Args&&... __args); 
 iterator insert(const_iterator __position, value_type&& __x)
 
  10 //擦除指定位置的数据，节点大小每删除一个就减小1
  iterator erase(const_iterator__first,const_iterator __last) 
   void swap(list& __x) //列表之间交换
   
  11  //__position是指当前列表插入的位置，将数据插入当前列表位置之前或者之后，并将之前的列表插过的元素清空
   void splice(const_iterator __position,list&& __x,const_iterator __first,const_iterator __last) noexcept
   
   12 void remove(const _Tp& __value);//删除指定的值
   13   _Predicate是一个函数，删除满足条件的值    
   template<typename _Predicate>
	void remove_if(_Predicate);
   14 void unique(); //去除重复的
   15 void merge(list&& __x);//合并以及清空_X
   16 void merge(list&& __x, _StrictWeakOrdering __comp);//归并合并，清空_x
   17 void reverse() _GLIBCXX_NOEXCEPT //翻转
   18 排序
     template<typename _StrictWeakOrdering>
	void sort(_StrictWeakOrdering);
	
```

## 3.2 deque

双端队列，支持随机访问，因为重写了"[]"运算符。

deque的存储是一个个的连续块，这些连续块中包含一个个的元素。 如下所示，展示了deque的部分数据结构，从里面可以看到，连续块实际上就是**_Map_pointer**,而块实际上是**_Elt_pointer**，对于每个块，又有指向当前元素的指针**_M_cur**，以及当前块的头指针**_M_first**和尾指针**_M_last**，以及指向连续块管理中心的**_M_node**，在遍历时，如果当前指针浏览到末尾后，并且是向下遍历，**_M_node**就需要加1，遍历下一个中心。

```c++
 _GLIBCXX_CONSTEXPR inline size_t
  __deque_buf_size(size_t __size)
  { return (__size < _GLIBCXX_DEQUE_BUF_SIZE
	    ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }

template<typename _Tp, typename _Ref, typename _Ptr>
    struct _Deque_iterator
    {
      typedef _Deque_iterator<_Tp, _Tp&, _Tp*>	     iterator;
      typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
      typedef _Tp*					 _Elt_pointer;
      typedef _Tp**					_Map_pointer;
      typedef std::random_access_iterator_tag	iterator_category;
        
      typedef _Tp				value_type;
      typedef _Ptr				pointer;
      typedef _Ref				reference;
      typedef size_t				size_type;
      typedef ptrdiff_t				difference_type;
      typedef _Deque_iterator			_Self;
 
      _Elt_pointer _M_cur; //此迭代器所指之缓冲区中的现行（current）元素
      _Elt_pointer _M_first; // 此迭代器所指之缓冲区的头
      _Elt_pointer _M_last;  // 此迭代器所指之缓冲区的尾（含备用空间）
      _Map_pointer _M_node; // 指向管控中心
      //初始化
      _Deque_iterator(_Elt_pointer __x, _Map_pointer __y) _GLIBCXX_NOEXCEPT
      : _M_cur(__x), _M_first(*__y),
	_M_last(*__y + _S_buffer_size()), _M_node(__y) { }

      _Deque_iterator() _GLIBCXX_NOEXCEPT
      : _M_cur(), _M_first(), _M_last(), _M_node() { }

      _Deque_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT
      : _M_cur(__x._M_cur), _M_first(__x._M_first),
	_M_last(__x._M_last), _M_node(__x._M_node) { }
        
        
     _Self&
      operator++() _GLIBCXX_NOEXCEPT
      {
	++_M_cur;
	if (_M_cur == _M_last)
	  {
	    _M_set_node(_M_node + 1);
	    _M_cur = _M_first;
	  }
	return *this;
      }
        
     reference
      operator*() const _GLIBCXX_NOEXCEPT
      { return *_M_cur; }
    }
   
```



### 3.2.1 构造方法

总共有10个构造函数。常用的有：

```c++
  __a 分配器
  __vallue 填充的常数项
  __n 初始化的节点个数
  __x 复制deque

```



```c++
deque() : _Base() { }
deque(const allocator_type& __a)
deque(size_type __n, const value_type& __value,
	    const allocator_type& __a = allocator_type())
      : _Base(__a, __n)
deque(const deque& __x) //浅拷贝
deque(deque&& __x)
deque(const deque& __x, const allocator_type& __a)
deque(deque&& __x, const allocator_type& __a)；//拷贝的同时，清空__x
deque(_InputIterator __first, _InputIterator __last,
	    const allocator_type& __a = allocator_type())
```



 从下面的代码可以看到，__n指的是申请的元素个数，通过元素求得块的个数，从代码里可以看到，块的个数是有可能多出来一块的。

```c++
  _Deque_base()
      : _M_impl()
      { _M_initialize_map(0); }
  template<typename _Tp, typename _Alloc>
    void
    _Deque_base<_Tp, _Alloc>::
    _M_initialize_map(size_t __num_elements)
    {
      const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))
				  + 1);

      this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
					   size_t(__num_nodes + 2));
      this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);

      // For "small" maps (needing less than _M_map_size nodes), allocation
      // starts in the middle elements and grows outwards.  So nstart may be
      // the beginning of _M_map, but for small maps it may be as far in as
      // _M_map+3.

      _Map_pointer __nstart = (this->_M_impl._M_map
			       + (this->_M_impl._M_map_size - __num_nodes) / 2);
      _Map_pointer __nfinish = __nstart + __num_nodes;

      __try
	{ _M_create_nodes(__nstart, __nfinish); }
      __catch(...)
	{
	  _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
	  this->_M_impl._M_map = _Map_pointer();
	  this->_M_impl._M_map_size = 0;
	  __throw_exception_again;
	}

      this->_M_impl._M_start._M_set_node(__nstart);
      this->_M_impl._M_finish._M_set_node(__nfinish - 1);
      this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
      this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
					+ __num_elements
					% __deque_buf_size(sizeof(_Tp)));
    }
```

### 3.2.2 函数以及重写符号

1. assign

   可以看到，该函数同样用于拷贝，替换，以及范围赋值

   ```c++
     void
         assign(size_type __n, const value_type& __val)
         { _M_fill_assign(__n, __val); }
     void
           assign(_InputIterator __first, _InputIterator __last)
           { _M_assign_dispatch(__first, __last, __false_type()); }
   
   template<typename _InputIterator>
     void
           _M_assign_dispatch(_InputIterator __first, _InputIterator __last,__false_type)
           {
             typedef typename std::iterator_traits<_InputIterator>
             ::iterator_category _IterCategory;
             _M_assign_aux(__first, __last, _IterCategory());
   	    }
   template <typename _Tp, class _Alloc>
       template <typename _InputIterator>
      void
         deque<_Tp, _Alloc>::
         _M_assign_aux(_InputIterator __first, _InputIterator __last,
   		    std::input_iterator_tag)
         {
           iterator __cur = begin();
           for (; __first != __last && __cur != end(); ++__cur, ++__first)
             *__cur = *__first;
           if (__first == __last)
             _M_erase_at_end(__cur);
           else
             insert(end(), __first, __last);
         }
   ```

   

2. 重写 ”=“

   ```c++
   如果当前节点过多，就删除掉多余的，删除后再赋值。其他情况下，就直接插入
   template <typename _Tp, typename _Alloc>
       deque<_Tp, _Alloc>&
       deque<_Tp, _Alloc>::
       operator=(const deque& __x)
       {
         if (&__x != this)
   	{
   	  const size_type __len = size();
   	  if (__len >= __x.size()){
            _M_erase_at_end(std::copy(__x.begin(), __x.end(),this->_M_impl._M_start));
   	  }else
   	    {
   	      const_iterator __mid = __x.begin() + difference_type(__len);
   	      std::copy(__x.begin(), __mid, this->_M_impl._M_start);
   	      insert(this->_M_impl._M_finish, __mid, __x.end());
   	    }
   	}
         return *this;
       }
   
    deque&
         operator=(deque&& __x) noexcept(_Alloc_traits::_S_always_equal())
         {
   	using __always_equal = typename _Alloc_traits::is_always_equal;
   	_M_move_assign1(std::move(__x), __always_equal{});
   	return *this;
         }
   ```

   

3. resize

   如果有指定默认值，且新的节点个数大于原来的，就使用指定默认值，否则就使用类型的默认值。

   ```
        void
         resize(size_type __new_size)
         {
   	const size_type __len = size();
   	if (__new_size > __len)
   	  _M_default_append(__new_size - __len);
   	else if (__new_size < __len)
   	  _M_erase_at_end(this->_M_impl._M_start
   			  + difference_type(__new_size));
         }
      void
         resize(size_type __new_size, const value_type& __x)
         {
   	const size_type __len = size();
   	if (__new_size > __len)
   	  insert(this->_M_impl._M_finish, __new_size - __len, __x);
   	else if (__new_size < __len)
   	  _M_erase_at_end(this->_M_impl._M_start
   			  + difference_type(__new_size));
         }
   ```

   

4. shrink_to_fit

   清楚超出容量的数据，但是不破坏容器的本身的容量

   ```
    void
       shrink_to_fit() noexcept
       {
         _M_shrink_to_fit();
       }
       
   ```

5. 其他方法不再介绍

## 3.3 vector

  *vector* 是向量类型,它可以容纳许多类型的数据,如若干个整数。vector的扩容方式是将旧的数组转移到新的数组里去，这种方式是比较耗费时间的。以push_back为例子。每次扩容至少比原来增加一倍。

```c++
   void
        push_back(value_type &&__x)
            {
                  emplace_back(std::move(__x));
            }
/////////////////////////////////////////////////////////
  template<typename _Tp, typename _Alloc>
    template<typename... _Args>
      void
      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_emplace_back_aux(std::forward<_Args>(__args)...); //如果容量不够，就开始扩容存储了
      }
 //////////////////////////////////////////////////////////
  template<typename _Tp, typename _Alloc>
    template<typename... _Args>
      void
      vector<_Tp, _Alloc>::
      _M_emplace_back_aux(_Args&&... __args)
      {
          //计算需要扩容的长度，这里为1，最终返回的是扩容后的数组长度。
	const size_type __len =
	  _M_check_len(size_type(1), "vector::_M_emplace_back_aux"); 
	pointer __new_start(this->_M_allocate(__len));
	pointer __new_finish(__new_start);
	__try
	  {
	    _Alloc_traits::construct(this->_M_impl, __new_start + size(),
				     std::forward<_Args>(__args)...);
	    __new_finish = pointer();

	    __new_finish
	      = std::__uninitialized_move_if_noexcept_a
	      (this->_M_impl._M_start, this->_M_impl._M_finish,
	       __new_start, _M_get_Tp_allocator());

	    ++__new_finish;
	  }
	__catch(...)
	  {
	    if (!__new_finish)
	      _Alloc_traits::destroy(this->_M_impl, __new_start + size());
	    else
	      std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
	    _M_deallocate(__new_start, __len);
	    __throw_exception_again;
	  }
	std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
		      _M_get_Tp_allocator());
	_M_deallocate(this->_M_impl._M_start,
		      this->_M_impl._M_end_of_storage
		      - this->_M_impl._M_start);
	this->_M_impl._M_start = __new_start;
	this->_M_impl._M_finish = __new_finish;
	this->_M_impl._M_end_of_storage = __new_start + __len;
      }
///////////////////////////////////////////
/**
  计算扩容后的数组长度，从这里可以看到，扩容后的长度至少为之前的1倍
*/
    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;
            }

/////////////////////////////////
/**
  返回当前数组长度
*/
    size_type
            size() const _GLIBCXX_NOEXCEPT
            {
                  return size_type(this->_M_impl._M_finish - this->_M_impl._M_start);
            }
```

## 3.3 array

实际上就是实现了一个数组，不过对于数组做了一些操作，非可变

```c++
template<typename _Tp, std::size_t _Nm>
    struct __array_traits
    {
      typedef _Tp _Type[_Nm];

      static constexpr _Tp&
      _S_ref(const _Type& __t, std::size_t __n) noexcept
      { return const_cast<_Tp&>(__t[__n]); }

      static constexpr _Tp*
      _S_ptr(const _Type& __t) noexcept
      { return const_cast<_Tp*>(__t); }
    };
```

## 3.4 queue

单端队列吧，先进先出，底层默认调用的是deque实现。

```
template<typename _Tp, typename _Sequence = deque<_Tp> >
    class queue
    {
    public:
      typedef typename _Sequence::value_type                value_type;
      typedef typename _Sequence::reference                 reference;
      typedef typename _Sequence::const_reference           const_reference;
      typedef typename _Sequence::size_type                 size_type;
      typedef          _Sequence                            container_type;

    protected:
      /**
       *  'c' is the underlying container.  Maintainers wondering why
       *  this isn't uglified as per style guidelines should note that
       *  this name is specified in the standard, [23.2.3.1].  (Why?
       *  Presumably for the same reason that it's protected instead
       *  of private: to allow derivation.  But none of the other
       *  containers allow for derivation.  Odd.)
       */
      _Sequence c;

    public:
      explicit
      queue(const _Sequence& __c)
      : c(__c) { }

      explicit
      queue(_Sequence&& __c = _Sequence())
      : c(std::move(__c)) { }

      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
	explicit
	queue(const _Alloc& __a)
	: c(__a) { }

      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
	queue(const _Sequence& __c, const _Alloc& __a)
	: c(__c, __a) { }

      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
	queue(_Sequence&& __c, const _Alloc& __a)
	: c(std::move(__c), __a) { }

      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
	queue(const queue& __q, const _Alloc& __a)
	: c(__q.c, __a) { }

      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
	queue(queue&& __q, const _Alloc& __a)
	: c(std::move(__q.c), __a) { }
#endif

```

## 3.5 set

 set中，每种元素只能出现一次。

### 3.5.1 构造方法

set的构造方法有12种

```c++
template <typename _Key, typename _Compare = std::less<_Key>,
                typename _Alloc = std::allocator<_Key>>
      class set
      {
            // concept requirements
            typedef typename _Alloc::value_type _Alloc_value_type;
            __glibcxx_class_requires(_Key, _SGIAssignableConcept)
                __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
                                          _BinaryFunctionConcept)
                    __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)

                        public :
                // typedefs:
                //@{
                /// Public typedefs.
                typedef _Key key_type;
            typedef _Key value_type;
            typedef _Compare key_compare;
            typedef _Compare value_compare;
            typedef _Alloc allocator_type;
            //@}

      private:
            typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Key>::other _Key_alloc_type;

            //set的底层数据结构是基于红黑树的，可以看到，每个元素的identy实际就是key
            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.

            typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits;

      public:
            //@{
            ///  Iterator-related typedefs.
            typedef typename _Alloc_traits::pointer pointer;
            typedef typename _Alloc_traits::const_pointer const_pointer;
            typedef typename _Alloc_traits::reference reference;
            typedef typename _Alloc_traits::const_reference const_reference;
            // _GLIBCXX_RESOLVE_LIB_DEFECTS
            // DR 103. set::iterator is required to be modifiable,
            // but this allows modification of keys.
            typedef typename _Rep_type::const_iterator iterator;
            typedef typename _Rep_type::const_iterator const_iterator;
            typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
            typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
            typedef typename _Rep_type::size_type size_type;
            typedef typename _Rep_type::difference_type difference_type;
            //@}
            set()
                _GLIBCXX_NOEXCEPT_IF(
                    is_nothrow_default_constructible<allocator_type>::value
                        &&is_nothrow_default_constructible<key_compare>::value)
                : _M_t() {}
            explicit set(const _Compare &__comp,
                         const allocator_type &__a = allocator_type())
                : _M_t(__comp, _Key_alloc_type(__a)) {}
          
            template <typename _InputIterator>
            set(_InputIterator __first, _InputIterator __last)
                : _M_t()
            {
                  _M_t._M_insert_unique(__first, __last);
            }
            template <typename _InputIterator>
            set(_InputIterator __first, _InputIterator __last,
                const _Compare &__comp,
                const allocator_type &__a = allocator_type())
                : _M_t(__comp, _Key_alloc_type(__a))
            {
                  _M_t._M_insert_unique(__first, __last);
            }
            set(const set &__x)
                : _M_t(__x._M_t) {}
      /////////////////////////////////////////////////////////////
            template<typename _Tp>
    struct _Identity
    : public unary_function<_Tp,_Tp>
    {
      _Tp&
      operator()(_Tp& __x) const
      { return __x; }

      const _Tp&
      operator()(const _Tp& __x) const
      { return __x; }
    };
```

## 3.6 map

map因为底层也是调用的红黑树，并且存入红黑树的是<key,value>,且以key作为排序的方式，所以不做介绍。

### 3.6.1 map与unordered_map的区别

map是基于红黑树，unordered_map是基于散列表。因此，在查询上，unordered_map会快一些，但是由于散列表性能不稳定，可能会有hash碰撞问题，导致查询时间为O(n)。插入数据上，map相对要快速一些，因为unordered_map中链表的插入是比较慢的。此外，在空间存储上，unordered_map要占的少一些，红黑树除了存储数据，还要存储左右子节点、父节点以及是否为黑节点。

```c++
#include <iostream>
#include <unordered_map>
#include<map>
#include<ctime>
using namespace std;
typedef int key;
typedef string value;
#define N 10000
#define VA "hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh"
int main()
{
    clock_t map_time_start,map_time_end,unorder_map_time_start,unorder_map_time_end;
    unordered_map<key,value> m_unorder_map;
    map<key,value> m_map;
    
    map_time_start = clock();
    for(int i=0;i<N;i++){
        m_map.insert(pair<key,value>(i,VA));
    }
    map_time_end = clock();
    

    unorder_map_time_start = clock();
    for(int i=0;i<N;i++){
        m_unorder_map.insert(pair<key,value>(i,VA));
    }
    unorder_map_time_end = clock();

    cout <<"map加入数据耗时："<<map_time_end - map_time_start << " ms" << endl;
    cout <<"unordered_map加入数据耗时："<<unorder_map_time_end - unorder_map_time_start << " ms" << endl;  

    map_time_start = clock();
    for(int i=0;i<N;i++){
        m_map.count(i);
    }
    map_time_end = clock();
    

    unorder_map_time_start = clock();
    for(int i=0;i<N;i++){
        m_unorder_map.count(i);
    }
    unorder_map_time_end = clock();

    cout <<"map查询数据耗时："<<map_time_end - map_time_start << " ms" << endl;
    cout <<"unordered_map查询数据耗时："<<unorder_map_time_end - unorder_map_time_start << " ms" << endl;    

    m_map.clear();
    m_unorder_map.clear();


    
}
```

![1680785668120](README.assets/1680785668120.png)

### 3.6.2 unodered_map

unodered_map底层是基于散列表，也就是桶+链表的方式。每次扩增容量，至少是原来的2倍，也就是比原来的2倍多一些，初始容量为1。需要注意的是，unodered_map的扩容方式会因为编译器的不同，可能会有所改变，在vs2019中，每次扩容是直接扩容为原来的8倍。扩容时，是直接将原来的数据复制到新的桶里面，并且复制的时候，采用的是倒插法。

```c++

      inline std::pair<bool, std::size_t>
      _Prime_rehash_policy::
          _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
                         std::size_t __n_ins) const
      {
        if (__n_elt + __n_ins > _M_next_resize)
        {
          float __min_bkts = ((float(__n_ins) + float(__n_elt)) / _M_max_load_factor);
          if (__min_bkts > __n_bkt)
          {
            __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
            const unsigned long *__p =
                std::lower_bound(__prime_list, __prime_list + _S_n_primes,
                                 __min_bkts);
            _M_next_resize = static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
            return std::make_pair(true, *__p);
          }
          else
          {
            _M_next_resize = static_cast<std::size_t>(__builtin_ceil(__n_bkt * _M_max_load_factor));
            return std::make_pair(false, 0);
          }
        }
        else
          return std::make_pair(false, 0);
      }

```

```c++
    // Rehash when there is no equivalent elements.
    template<typename _Key, typename _Value,
            typename _Alloc, typename _ExtractKey, typename _Equal,
            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
            typename _Traits>
    void
    _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
            _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    _M_rehash_aux(size_type __n, std::true_type) {
        __bucket_type *__new_buckets = _M_allocate_buckets(__n);
        __node_type *__p = _M_begin();
        _M_before_begin._M_nxt = nullptr;
        std::size_t __bbegin_bkt = 0;
        while (__p) {
            __node_type *__next = __p->_M_next();
            std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
            if (!__new_buckets[__bkt]) {
                __p->_M_nxt = _M_before_begin._M_nxt;
                _M_before_begin._M_nxt = __p;
                __new_buckets[__bkt] = &_M_before_begin;
                if (__p->_M_nxt)
                    __new_buckets[__bbegin_bkt] = __p;
                __bbegin_bkt = __bkt;
            } else {
                __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
                __new_buckets[__bkt]->_M_nxt = __p;
            }
            __p = __next;
        }

        _M_deallocate_buckets();
        _M_bucket_count = __n;
        _M_buckets = __new_buckets;
    }
```







```c++
struct _Prime_rehash_policy
      {
        _Prime_rehash_policy(float __z = 1.0)
            : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0) {}

        float
        max_load_factor() const
        {
          return _M_max_load_factor;
        }

        // Return a bucket size no smaller than n.
        std::size_t
        _M_next_bkt(std::size_t __n) const;

        // Return a bucket count appropriate for n elements
        std::size_t
        _M_bkt_for_elements(std::size_t __n) const;

        // __n_bkt is current bucket count, __n_elt is current element count,
        // and __n_ins is number of elements to be inserted.  Do we need to
        // increase bucket count?  If so, return make_pair(true, n), where n
        // is the new bucket count.  If not, return make_pair(false, 0).
        std::pair<bool, std::size_t>
        _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
                       std::size_t __n_ins) const;

        enum
        {
          _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48
        };

        float _M_max_load_factor;
        float _M_growth_factor;
        mutable std::size_t _M_next_resize;
      };

      extern const unsigned long __prime_list[];

      // XXX This is a hack.  There's no good reason for any of
      // _Prime_rehash_policy's member functions to be inline.

      // Return a prime no smaller than n.
      inline std::size_t
      _Prime_rehash_policy::
          _M_next_bkt(std::size_t __n) const
      {
        const unsigned long *__p = std::lower_bound(__prime_list, __prime_list + _S_n_primes, __n);
        _M_next_resize =
            static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
        return *__p;
      }

      // Return the smallest prime p such that alpha p >= n, where alpha
      // is the load factor.
      inline std::size_t
      _Prime_rehash_policy::
          _M_bkt_for_elements(std::size_t __n) const
      {
        const float __min_bkts = __n / _M_max_load_factor;
        const unsigned long *__p = std::lower_bound(__prime_list, __prime_list + _S_n_primes, __min_bkts);
        _M_next_resize =
            static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
        return *__p;
      }

  inline std::pair<bool, std::size_t>
  _Prime_rehash_policy::
  _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
		 std::size_t __n_ins) const
  {
    if (__n_elt + __n_ins > _M_next_resize)
      {
	float __min_bkts = ((float(__n_ins) + float(__n_elt))
			    / _M_max_load_factor);
	if (__min_bkts > __n_bkt)
	  {
	    __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
	    return std::make_pair(true,
				  _M_next_bkt(__builtin_ceil(__min_bkts)));
	  }
	else 
	  {
	    _M_next_resize = static_cast<std::size_t>
	      (__builtin_ceil(__n_bkt * _M_max_load_factor));
	    return std::make_pair(false, 0);
	  }
      }
    else
      return std::make_pair(false, 0);
  }
```



# 4 红黑树

红黑树位于mingw64\lib\gcc\x86_64-w64-mingw32\6.4.0\include\c++\bits\stl_tree.h文件中，红黑树是一种可以自旋的平衡二叉树。

```c++
  enum _Rb_tree_color
  {
    _S_red = false,
    _S_black = true
  };

  struct _Rb_tree_node_base
  {
    typedef _Rb_tree_node_base *_Base_ptr;
    typedef const _Rb_tree_node_base *_Const_Base_ptr;

    _Rb_tree_color _M_color;
    _Base_ptr _M_parent;
    _Base_ptr _M_left;
    _Base_ptr _M_right;

    /**
     * 因为左值必然小于右值，所以只需要向左查找就可以找到最小值
    */
    static _Base_ptr
    _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
    {
      while (__x->_M_left != 0)
        __x = __x->_M_left;
      return __x;
    }
  
    static _Const_Base_ptr
    _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
    {
      while (__x->_M_left != 0)
        __x = __x->_M_left;
      return __x;
    }
    /**
     * 因为左值必然小于右值，所以只需要向右查找就可以找到最大值
    */
    static _Base_ptr
    _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
    {
      while (__x->_M_right != 0)
        __x = __x->_M_right;
      return __x;
    }

    static _Const_Base_ptr
    _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
    {
      while (__x->_M_right != 0)
        __x = __x->_M_right;
      return __x;
    }
  };
```

# 5 多线程

## 5.1  多线程

## 5.2 互斥锁锁

### 5.2.1 互斥锁mutex

互斥意味着对于同一个资源，同一时间，只能由一个线程去占有。如果不引入互斥的概念，那么最终的结果可能会和预期有所偏离，代码如下所示，由于多个线程可以同时占有当前资源 "num",就导致最终的计算结果和预期偏离，当加锁后，则不会出现这种情况。

```c++
#include <iostream>
#include <pthread.h>
#include <mutex>
#include <thread>
#include<ctime>

int num = 0;
using namespace std;

#define THREAD_NUM 40000

int no_lock() {
    mutex mtex;
    thread thd[THREAD_NUM];
    auto f = []() -> void * {
        num++;
    };
    ::clock_t time_start, time_end;
    time_start = ::clock();
    for (int i = 0; i < THREAD_NUM; i++) {
        thd[i] = thread(f);
    }
    for (int i = 0; i < THREAD_NUM; i++) {
        thd[i].join();
    }
    cout << "不加锁的计算结果==" << num << endl;
    //pthread_exit(NULL);
    time_end = ::clock();
    cout << "不加锁的耗费时间为:" << time_end - time_start << "ms" << endl;
    return 0;
}

void has_lock() {
    mutex mtex;
    thread thd[THREAD_NUM];
    auto f = [](mutex *tmux) -> void * {
        unique_lock<mutex> uniqueLock(*tmux);
        num++;
    };

    ::clock_t time_start, time_end;
    time_start = ::clock();
    for (int i = 0; i < THREAD_NUM; i++) {
        thd[i] = thread(f, &mtex);
    }
    for (int i = 0; i < THREAD_NUM; i++) {
        thd[i].join();
    }
    cout << "加锁后的计算结果==" << num << endl;
    time_end = ::clock();
    cout << "加锁后，耗费时间为:" << time_end - time_start << "ms" << endl;
}

int main() {
    //no_lock();
    has_lock();
    pthread_exit(NULL);
}
```

![1681179397052](README.assets/1681179397052.png)

![1681179414763](README.assets/1681179414763.png)

![1681179457989](README.assets/1681179457989.png)

![1681179486685](README.assets/1681179486685.png)

 mutex的使用比较简单，初始化mutex后，就可以直接调用lock和unlock.但是会存在一个问题，也就是死锁情况的产生。假设程序再执行过程中，资源为C和D,线程A抢占了C资源，线程B抢占了D资源，现在线程A需要抢D资源，因为抢占不到陷入阻塞状态，而线程B因为要抢占C资源而陷入阻塞，发生死锁。

### 5.2.2 互斥锁的种类

在互斥锁中，包含可重入和不可重入的锁，即递归调用锁和非递归调用锁，细分又可以分为超时锁和普通锁，即总共四类。

1.mtex

2.timed_mutex

3.recursive_mutex

4 recursive_timed_mutex

上述锁都需要自己调用lock和unlock，使用起来比较麻烦，容易导致忘记释放锁或者死锁的存在。于是有了unique_lock和lock_guard的存在。两者在构造函数中加锁，在析构函数中释放锁。从下面的代码可以看到，unique_lock更灵活，但是意味着对于性能的消耗相对高一些。如果对于性能追求不是很高，可以优先考虑unique_lock。

## 5.3 共享锁

共享锁即读写锁，读锁可以多个线程共同持有，写锁就是互斥锁。共享锁分为shared_timed_mutex和普通锁shared_mutex两类，shared_mutex可以配合shared_lock和unique_lock使用，读锁和写锁不能同时存在，不然会发生死锁情况。

```c++
#include <iostream>
#include<shared_mutex>
#include<mutex>
#include<thread>
#include<ctime>

using namespace std;

//定义书籍数量只有20本，超过了就不能抢了。
int books_num = 90000;
typedef shared_mutex MUTEX_TYPE;
#define THREAD_NUM 70000
MUTEX_TYPE my_mutex;

void *order(MUTEX_TYPE *mtx, int *orders) {

    shared_lock<MUTEX_TYPE> sharedLock(*mtx); //读锁
    unique_lock<MUTEX_TYPE> uniqueLock(*mtx);//写锁
    if (books_num > *orders) {
        (*orders)++;
    }

    return (void *) (orders);
}

void *order_nolocks(int *orders) {
    if (books_num > *orders) {
        (*orders)++;
    }
    return (void *) (orders);
}

void haslocks() {
    thread thd[THREAD_NUM];
    clock_t time_start, time_end;
    time_start = ::clock();
    int orders = 0;
    for (int i = 0; i < THREAD_NUM; i++) {
        thd[i] = thread(order, &my_mutex, &orders);
    }
    for (int i = 0; i < THREAD_NUM; i++) {
        thd[i].join();
    }
    time_end = ::clock();
    cout << "加锁情况下耗时：" << time_end - time_start << "ms" << endl;
    cout << "发起秒杀：" << THREAD_NUM << "次" << "，书籍还剩:" << books_num - orders << "本" << endl;

}

void nolocks() {
    thread thd[THREAD_NUM];
    clock_t time_start, time_end;
    int orders = 0;
    time_start = ::clock();
    for (int i = 0; i < THREAD_NUM; i++) {
        thd[i] = thread(order_nolocks, &orders);
    }
    for (int i = 0; i < THREAD_NUM; i++) {
        thd[i].join();
    }
    time_end = ::clock();
    cout << "不加锁的情况下耗时：" << time_end - time_start << "ms" << endl;
    cout << "发起秒杀：" << THREAD_NUM << "次" << "，书籍还剩:" << books_num - orders << "本" << endl;

}

int main() {
    nolocks();
    haslocks();
    return 0;
}

```

## 5.4 条件变量

 当需要死循环判断某个条件成立与否时【true or false】，我们往往需要开一个线程死循环来判断，这样**非常消耗CPU**。使用条件变量，可以让当前线程wait，释放CPU，如果条件改变时，我们再notify退出线程，再次进行判断。 

 条件锁就是所谓的条件变量，某一个线程因为某个条件未满足时可以使用条件变量使该程序处于阻塞状态。一旦条件满足以“信号量”的方式唤醒一个因为该条件而被阻塞的线程(常和互斥锁配合使用)，唤醒后，需要检查变量，避免虚假唤醒。最为常见就是在线程池中，起初没有任务时任务队列为空，此时线程池中的线程因为“任务队列为空”这个条件处于阻塞状态。一旦有任务进来，就会以信号量的方式唤醒一个线程来处理这个任务。
头文件：`< condition_variable >`
类型：`std::condition_variable`（只和`std::mutex`一起工作） 和 `std::condition_variable_any`（符合类似互斥元的最低标准的任何东西一起工作）。 

std::condition_variable_any 能与std::shared_lock一同使用，在std::shared_mutex上以共享所有权模式等待。

condition_variable_any 类是std::condition_variable的泛化。相对于只在std::unique_lock<std::mutex>上工作的std::condition_variable ， condition_variable_any 能在任何满足基本可锁定 (BasicLockable) 要求的锁上工作(也可用于自定义可锁定的类型)。

```c++
#include <iostream>
#include<condition_variable>
#include <mutex>
#include<thread>
#include<shared_mutex>
#include<vector>
#include<ctime>

using namespace std;
typedef std::mutex MUTEX_TYPE;
typedef condition_variable_any CONDITION_TYPE;
typedef int DATA_TYPE;
MUTEX_TYPE mtex;
vector<DATA_TYPE> ve;

#define DEVOLOP_NUM 1
#define CONSUMER_NUM 20

void *devolop(MUTEX_TYPE *mtx, CONDITION_TYPE *condition) {
    unique_lock<MUTEX_TYPE> uniqueLock(*mtx);
    for (int i = 0; i < 25; i++) {
        ve.push_back(i);
    }
    uniqueLock.unlock();
    condition->notify_one();
}

void *consumer(MUTEX_TYPE *mtx, CONDITION_TYPE *condition, int numbers) {
    unique_lock<MUTEX_TYPE> uniqueLock(*mtx);
    while (ve.empty()) {
       condition->wait(uniqueLock);
    }
    int data = ve.back();
    ve.pop_back();
    cout << numbers << "号消费" << "消费了资源" << data << endl;
    uniqueLock.unlock();
}

int main() {

    thread thd_dev[DEVOLOP_NUM];
    thread thd_consu[CONSUMER_NUM];
    CONDITION_TYPE condition;
    for (int i = 0; i < DEVOLOP_NUM; i++) {
        thd_dev[i] = thread(&devolop, &mtex, &condition);
    };

    for (int i = 0; i < DEVOLOP_NUM; i++) {
        thd_dev[i].join();
    };

    for (int i = 0; i < CONSUMER_NUM; i++) {
        thd_consu[i] = thread(&consumer, &mtex, &condition, i);
    };

    for (int i = 0; i < CONSUMER_NUM; i++) {
        thd_consu[i].join();
    };

    return 0;
}

```

## 5.5 原子操作


​         所谓原子操作，就是多线程程序中“最小的且不可并行化的”操作。对于在多个线程间共享的一个资源而言，这意味着同一时刻，多个线程中有且仅有一个线程在对这个资源进行操作，即互斥访问。提到“互斥”访问，熟悉多线程开发的同学可能立即想到Windows平台下使用的临界区/CRITICAL_SECTION、互斥体/Mutex。实现互斥通常需要平台相关的特殊指令，在C++11标准之前，这意味着需要在C/C++代码中嵌入平台相关的内联汇编代码。 平台相关意味着：1.你必须了解平台相关的编译器扩展；2.无法跨平台运行你的多线程程序。

多线程中需要同步的总是资源/数据，而不是代码。因此C++11对数据进行了更为良好的抽象，引入"原子数据类型"/atomic类型，以达到对开发者掩盖互斥锁、临界区的目的。

![3e897c5e950f4992ad59ff033d3691eb](README.assets/3e897c5e950f4992ad59ff033d3691eb.png)



```c++
#include <iostream>
#include<condition_variable>
#include <mutex>
#include<thread>
#include<shared_mutex>
#include<vector>
#include<atomic>

using namespace std;

typedef atomic_int DATA_TYPE;

#define DEVOLOP_NUM 20000

DATA_TYPE count(0);

void *devolop() {
    count+=1;
}


int main() {
    thread thd_dev[DEVOLOP_NUM];
    for (int i = 0; i < DEVOLOP_NUM; i++) {
        thd_dev[i] = thread(&devolop);
    };

    for (int i = 0; i < DEVOLOP_NUM; i++) {
        thd_dev[i].join();
    };

   cout<<count <<endl;
    return 0;
}
////////////////////////////////////////////////////////////////
#include <iostream>
#include <pthread.h>
#include <mutex>
#include <thread>
#include<ctime>
#include <atomic>
std::atomic_int  aint(0);
int num = 0;
int check=0;
using namespace std;

#define THREAD_NUM 30000
typedef  recursive_timed_mutex MTEX_TYPE;
MTEX_TYPE mtex;
chrono::microseconds timeout(1);

int no_lock() {
    thread thd[THREAD_NUM];
    auto f = []() -> void * {
        aint++;
    };
    ::clock_t time_start, time_end;
    time_start = ::clock();
    for (int i = 0; i < THREAD_NUM; i++) {
        thd[i] = thread(f);
    }
    for (int i = 0; i < THREAD_NUM; i++) {
        thd[i].join();
    }
    cout << "不加锁并且使用原子int的计算结果==" << aint << endl;
    //pthread_exit(NULL);
    time_end = ::clock();
    cout << "不加锁的耗费时间为:" << time_end - time_start << "ms" << endl;
    return 0;
}

void has_lock() {
    num = 0;
    thread thd[THREAD_NUM];
    auto f = [](MTEX_TYPE *tmux)  {
        if((*tmux).try_lock_for(timeout)){
            num++;
        }else{
            // cout << "加锁失败"<<endl;
            check++;
        }
        (*tmux).unlock();
        return 0;
    };

    ::clock_t time_start, time_end;
    time_start = ::clock();
    for (int i = 0; i < THREAD_NUM; i++) {
        thd[i] = thread(f, &mtex);
    }
    for (int i = 0; i < THREAD_NUM; i++) {
        thd[i].join();
    }
    cout << "加锁后的计算结果==" << num << endl;
    cout << "计算失败的结果==" << check << endl;
    time_end = ::clock();
    cout << "加锁后，耗费时间为:" << time_end - time_start << "ms" << endl;
}

int main() {
    no_lock();
    has_lock();
    //(NULL);
    return 0;
}


```

![1681286010358](README.assets/1681286010358.png)

![1681286018235](README.assets/1681286018235.png)

## 5.6 线程池

在c++17以及之前，并没有线程池的相关实现，因此，需要自己动手实现。线程池的目的在于：（1）实现线程复用，避免频繁的创建线程导致系统资源以及时间的浪费。（2）实现线程的控制，方便线程管理，并根据特定场景设计合适的线程池。线程池的主要参数包括：核心线程（最小线程）、最大线程、线程队列，空闲线程存活时间以，记时单位以及拒绝策略（超过最大线程，直接拒绝）

核心线程：维持的最小工作线程，即使这些线程处于空闲状态，也不会被销毁。 任务提交到线程池后，首先会检查当前线程数是否达到了corePoolSize，如果没有达到的话，则会创建一个新线程来处理这个任务。 

最大线程：如果线程超过了核心线程，但是没有超过最大线程，提交的任务会被添加到任务队列中。如果线程超过了最大线程，就新开一个线程执行拒绝策略。

线程队列：指的是线程队列的种类，这里默认为queue(先进先出)

空闲线程存活时间：当线程大于核心线程后，创建的线程如果一直处于空闲时间，就要被销毁了。

例子一，在下面的例子中，创建了一个线程池，该线程池在初始化的时候就已经构造好了多个线程，在线程没有添加任务的时候，会通过循环函数一直循环，保证线程不会被销毁，实现线程的复用。从两个测试代码可以看到，多线程之所以耗费的时间比线程池要多上不少，是因为创建线程耗费了大量的时间。而线程池相比同样数量的多线程多出来的时间在于，线程复用中会不断的挂起与唤醒线程。

```c++

#ifndef STL_MY_THREAD_POOL_THREAD_POOL_H
#define STL_MY_THREAD_POOL_THREAD_POOL_H

#include <thread>
#include <mutex>
#include <queue>
#include <vector>
#include <condition_variable>
#include<atomic>
#include<functional>

using namespace std;
using namespace std::literals::chrono_literals;
using callback = void (*)(void *);
typedef recursive_mutex MUTEX_TYPE;

// 任务队列类
// 成员函数介绍：参数1：任务执行函数；参数2：任务执行函数的参数
class Task {
public:
    callback function;
    void *arg;
public:
    Task(callback f, void *arg) {
        function = f;
        this->arg = arg;
    }
};

namespace tools {
    class joiner {
    public:
        joiner(vector<thread> &threads) : m_threads(threads) {

        }
        ~joiner() {
            for (thread &thd: m_threads) {
                if (thd.joinable()) {
                    thd.join();
                }
            }
        }

    private:
        vector<thread> &m_threads;
    };
  //安全队列
    class safe_queue {
    private:
        queue<Task> safe_que;
        MUTEX_TYPE m_mutex;
    public:
        void add(Task && task) {
            unique_lock<MUTEX_TYPE> lk(this->m_mutex);
            this->safe_que.push(task);
        }

        Task* pop_front() {
            unique_lock<MUTEX_TYPE> lk(this->m_mutex);
            Task *task = nullptr;
            if (!this->safe_que.empty()) {
                task = &this->safe_que.front();
                safe_que.pop();
            }
            return task;
        }

    };

}
// 线程池类
class thread_pool {
public:
    thread_pool(int thread_num = thread::hardware_concurrency()) : state(false), thread_joiner(thread_runer) {
        try {
            for (int i = 0; i < thread_num; i++) {
                this->thread_runer.emplace_back(&thread_pool::woker, this);
            }
        } catch (...) {
            this->state = true;
            throw runtime_error("thread create error");
        }
    }

    void add(Task task) {
        //unique_lock<MUTEX_TYPE> lockGuard(this->mtx);
        this->task_queue.add(move(task));
    }
    ~thread_pool() {
        state = true;
    }

private:
    atomic<bool> state;
    tools::safe_queue task_queue;
    vector<thread> thread_runer;
    tools::joiner thread_joiner;
    MUTEX_TYPE  mtx;
    void woker() {

        while (!this->state) {
            //unique_lock<MUTEX_TYPE> lk(this->mtx);
            Task *task = nullptr;
            task = this->task_queue.pop_front();
            if (task ) {
                task->function(task->arg);
                ::free(task->arg);
                task->arg = nullptr;
            } else {
                this_thread::yield();
            }
        }
    }

};

#endif //STL_MY_THREAD_POOL_THREAD_POOL1_H
```

测试代码

```c++
#include <iostream>
#include "utils_thdpool/thread_pool.h"
#include<ctime>

using  namespace  std;
atomic_int  num=0;
#define  NUM 100000
#define  THREAD_NUM 5
void taskFunc(void* arg)
{
    num++;
}

void use_threadpool(){
    clock_t time_start,time_end;
    time_start = clock();
    thread_pool threadPool(THREAD_NUM);
    num = 0;
    for (int i = 1; i <=NUM; ++i)
    {
        int* pNum = new int(i + 100);
        Task task(taskFunc,(void*)pNum);
        threadPool.add(task);
    }
    time_end = clock();
    cout << "使用线程池，耗费时间为：" << time_end - time_start <<"ms"<<endl;
    cout << "使用线程池，计算结果为：" << num <<endl;
}
void use_mutithread(){
    thread thd[NUM];
    clock_t time_start,time_end;
    time_start = clock();
    num = 0;
    for (int i = 0; i <NUM; ++i)
    {
        int* pNum = new int(i + 100);
        thd[i] = thread(taskFunc,(void*)pNum);
    }
    for (int i = 0; i <NUM; ++i)
    {
       thd[i].join();
    }
    time_end = clock();
    cout << "使用多线程，耗费时间为：" << time_end - time_start <<"ms"<<endl;
    cout << "使用多线程，计算结果为：" << num <<endl;
}
int main() {

    use_threadpool();
    use_mutithread();
    return 0;
}

```

![1681476550763](README.assets/1681476550763.png)

将测试代码修改一下：

```c++
#include <iostream>
#include "utils_thdpool/thread_pool.h"
#include<ctime>

using  namespace  std;
atomic_int  num=0;
#define  NUM 10000
#define  THREAD_NUM 5
void taskFunc(void* arg)
{
    int nNum = *(int*)arg;
    num++;
}
void taskFunc1(void* arg)
{
    for(int i=0;i<NUM/THREAD_NUM;i++){
        num++;
    }
}
void use_threadpool(){
    clock_t time_start,time_end;
    time_start = clock();
    thread_pool threadPool(THREAD_NUM);
    num = 0;
    for (int i = 1; i <=NUM; ++i)
    {
        int* pNum = new int(i + 100);
        Task task(taskFunc,(void*)pNum);
        threadPool.add(task);
    }
    time_end = clock();
    cout << "使用线程池，耗费时间为：" << time_end - time_start <<"ms"<<endl;
    cout << "使用线程池，计算结果为：" << num <<endl;
}
void use_mutithread(){

    thread thd[THREAD_NUM];
    clock_t time_start,time_end;
    time_start = clock();
    num = 0;
    for (int i = 0; i <THREAD_NUM; ++i)
    {
        int* pNum = new int(i + 100);
        thd[i] = thread(taskFunc1,(void*)pNum);
    }
    for (int i = 0; i <THREAD_NUM; ++i)
    {
       thd[i].join();
    }
    time_end = clock();
    cout << "使用多线程，耗费时间为：" << time_end - time_start <<"ms"<<endl;
    cout << "使用多线程，计算结果为：" << num <<endl;
}
int main() {

    use_threadpool();
    use_mutithread();
    return 0;
}

```

![1681476869085](README.assets/1681476869085.png)