20210713 STL

明昧 Lv7

2021-07-13 23:11:12 2024-06-24 13:18:49

C++ STL

STL/7/13

STL简介

标准库>STL,标准模板库
STL内含六大部件
展现形式：

补充：命名空间：封装你自己写的东西（函数，模板类等）

标准库里的东西都在命名空间中

把std里面的东西都给放出来能够被使用

迭代器分类的设计//移动的性质因此特别需要搞清楚不理解
数据结构和算法的标准
六大组件：容器，算法，迭代器，仿函数（？），适配器（搞接口），空间配置器

六大组件关系图

1641829659949

算法看不到容器,只看见迭代器，

通过迭代器看到容器，

这就是迭代器需要回答的原因。（上图左下文字

仿函数

特点

1.普通函数

2.可以记录调用次数

3.可以重载（自定义重载）

谓词

概念

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

void test1()
{
	negate<int>n;
	cout << n(50) << endl;
}

void test2()
{
	plus<int>p;
	cout << p(10, 20) << endl;
}

int main()
{
	test1();
	test2();
	std::cout << "Hello World!\n";
}

内建对象

使用例子

1641884351189

左四紫：给定类型，产生函数对象，放进去

左五紫：

分类

黄色部分：内部的这些仿函数都有继承关系

这里是所继承的东西

1641884647946

binary_function:两个操作数的操作

unart_function：一个操作数的操作，比如取反

虽然说这些仿函数单独存在的时候大小实际可能为1

如果被继承了，那么成为父类的仿函数一定是0

对于less，在继承之后：

对于迭代器，需要回答算法的问题

对于仿函数，需要回答适配器的问题

怎样回答，通过继承上图左边两个中的其中一个来回答

想要自己写的仿函数融入STL，最好继承上图左边两个中的其中一个

算术仿函数

//////算术类仿函数 + - * / %////////////////////////////////
//plus仿函数，生成一个对象，里面仅仅有一个函数重载的方法。
template <class T>
struct plus : public binary_function<T, T, T>
{
    T operator()(const T& x, const T& y) const
    { return x + y; }
};

//minus仿函数
template <class T>
struct minus : public binary_function<T, T, T> 
{
    T operator()(const T& x, const T& y) const 
    { return x - y; }
};

template <class T>
struct multiplies : public binary_function<T, T, T>
{
    T operator()(const T& x, const T& y) const
    { return x * y; }
};

template <class T>
struct divides : public binary_function<T, T, T> 
{
    T operator()(const T& x, const T& y) const 
    { return x / y; }
};
template <class T>
struct modulus : public binary_function<T, T, T>
{
    T operator()(const T& x, const T& y) const
    { return x % y; }
};

//取负值
template <class T>
struct negate : public unary_function<T, T>
{
    T operator()(const T& x) const { return -x; }
};

关系仿函数

逻辑仿函数

特殊仿函数介绍

GNUC++特有

1641883342840

G2.9和G4.9名称不一样

分配器

分配器在几个奇怪的命名空间里

都放在ext库下
例子：双向链表搭配，放100个元素，看不同分配器的执行时间
分配器是一个class
没必要单独需要分配器
分配器和容器一起使用
一般的分配空间的方式：malloc，free，new…
反正直接用分配器不好，会需要记住当时利用了多少个
底层都是：malloc，free
operator_new一个函数
malloc会有一些额外的开销/空间使用，相对于你需要申请的内存空间，有时候额外开销比你需要申请的空间所使用的开销都大这个相对程度一般取决于看区块的大小吧，区块小，开销相对而言就很大

元素小小，有时候开销更大大

例子

VC6

const void * 知道是什么类型的一个小技巧
分配器的直接使用://VC6

1641656426536

需要记忆当时候申请了多少内存，挺难用的

BC5//有默认值

G2.9

1641658369093

这个版本的容器用的分配器和通常意义一般的分配器不是同一个分配器
特殊分配器：alloc会尽量减少底层malloc的次数//这样会减少额外开销，cookie记录着空间的大小，
对于容器，可以不需要cookie
alloc十六条链表，问这个分配器要内存，并且内存块大小调整到8的倍数也不是很理解，反正省空间，省空间的原理是减少了cookie的空间

G4.9

这容器不再用alloc分配器//没有特殊设计了
G2.9中的alloc仍在，换了个名字，想用的话也可以自己指定继续用

适配器

标准库定义了三个顺序容器适配器：stack、queue和priority_queue。
适配器(adaptor)是标准库中的一个通用概念。**容器、迭代器和函数都有适配器。**本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样。

一个容器适配器接受一种已有的容器类型，使其行为看起来像一种不同的类型。
底层不是拥有自己的数据结构的容器（stack，queue）
存在形式：

1641886434915

B改造某一个东西之后，为A，

用A的时候，大家只看到A，看不到B，实际做还是用B

A用B的功能咋用：1.继承；2.内含//这里适配器大部分都是采用了内含的方式

容器简介

容器之间联系联系

1641659570140

stack里有deque
priority中有vector
A怎样用B的方法：1.继承2.复合
下面有C++11特性
蓝色：容器本身的基础东西的大小

分类

序列式容器
关联式容器
常用的：数组，链表，树，栈，队列，集合，映射表
序列式容器/顺序容器
- 数组，C++11

容器（只有后头可以扩充自动增长）
- 队列（前后都可自动增长）
- list（双向链表）
- 单向链表 C++11

1.这些容器在添加或删除元素和非顺序访问元素都有不同的性能折中

2.除了array是固定大小的，其他容器都有自己的内存管理策略（增，删元素，扩缩容器大小…）。该策略会影响特定容器是否支持某些操作。

3.几乎可以保存任意类型的元素

关联式容器

set/multiset（大多数编译器都是红黑树/平衡树）
- map/multimap
- 查找很快
- 小型数据库
- 底层：红黑树，hash_table
查找很快

set和map的区别是键值对与否，mul和非mul的区别是是否含有重复的数据

不定序式容器
- 没定序的排列
额外补充哈希表

输入需要查找的目标

1641476563218

查找目标字符串

1641476695969

比较两个long是否相等

> 比较两个string是否相等

迭代器

基本介绍

迭代器是STL将数据容器和算法分开后连接的纽带，

(就当前所见例子而言，一般都是算法需要知道容器头尾迭代器+迭代器性质，然后利用迭代器对容器进行操作，如下方trait中的rotate函数具体例子分析)

也是泛型思维发展的必然结果。

泛型算法就是通过迭代器操作容器的，使得算法和容器本身分离开来。

迭代器模式：提供一种方式，可以依次访问一个聚合物（容器）中所有元素而不暴露聚合物内部的表达方式。

迭代器类似与智能指针，但是它一般不会对所指向的元素进行释放空间，因为迭代器只是在指针外面包裹一层外加一些操作。

迭代器最重要编码工作是完成一些操作符的重载，

这些重载都是针对指针类型的操作，例如，++，——，*，->等，不同类型的迭代器完成的功能都不相同，详解见下文。

迭代器定义的位置最好是在容器内，将定义的任务交给了容器的设计者，因为每一种容器都对应一种迭代器，而定义在内部也不会暴露容器的内部元素。

迭代器是泛化的指针，可以看下面的例子试图理解，这里的泛化指的是对于数据结构类型都为list，但是数据本身的结构是多种多样的

基本所有容器都有记录头和尾的迭代器（类似指针）

起始迭代器是指向第一个

但是结尾迭代器指向最后一个元素后面一个的位置

温馨提示

某些对vector对象的操作会使迭代器失效

迭代器支持的操作

类似指针

小细节：

1
2
3

(*it).empty()
    //等价于it->empty（）
    //不等价于*it.empyty

迭代器和操作符重载

这里可以看到，无论是什么迭代器，都需要重载下方的黑色部分，这里的黑色部分其实就是利用指针一般都会进行的行为，但是因为这里定义迭代器它就不仅仅只有指针的功能，还有一些其他特性，所以迭代器得对自身类似指针的那部分功能进行重载

迭代器类型

iterator和const_iterator

begin(),end(),cbegin(),cend()

常量容器返回只读迭代器

一般容器返回读写迭代器

常量返只读就用cbegin(),cend()

迭代器和trait

迭代器的trait型别主要有五种：value_type,catalog,reference,pointer,diffrence。

value_type迭代器所指对象类型，

catalog迭代器类型，//主要是指迭代器的移动性质

reference迭代器所指类型引用，

pointer迭代器所指类型指针，

diffrence用什么基本数据类型表示迭代器之间距离（如int类型）。

五个trait

value type

每个STL中的类都有value_type这种东西，

通俗的说value_type 就是stl容器盛装的数据的数据类型，

例如：

1
2
3

vector<int> vec;

vector<int>::value_type x;

上述两句代码，第一句是声明一个盛装数据类型是int的数据的vector，

第二句是使用vector::value_type定义一个变量x，这个变量x实际上是int类型的，因为vector::value_type中声明的为int型。相应的，假设有：

1
2
3

vector<C> vec;  //假设C是自定义类型

vector<C>::value_type x;

那么第二句定义的变量x的数据类型是C。

每个STL容器类（感觉应该是迭代器类更加准确），都有一句相同的代码：

typede T value_type;

其中T则是类模板中使用的参数：

template

以STL的list容器为例，那么它的类定义就应该有下面的语句:

template

class list{

publict:

typedef T value_type;

//……

};

上述写法，在《STL源码剖析》中称为“声明内嵌型别”技术。

template

T也可以是一个class，那么value_type也就是可以用来定义class的对象了。

迭代器所指对象的类型，原生指针也是一种迭代器，

**对于原生指针 int *，int 即为指针所指对象的类型 **，也就是所谓的 value_type 。

iterator_category

简单理解

不同的数据结构会有不同的类型的迭代器来对其进行操作。

有的迭代器只能往前走++，有的迭代器只能往后走–，有的迭代器能进行双向走（能++也能–。

有的迭代器可以修改容器所指东西内容，有的迭代器不可以。

不同迭代器有许多不同的特征。

而在迭代器类中，这个iterator_category就是为了告诉算法某些迭代器移动和读写特征信息的。

基本概念

iterator_category：的作用是标识迭代器的移动特性和可以对迭代器执行的操作，

从 iterator_category 上，可将迭代器分为 Input Iterator、Output Iterator、Forward Iterator、Bidirectional Iterator、Random Access Iterator 五类，这样分可以尽可能地提高效率。

左边讲述了iterator_category之间的继承关系

右边作为例子举例不同的iterator_category可能对应怎怎样不同的容器结构

单向，双向，随机，input,output

Input Iterator： 此迭代器不允许修改所指的对象，是只读的。支持 ==、!=、++、 *、-> 等操作。
Output Iterator：允许算法在这种迭代器所形成的区间上进行只写操作。支持 ++、 * 等操作。
Forward Iterator：允许算法在这种迭代器所形成的区间上进行读写操作，但只能单向移动，每次只能移动一步。支持 Input Iterator  和 Output Iterator 的所有操作。
Bidirectional Iterator：允许算法在这种迭代器所形成的区间上进行读写操作，可双向移动，每次只能移动一步。支持 Forward Iterator 的所有操作，并另外支持 –  操作。

Random Access Iterator：包含指针的所有操作，可进行随机访问，随意移动指定的步数。支持前面四种  Iterator  的所有操作，并另外支持 [n] 操作符等操作。

实例一

左下的最下面部分是老师设计的一个萃取机机制的入口

左下的上面部分对应的是回答

右边是测试代码和结果显示

尤为值得注意的是右下角的虚线部分的相应测试代码和输出（实例三）

实例二

左方是老师测试所用代码

写一个函数问并且显示迭代器的类型是什么？

typeid（itr）. name 理解上来说

比如这里，一般来说只应该出现Deque——iteratorl…之后的内容

前面的St15出现实现因为类的名称经过编译器编译后实际上确实会不一样

这个其实可以自己试一试

实例三

Input Iterator 萃取机制入口的传参不同版本设计

g2.9 g3.3 g4.9（看虚线引导）

不同标准库实现方法不同，接口相同（并且能兼容之前的接口）

注意在g4.9的设计中

实例四

output Iterator 萃取机制入口的传参不同版本设计

g2.9 g3.3 g4.9（看虚线引导）

迭代器类型对算法的影响//下面迭代器那里也有一个例子

1641833845378

这里的小方块说是写了一个函数来问迭代器类型，以便这个前进函数使用

虽然这里是只有三种迭代器类型，但是迭代器之间存在着继承关系，最终这五种类型一定都会拥有自己的调用

different_type

//两个迭代器的距离用什么来表现

//一个容器中两个迭代器的距离

//带符号类型，其数值可正可负

对于原生指针，STL 以 C++ 内建的 ptrdiff_t 作为原生指针的 difference_type。

迭代器类型对算法的影响

1641831292672

传入两个参数

1641831467540

连续的话可以直接相减

1641831481224

非连续的话只能一步步数，一步步算

reference type

是指迭代器所指对象的类型的引用，reference_type 一般用在迭代器的 * 运算符重载上，

如果 value_type 是 T，那么对应的 reference_type 就是 T&；

如果 value_type 是 const T，那么对应的reference_type 就是 const T&。

pointer_type

就是相应的指针类型，对于指针来说，最常用的功能就是 operator* 和 operator-> 两个运算符

迭代器trait的作用

只要迭代器内有定义，并且能够传进去，就算能够回答问题//虚线连接的部分

trait具体回答的机制

所有迭代器都需继承以下这个共同的模板

//迭代器模板
template <class Category, class T, class Distance = ptrdiff_t,  
          class Pointer = T*, class Reference = T&>  
          
struct iterator {  
  typedef Category  iterator_category;  
  typedef T         value_type;  
  typedef Distance  difference_type;  
  typedef Pointer   pointer;  
  typedef Reference reference;  
};

当具体开始写某一个迭代器时

当定义迭代器的时候，必须给定迭代器的特性。

STL为提取迭代器的特性，提供了一个模板类iterator_trait，适用于所有的迭代器和原生指针，定义如下

(要理解的话，就想想，当你拥有这个模板之后应当怎样使用这个模板来进行迭代器特征的定义)



template <class Iterator>  //看这里
struct iterator_traits  
{  
  // 迭代器类型, STL提供五种迭代器  
  typedef typename Iterator::iterator_category iterator_category;  
  
  // 迭代器所指对象的型别  
  // 如果想与STL算法兼容, 那么在类内需要提供value_type定义  
  typedef typename Iterator::value_type        value_type;  
  
  // 这个是用于处理两个迭代器间距离的类型  
  typedef typename Iterator::difference_type   difference_type;  
  
  // 直接指向对象的原生指针类型  
  typedef typename Iterator::pointer           pointer;  
  
  // 这个是对象的引用类型  
  typedef typename Iterator::reference         reference;  
};

这里的特化是偏特化：顾名思义，偏特化就是对部分进行了特化，全特化就是将全部进行特化。


// 针对指针提供特化版本  
template <class T>  
struct iterator_traits<T*>  
{  
  typedef random_access_iterator_tag iterator_category; //不理解 
  typedef T                          value_type;  //不理解
  typedef ptrdiff_t                  difference_type;  //ptrdiff_t是C/C++标准库中定义的一个与机器相关的数据类型。ptrdiff_t类型变量通常用来保存两个指针减法操作的结果。
  typedef T*                         pointer;  
  typedef T&                         reference;  
};  


  
// 针对指向常对象的指针提供特化  
template <class T>  
struct iterator_traits<const T*>  
{  
  typedef random_access_iterator_tag iterator_category;  //不理解
  typedef T                          value_type;  //不理解
  typedef ptrdiff_t                  difference_type;  //不理解
  typedef const T*                   pointer;  
  typedef const T&                   reference;  
}; 


//这里是上面正常版本，对比一下
template <class Iterator>  //看这里
struct iterator_traits  
{  
  typedef typename Iterator::iterator_category iterator_category;  
  typedef typename Iterator::value_type        value_type;  
  typedef typename Iterator::difference_type   difference_type;  
  typedef typename Iterator::pointer           pointer;  
  typedef typename Iterator::reference         reference;  
    
};

trait：迭代器中的基本特征特点

迭代器的trait：//迭代器需要遵循的桥梁

例子：rotate函数中迭代器传参分析

rotate函数想要迭代器移动的性质//iterator_category

右下角是完整的实例传参应用

左上角是rotate的函数定义以及所需传参和内部函数定义，

rotate里面的rotate需要右上角的函数_iterator_category返回迭代器的特征（在没有将对于的移动性质传进去的时候，自动将 _first放入函数进行分析）

至于2和3黑圆圈则是根据该实例的具体typename那里的传参来确定的

总结：迭代器得有回答算法的能力

迭代器得有回答算法的能力，在具体设计代码中，基本需要回答以下五种问题

只要迭代器内有定义，并且能够传进去，就算能够回答问题

//虚线连接的部分

虽然有两者基本不怎么会被用到pointer reference（这两个问题基本不会设置）

完整的trait基本回答能力的设计

即（包括萃取机偏特化一般指针）

先看下面再食用这个

其他trait

“萃取机”

迭代器内被定义如上五个问题答案，才能回答问题。

有的容器底部用普通指针，不能回答问题，怎么办？

但是我们又得用指针对容器进行操作

“萃取机“：分辨传进来究竟是指针还是迭代器，帮助不具备迭代器特征的指针回答问题

1641712378064

总结：核心知识点在于 模板参数推导机制+内嵌类型定义机制，为了能处理原生指针这种特殊的迭代器，引入了偏特化机制。traits 就像一台 “特性萃取机”，把迭代器放进去，就能榨取出迭代器的特性。

这种偏特化是针对可调用函数 func 的偏特化，想象一种极端情况，假如 func 有几百万行代码，那么如果不这样做的话，就会造成非常大的代码污染。同时增加了代码冗余。

具体例子分析

在没有设计萃取机机制前，算法如何问

设计萃取机机制后

算法想知道五种类型（最下方），

就会来问萃取机（iterator_trait）,

传参们从萃取机入口进入（最上方1）

通过传参的类型j进入不同的偏特化模板（2 3）

如果不是正常的迭代器，而是一般指针进来由偏特化里面的内容来回答问题

上例为什么value type是T而不是const T

1641712790470

通过偏特化添加一层中间转换的 traits 模板 class，能实现对原生指针和迭代器的支持，有的读者可能会继续追问：对于指向常数对象的指针又该怎么处理呢？比如下面的例子：

const 变量只能初始化，而不能赋值（这两个概念必须区分清楚）。这将带来下面的问题：

那该如何是好呢？答案还是偏特化，来看实现：

完整的萃取机制


template<typename Category,
         typename T,
         typename Distance = ptrdiff_t,
         typename Pointer = T*,
         typename Reference = T&>
struct iterator //迭代器的定义
{
    typedef Category iterator_category;
    typedef T value_type;
    typedef Distance difference_type;
    typedef Pointer pointer;
    typedef Reference reference;
};
-----------------------------------
【STL 源码剖析】浅谈 STL 迭代器与 traits 编程技法
https://blog.51cto.com/u_15098004/2611939

tempalte<typename I>
struct iterator_traits {//特性萃取机，萃取迭代器特性
    typedef typename I::iterator_category iterator_category;
    typedef typename I::value_type value_type;
    typedef typeanme I:difference_type difference_type;
    typedef typename I::pointer pointer;
    typedef typename I::reference reference;
};

//需要对型别为指针和 const 指针设计特化版本看
//更具体例子看下方图片

!这里部分的视频有待总结和回看

1641834259303

copy通过不断检查迭代器的类型？，来选择更快更合适的copy方法

1641834489578

先检查迭代器的类型

1641834543170

上面那个是一般的方式，下面那两个能传入进去的是指针

1641834614793

这里又再问有没有这种迭代器，如果有又可以使用更快的方法

1641834835438

如果是上面的拷贝赋值不重要的话，就调用memmove

如果拷贝赋值重要的话，调用最下面的黄色方框

什么叫拷贝赋值重要？什么叫不重要？

比如虚数，的拷贝赋值不用设计，所以这种的拷贝赋值不重要不理解

迭代器类型影响的例子：destroy

1641835389918

迭代器类型影响的例子：unique_copy

功能：复制独一无二的懂细

右侧版本是针对右侧紫色部分迭代器类型的版本

左侧版本是针对左侧紫色部分迭代器类型的版本

两者的功能不同

这里模板种T的位置，虽然是说算法接收all类型的东西，但是T这里已经给了，算法能接收什么迭代器已经给暗示

具体容器介绍

遍历的三种方法
容器里的容器
自定义类型容器（指针的理解和代码形式上的表现）
用的时候要确保容器是否空，明确迭代器现在在哪，执行之后长度会不会改变

array

温馨提示

数组可以获得最后一个容器位置之后的那个位置
使用数组作为一个auto的变量的初始值时，推断得到的类型是指针而不是数组，用decltype的时候，这种情况不会发生（为啥去decltype看）
用auto或者decltype代替指针类型声明
类型别名化简多维数组指针

string和char*的混用

string转char*：c_str函数

char*转string：直接转，string可以兼容

数组相关声明的理解
- 元素为指针的数组
- 数组的指针
- 数组的引用
理解记忆：

首先，存在 * 号的声明不要看* 靠近哪个就认为星号赋予名字意义

第二遵循从左到右的原则比如，第一个例子 int 和 * 号结合获得意义

第三如果有小括号 括号大于从左到右的优先级 括号内的空间首先结合获得意义

底层

数组大小不能随意改变
维度必须是常量表达式
封装成容器的原因：使其像个容器，符合容器规则，能够使用容器的相关算法

源代码//98-11的过度版本

没有构造函数，没有析构函数
迭代器为普通指针//萃取剂走偏特化的路

G4.9

1641749756726

1641749658681

最根本类型

声明

长度必为常量

指针

指针可以+1 +2 来进行移动
小心指针越界
指针相加减的结果类型是ptrdiff_t
指向不同对象的指针不能相互比较

基本操作

1.数组没有拷贝和直接等号赋值

2.下标访问和修改（其实每个容器的下标运算符都不太一样，专属于容器）

3…初始化

tip:

维度必须已知

字符串赋值别忘记‘/0’的空间要给够

data的话是输出起始位置

1641484772996

string

温馨提示

string+运算允许C风格字符数组作为其中一个进行
利用for改变字符用引用

string相加时要注意：
1
string s4 =s1 +",";√
一条表达式中有size（），不要再使用int，因为size（）返回的是…
小妙用**（？）**
读取未知数量的string对象

#include<iostream>	
#include<string>	
using namespace std;
int main(){
	string word;
    while(cin >> word && word!=#)
    //输入#时可以结束
    //输入操作符返回输入流对象，如果输入流对象处于有效状态，表示没有遇到文件结束或非法输入(Ctrl+z)
    cout << word << endl;	
}

(3)使用getline()函数

目的：得到输入时候的空白符

①两个参数：输入流对象和存放读入字符串的string对象

②从指定输入流中读取内容，遇到换行符（回车）为止；（）

将所读内容存入指定的string对象中，流中的换行符虽然被读取到流中但在string被丢弃

③返回参数输入流对象

getline（）会返回它的流参数

#include<iostream>	
#include<string>	
using namespace std;
int main(){
	string line;
    while(getline(cin, line))
    cout << line << endl;	
}

size_type类型

1.size()函数返回的并不是int类型数据，而是size_type类型的数据

2.它是一个无符号类型的值足够放下任何string对象的大小

3.所有存放string类的size函数返回值的变量都应该是size_type

4.auto可以推断出来

基本内容

相关头文件

1 2	#include<string> using std::string

本质：里面封装char，实质是个容器/类*

可进行操作：

1.初始化

拷贝初始化（s3 = “ a”）和直接初始化（s3（“a”））之分

2.增（+和append，insert）看看下面

3.删（erase）

4.改

5.查

6.拷贝（直接拷贝，切片substr左闭右开）

关于加法：

但是不能够两个字面值直接相加，如下

7.处理单个字符的函数

vector

自己设计的话必须得考虑vector得兼容deque的操作
兼容stack的设计
不兼容queue的设计
元素为vector的声明

1 2	vector<vertor<int> > √ 老版 vector<vertor<int>> √ × 不一定对

小心下标操作和空容器之间的矛盾
范围for语句体内不应该改变其所遍历序列大小
size_type的使用

1661821937060

底层

基本存储结构

1641748235474

push-back的实现：

1641748573429

小心容器为0时候的处理
原来的空间记得删除，在拓展之后
拷贝安插点后面的内容，容易漏//insert

迭代器分析

底层的迭代器为普通的指针

G4.9

1641748906781

这里的public的继承设计有一些不很合理//这里这个继承只是为了让下面用上面父类的功能

萃取器过程

1641749157906

反正这里这个版本把迭代器搞成了一个对象，这个对象本身的trait特征仍然是普通指针，但是也可以做容器的这一个迭代器，之前的G2.9就是一个偏特化的处理就解决了

特点

动态拓展数组（原理：找新地方拷贝在放新东西，旧空间释放）
支持随机访问
动态拓展空间是两倍增长的
好像有find不能用来着，会破坏其独特性stack，queue同理

初始化

容器大小可以指定，库会自动创建初始值
- 基本数据类型，库已经设置好
- 自定义数据类型，根据类默认初始化
  
  （如果类没有默认初始化值，那么就得明确提供初始值）

构造

1661737366842

v4理解容易出错，传参是元素数量哦

1661737454096


push_back

vector<int>v2(v1.begin(),v1.end());

vector<int>v3(10,100);

vector<int>v4(v3);

查找

1641485877380

赋值=

vector<int>v2;
v2=v1;

#assign
vector<int>v3;
v3.assign(v1.begin(),v1.end())；

v4.assign(10,100)#10个100

vector容量和大小

vector(int)v1;
v1.empty();//为空返回1
capacity();//容器容量
size();//元素个数
v1.resize(15);//重新容器大小，扩大型，默认用0填充新位置
v1.resize(15，100);//重载用100填充

插入和删除

push_back();
pop_back();//尾删
erase(迭代器位置);
erase(迭代器位置,迭代器位置);
insert(迭代器位置，n个数据，数据内容);
push_back();
clear();

1661821592357

1661821604989

1661821751697

这个真的有点怪

数据存取

//v1[n]   返回v1第n个位置上元素的引用
cout<<v1[1]<<endl;

cout<<v1.at(1)<<;

cout<<v1.front();

cout<<v1.back();

互换容器

v1.swap(v2);
##长度不一样可以交换吗(可以，因为swap交换的是指针)


# 1.题目：求众数

封装 继承 多态

应用

1	vector<int>v.swap（v）;//收缩内存

排序

class MyCompare
{
public:
	bool operator()(int num1, int num2)
	{
		return num1 > num2;
	}
};
void test01()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(40);
	v.push_back(20);
	v.push_back(30);
	v.push_back(50);
	//默认从小到大
	sort(v.begin(), v.end());
	//使用函数对象改变算法策略，排序从大到小
	sort(v.begin(), v.end(), MyCompare());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	test01();
	system("pause");
	return 0;
}

使用的问题

当我在使用容器时能否显示里面某个量的地址。（可以的）

//无法实现这种形式的赋值

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

int main()
{
	string x;

	char c[5];

	c[0] = 'l';
	c[1] = 'l';
	c[2] = 'l';
	c[3] = 'l';
	c[4] = 'l';

	x = c;

	cout << c << "                  " << x[0]<<"                       "<<x;

	return 0;
}

stack

能否判断容器是否为空？可以。为什么呢？为什么呢？
能否可以返回元素个数吗？可以。为什么呢？
先进后出
不提供迭代器

底层

也可以选择list和vector作为底层，不可以选set和map

接口

这里是push

deque

特点

两头可以扩充
一个buffer一个buffer地扩充
其实是假连续。并不是元素的存放地址都相连

底层

存有缓冲区指针的vector

迭代器分析

node：控制中心/vector

cur：迭代器现在指向的元素
源代码//老版本

1641794060898

这里的buffer缓冲区可以为0//新版本不可以

最本质理解

1641794171056

deque最本质有40个字节

insert

插入需要腾出空间，移动前面元素还是后面元素是个问题，inset内部需要完成这个功能。

为头部和尾部的情况

1641794618464

一般情况

模拟连续空间

这里对迭代器进行了操作符重载//上图左下

//下面这张图是具体实现

1641795489803

这里值得自己细推一下

1641795630232

++:

++之后是否到达边界

到边界之后：

没到边界：

–:

–之前在不在容器的起点

在边界上的起点上，就会退回控制中心并且返回前一个node给他，并且cur=前一个的最末端

这里前和后的设计很经典,–同理

1641795967832

一下子移动多个空间如何设//+=的设计

cur加之后有没有超出当前缓冲区

已跨：到了正确的缓冲区再计算跨几个

未跨：直接跨

-=同理设计，照抄+=

G4.9

左边黑框算迭代器存储结构大小

1641796502146

好：没有必要这样

坏：专业者更快无法调整buffer

vector/控制中心扩充之后，原来的char*数据到新的区域的中段

queue

底层：deque，并且只有一部分deque的功能
queue是适配器：把别人改装一下，成自己的功能
底层也可以用list实现，不可以用vector实现，不可以选set和map

特点

队尾进数据
双向开口
不允许遍历
先进先出
不提供迭代器

使用

遍历的实现

while (!q.empty()) {
		cout << q.front() << " ";
		q.pop();
	}

max_size（）
只能用全局sort，自己没有sort

priority_queue

具有优先级的队列

forward_list

相关函数

1641648615931

1641648634155

slist

相关库ext

特点

单向串
stdexcept

相关函数

list

迭代器分析

基本构成：五个typeof+一堆的重载
区分i和i的重载

前++：

1641661369322

后++：

1641661438421

1641661597298

第一点的部分：= *两个重载的一个分析的大动作
两个++的返回类型不一样，因为学习整数的规定

1641661840705

阻止做第二行的操作返回自身，做第一行的动作返回自身的引用一个大不理解的状态

*的重载：取值
->的重载
G2.9/G4.9的迭代器定义比较

1641663351654

链表特点

链表的储存是非连续的，而动态数组的储存是连续的
链表由节点构成
节点由数据域和指针域构成的
一个一个扩充
G2.91/G4.91的链表的存储结构有一些不一样

链表的优点：快速删除和插入元素
链表的缺点：占用空间大，容器的遍历速度慢
链表实际上是环状双向
两个版本的list存储结构的定义和大小的区别

1641664032470

1641663939630

伪元素的实现

1641663628558

list特点

双向循环：循环指的是最后一个链表的尾指针指向第一个链表的位置
迭代器支持++（双向迭代器）

其他

在STL中，像vector、list、string这些容器都含有**max_size()**这个函数，想请教一下，关于这个max_size()函数的值。在我机子上vector的max_size（）=1073741823，list的max_size（）=357913941，而string的max_size（）=4294967294。。。请问这些值是固定的吗？？为什么要设为这么大的值？？是由电脑的配置决定的吗？？？

4294967294是2^32，也就是用一个int表示长度，能表示的最大值。1073741823是上一个值的1/4，如果有什么原因它需要的存储是前者的4倍的话，那么最大值就是1/4。这个应该是C++编译器/标准库规范/操作系统决定的，不是电脑配置决定的。

所有容器的指针都必须得是一个类，才能完成这个智能指针//迭代器的一个动作，在++的时候，自动指向下一个

构造

赋值

交换

大小操作

插入删除

数据存取

不能使用at&[]，因为空间不是连续的
迭代器不支持随机访问，只能前后移

反转和排序

反转用reverse
从小到大排序
从大到小的话，可以传入一个布尔函数来说明自己排序的顺序

sort是成员函数不是全局函数

unordered_multiset

底层都是hash_table
大量数据查找适合这玩意儿
backet比元素多很正常
底层：backet不会太长，元素个数超过backet的话，

backet会进行扩充

怎么还有数backet，数装载因子啊
使用方法

1641650539920

1641650897450

unordered_set

调用

这里是4.9版，不遵循上面的素数规则，从篮子的数量可以观察得出

1641828614830

不管篮子个数的设定和拓展规则（比如一定是素数）是怎么样的，篮子的个数肯定大于总结点的个数

multiset

底层：红黑树
有规则地形成结果，数据有规律地插入，但插入会慢一点
全局find和自己拥有find
查找速度极快/自己的find
可以放重复放

set/multiset

set底层

1641801030469

源代码：

1641801059873

1641801149057

每一个的传参

less是模板，允许你指定你要比什么东西，怎么写//后面再讲

set里面拿到的红黑树的迭代器是const的，防止使用者改变
格鲁C提供identity，vc不提供

VC6的版本源代码

特点

一般用set头文件
可以遍历
set是容器适配器
自己有find可以使用//自己的这个真的很快
这里的key和value的理解要和map里面的区分

赋值和构造

#插入值
insert

#拷贝构造

大小和交换

插入和删除

						set


insert						√
size						√
empty						√
swap						√
erase（可重载为remove）						√
clear						√
find						√
count（参数和remove一样）						√

查找和统计

set和multiset区别

底层有一个pair

pair

使用不需要头文件

创建

获取

map/multimap

特点：

map

1641802019941

1、map是关联式容器，它按照key值比较存储，默认是小于；

2、在map中，

键值key通常用于唯一的标识元素，而值value中存储与此键值key关联的内容；

键值key和value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名为pair；

3、map中的元素是键值对；

4、map中的key是唯一的，并且不能修改，遇到重复的key就会插入失败；但可以利用operator[]对value进行修改；

5、map的底层实现为红黑树，查找效率比较高，是O(logN);
原文链接：https://blog.csdn.net/yam_sunshine/article/details/89930311

6.Map是键值对，Set是值的集合，当然键和值可以是任何的值；

multimap

multimap和map的功能类似，就不一一介绍了，下面主要说一下这两者的不同：

1、multimap中的key可以重复

2、multimap中没有重载operator[ ]功能

3、对于重复的元素，查找的时候也是返回中序遍历的第一个元素，小不理解

原文链接：https://blog.csdn.net/yam_sunshine/article/details/89930311

multimap底层

底层：红黑树
元素可以重复
不可以直接取元素
data不一定只是一个数据，可能是数据集
使用方法：

1641802746849

测试结果

1641802679216

1641802853309

map底层

底部红黑树
键值对
唯一的，不重复
这玩意还会自己成键值对
key没重复
key禁止改
value重复不算重复

，1641651144372

1641802145765

map独有的中括号

1641802921569

key存在，可以通过中括号直接取值，key不存在，可以通过中括号建立并放入map

1641803215866

找得到的时候，直接返回一个迭代器位置

找不到时候，lowerbond返回一个最合适安插的位置的返回

源代码：

一个map和它里面的红黑树

1641802260043

一堆里面拿出第一个，拿出key

是这个编译器独有的

1641802368000

这个pair的key不能够被改变//之前set的不改变是利用const迭代器实现的，这里不一样

与其他版本比较

1641802505427

底层还有pair

复制和构造

大小交换插入删除

拷贝	√
赋值	√
交换	√	swap
判断为空	√	empty
获得数目（大小	√	size
插入	√	insert
		make_pair(2,20)
删除	√	erase
清空	√	clear

不同大小的map容器互换，容量小的将会损失数据
如果插入的数据在map中已经存在，则不会插入，不能用insert完成覆盖更新！切记！！！！

第四种不用的原因：不存在的数会自动给value赋值为0

查找统计

key不可以重复，那么value可以重复吗？可以
count（key）的话就是说搜索相同key的个数（map中只有0或1）

排序

class mylist
{
    public operator()(int v1,intv 2)
    {
        return v1 < v2;
    }
}

map<int,int,mylist>   #mylist自定义排序

旧版本的数据结构

也可以用，就是用的时候需要特别注意

1641651295193

算法

质变算法（对数据进行改变）
非质变算法（不改）

1641653055995

复习标准库六个部分整体关系

1641829528383

迭代器是STL将数据容器和算法分开后连接的纽带，

语言层面容器迭代器算法的关联

迭代器和算法的关系单独成章

迭代器与算法/！！！！

实例一

1658406764432

右下角distance函数（入口）：计算连续空间容器的距离，利用两个指针

方案一（非连续空间计算个数）：数数

方案二（连续空间计算个数）：尾指针减去头指针

为什么入口函数的返回类型不直接写为int（反正都是数个数）

其实我感觉很奇怪，怎么说返回的都得是(last-first)*difference_type吧，

难道对于指针的加减运算已经进行过重载了吗

总结：这个例子以distance的入口（包含主函数入口和次函数入口）

和两个次函数偏特化版本入手，显示迭代器中两种trait的具体使用（红色部分）

其实我不理解，直接像偏特化那样子写不可吗，为啥还要分主次函数来写，

主函数接口之间写三个传参不行吗

为啥只有两种？而不是有刚才显示的五种迭代器类型的不同偏特化版本

因为左下方的继承关系的存在，使得f is a input and ram is a bid

子类可以通过父类接口来调用函数

这样也是为什么用struct对象代替数字的trait的tag的存在形式的原因之一（？）

这有效减少了代码复用（?）