大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

前言

stl版本 abcd，四个版本，

接口肯定是一样的

代码复用性强，效率高，通用性高，vector deque

他有六个组件，空间配置器，容器，迭代器，算法，仿函数，容器适配器

容器和算法中间，靠迭代器连接

算法为了通用性，有辅助的东西，让算法通用，也就是使用仿函数

仿函数就是一个对象

容器通过适配器，可以相连，变成其他的容器

空间适配器，分配各个的内存空间~

在此之外有，特性萃取机制，为了效率，采取一系列操作

序列式

list，vector deque

关联式

set map multset multmap hashset hashmap

容器适配器

stack queue

List

双向链表

头节点不计入

size不包含头节点，也就是4

你可以通过1 找到2，

开辟出来都是0

begin，end

#include<iostream>
#include<list>

using namespace std;
int main() {
	//list <int> mylist(10);

	int ar[10] = { 1,2,3,4,5,6,7,8,9,10 };
	list<int> mylist(ar, ar + 10);
	return 0;
}

Vector 函数

向量，也就相当于动态数组

链表不是连续的

last 放入元素的下一个，

first 第一个

end 空间结束的下一个

end-first 是 size

last-first 是 有多少个空间

end-last 还剩多少空间

#include<iostream>
#include<vector>

using namespace std;
int main() {
	vector<int> v;
	cout << v.capacity() << endl;
	v.push_back(1);
	cout << v.capacity() << endl;
}

查看容量

vector为什么没有push_front 不是技术无法实现，而是为了效率

超出size的push_back ,他会开辟一个比之前还要大的空间，依次把数值放进去

他造完，然后，会把first，lat，end放过来。

push_front,他一个一个往后移，消耗很大

vector类似于数组，数组给他赋值，没啥问题

#include<iostream>
#include<vector>

using namespace std;
int main() {
	int ar[] = { 1,2,3,4,5,6,7,8 };
	vector<int> v(ar, ar + 8);


	//两种遍历方式
	for (auto i = 0; i < v.size(); ++i) {
		cout << v[i] << "";//相当于 v.operator[](i) 相当于重载
		cout << v.at(i) << "";
	}
	cout << endl;

	vector<int>::iterator it = v.begin();
	while (it != v.end()) {
		cout << *it << endl;
		++it;
	}
	
	//反向迭代器
		vector<int>::reverse_iterator it = v.rbegin();
	while (it != v.rend()) {
		cout << *it << endl;
		++it;
	}
}

deque

双端队列，和vector 类似，支持随机访问，快速插入删除

vector 不支持从头插入删除，

deque可以进行头部的操作

list没有容量这一说

想往哪儿插往哪儿插

中间这一个竖线，都有很多的讲究

竖线叫中控器，很麻烦

默认构造

#include<iostream>
#include<deque>

using namespace std;
void main() {
	//deque<int>



	deque<int> d(10, 1);
	deque<int>::iterator it = d.begin();
	while (it != d.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

#include<iostream>
#include<deque>

using namespace std;
void main() {
	//deque<int>
	deque<int> d;
	d.push_back(1);
	d.push_back(2);
	d.push_front(3);
	d.push_front(4);//pop_front,pop_back,d.back()


	///deque<int> d(10, 1);
	deque<int>::iterator it = d.begin();
	while (it != d.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

resize(10) 他变大，会填充0

我们在d.begin前面插入

插入方法放在迭代器前面

string

#include<iostream>
#include<string>

using namespace std;
void main() {
	string str = "hello";
	cout << "str = "<<str << endl;

}

有容器，当然肯定有迭代器，

iterator

#include<iostream>
#include<string>

using namespace std;
void main() {
	string str = "hello";
	cout << "str = "<<str << endl;

	string::iterator it = str.begin();
	while (it != str.end()) {
		cout << *it;
		++it;
	}
	cout << endl;
}

反向

#include<iostream>
#include<string>

using namespace std;
void main() {
	string str = "hello";
	cout << "str = "<<str << endl;

	string::iterator it = str.begin();
	while (it != str.end()) {
		cout << *it;
		++it;
	}
	cout << endl;

	string::reverse_iterator rit = str.rbegin();
	while (rit != str.rend()) {
		cout << *rit;
		++rit;
	}
}

他还有size，length，capacity

大小，长度， 容量

size和length差不多，

为什么容量不一样

因为他会的增长对吧，扩增，避免满了，

多开辟，未必会使用完

resize（20） 会填充/0 ，然后capacity 会加上原来的大小，变大，

str.reserve(20) 容积加了20，里面东西没变只有capacity变了

指针和 数组的区别，

数组可以修改，指针不能修改

很多函数，对吧，替换之类的，

替换，对吧，

stack queue

queue 受操作限制的线性结构，

deque可以适配成为queue或者stack嘛?

deque 通过适配，改为栈，队列

栈：先进后出，

只让头插，头删

或者

只让尾插，尾删

队列，先进先出

只进行尾插，只进行头删，就构成了队列

#include<iostream>
#include<stack>

using namespace std;
void main() {
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	int value;
	cout << "size : " << st.size() << endl; 
	while (!st.empty()) {
		value = st.top();
		cout << " 删除 " << value << endl;
		st.pop();
	}


}

queue

#include<iostream>
#include<queue>

using namespace std;
void main() {
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);

	cout << q.size() << endl;
}

先进先出

#include<iostream>
#include<queue>

using namespace std;
int main() {
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	int value1;
	while (!q.empty()) {
		value1 = q.front();
		cout << "删除" << value1 << endl;
		q.pop();
	}
	return 0;
}

front 是为了返回第一个数值

bitset

每一个元素只能是0和1

他叫位图

#include<iostream>
#include<bitset>

using namespace std;
int main() {
	bitset<10> bt;
	cout << bt << endl;
	cout << size(bt) << endl;
	cout << sizeof(bt) << endl;
	cout << bt.count() << endl;
	
	return 0;
}

size是10 10个大小，

都是0

sizeof是对象占用内存字节数

sizeof 占用4个，

size就是位数

bt.count 是为了查找里面有几个1

关联式容器 set multiset

注重，快速，高效检索

set multiset map multimap

这些set map是一个红黑树，动态平衡树

rbtree 动态平衡树

二叉排序树

set map

如何查询，（也就是排序）

#include<iostream>
#include<set>

using namespace std;
int main() {
	int ar[] = { 12,45,414,66,23,65,87 };
	set<int> s;
	for (int i = 0; i < sizeof(ar) / sizeof(int); ++i) {
		s.insert(ar[i]);
	}
	set<int>::iterator it = s.begin();
	while (it != s.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;
	return 0;
}

很明显，他放进来顺序不一样哟

之前，给什么顺序，放什么顺序，而，

set里面放进去默认排好序了

count 查看有12 ，只有一个

如果是其他查看的话，就能超过1了

集合同时，不可以重复，自带去重

我们来看一下，查找

这个，可以重载小于号

multiset

可以重复

#include<iostream>
#include<set>

using namespace std;
int main() {
	int ar[] = { 12,12,12,45,414,66,23,65,87 };
	multiset<int> s;
	for (int i = 0; i < sizeof(ar) / sizeof(int); ++i) {
		s.insert(ar[i]);
	}
	multiset<int>::iterator it = s.begin();
	while (it != s.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;

	cout << "count = " << s.count(12) << endl;

	return 0;
}

算法库

stl目的，为了提高复用性

容器—-迭代器—》算法

非变异算法，和变异算法

3 434 1231 55 11 23

顺序不变，就是非变异算法，for each，find,count

顺序改变，就是变异算法，

仿函数

仿函数就是函数对象代替函数指针

operator()

函数指针不能作为内联函数，函数对象可以，所以使用函数对象比较快

一个参数一元仿函数，两个函数二元仿函数

operator()(a,b)

#include<iostream>
#include<functional>

using namespace std;
int Sum(int a, int b) {
	return a + b;

}

void main(void) {
	cout << Sum(10, 20) << endl;
	plus<int>ps;//不能直接建立，需要先创建ps
	cout << ps(10, 20) << endl;
	//ps叫仿函数

}

他重载了括号，变成了二元

它调用了 ()

ps.operator()(10,20)

minus

multipiles

乘法

仿函数如何结合算法呢？

先打印出来

vector有一个排序方法

默认从小到大排序

从大到小，只要增加一个仿函数

#include<iostream>
#include<functional>
#include<vector>
#include<algorithm>

using namespace std;
int Sum(int a, int b) {
	return a + b;

}

void main(void) {
	int ar[4] = { 3,5,1,2 };
	vector<int> v(ar, ar + 4);
	sort(v.begin(),v.end(),greater<int>());
	vector<int>::iterator it = v.begin();
	while (it != v.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

自己实现一个仿函数

正常排序

s我们上面使用模板

添加模板类

下面我们使用迭代器，

#include<iostream>
#include<functional>
#include<vector>
#include<algorithm>

using namespace std;


template<class T>
void Swap(T &a, T &b) {
	T tmp = a;
	a = b;
	b = tmp;
}
void my_sort(int ar[], int n) {
	for (int i = 0; i < n - 1; ++i) {
		for (int j = 0; j < n - i - 1; ++j) {
			if (ar[j] > ar[j + 1]) {
				Swap(ar[j], ar[j + 1]);
			}
		}
	}
}


//仿函数
struct my_greater
{
	bool operator()(int a, int b) {
		return a > b;
	}
};

void my_sort2(int *first, int *last,my_greater _pr) {
	for (;first!=last;--last) {
		int *tmp = first;
		for (; tmp != last-1;tmp++) {
			if (_pr(*tmp,*(tmp+1))) {
				Swap(*tmp, *(tmp + 1));
			}
		}
	}
}



void main(void) {
	int ar[4] = { 3,5,1,2 };
	//my_sort(ar, 4);
	my_sort2(ar, ar + 4,my_greater());
	for (int i = 0; i < 4; ++i) {
		cout << ar[i] << endl;
	}
	
}

list.h

这个list没有添加任何的空间适配器，由malloc分配而成

#pragma once
#include<assert.h>
template<class _T>
class list {//完全是空的class，没啥问题
//加下划线，为了内部使用
//typedef _Node _Nodeptr
public:
struct _Node;
typedef _Node* _Nodeptr;
struct _Node {
_T _Value;
_Nodeptr _Next, _Prev;
};
struct _Acc {//acc专门返回前驱，后继，节点值
typedef _Nodeptr& _Nodepref;
typedef _T& _Vref;
static _Nodepref _Next(_Nodeptr _P) {
return ((_Nodepref)(*_P)._Next);//_p->_next
}
static _Nodepref _Prev(_Nodeptr _P) {
return ((_Nodepref)(*_P)._Prev);//_p->_Prev
}
static _Vref _Value(_Nodeptr _P) {
return ((_Vref)(*_P)._Value);//_p->_Value
}
};
//方便萃取，经常用到的几个类型
typedef size_t             size_type;
typedef _T                value_type;
typedef _T*            pointer_type;
typedef const _T*   const_pointer_type;
typedef _T&                reference;
typedef const _T&   const_reference;//引用，相当于别名，对引用的操作和原来变量的此操作完全一致
typedef int difference_type;//距离类型
//迭代器
class itrator;//普通迭代器
class const_iterator;//const类型迭代器
class const_iterator {
//迭代器用途就是，比较是否相同，如何加加，如何减少，如何取值
public:
const_iterator() {//构造函数
}
//有一个参数的构造函数
const_iterator(_Nodeptr _P):_Ptr(_P) {
}
//拷贝构造函数,
//!!!!!!! 一定要注意，这里是const
const_iterator(const const_iterator & _X) :_Ptr(_X._Ptr) {//参数值访问类内使用点
}
const_reference operator *()const {//完成星号的重载操作符
return _Acc::_Value(_Ptr);
}
//运算符重载相当于：
//https:\//blog.csdn.net/naibozhuan3744/article/details/93532268
//classA+classB==classA.operator+(classB);
const_iterator operator++() {//前加加，喜欢前加加
//先加后调用
_Ptr = _Acc::_Next(_Ptr);
return *this;
}
const_iterator operator++(int) {//后加加，里面加上参数
const_iterator _tmp = *this;//需要返回tmp出来
++* this;//先调用，后加
return _tmp;
}
const_iterator operator--()//前置减减
{
_Ptr = _Acc::_Prev(_Ptr);
return *this;
}
const_iterator operator--(int)//后置减减
{
const_iterator _Tmp = *this;
--*this;
return *_Tmp;
}
//通过重写等号，来判断是否两个迭代器相同
bool operator==(const const_iterator & _X)const {
return _Ptr == _X._Ptr;
}
bool operator!=(const const_iterator & _X)const {
return !(*this == _X);//利用重写的==，加一个感叹号即可
}
_Nodeptr _Mynode()const {//为了返回ptr
return _Ptr;
}
protected:
_Nodeptr _Ptr;//属性
};
public://构造函数
class iterator :public const_iterator//普通迭代器继承自常迭代器，我们使用公有继承，公有继承可以直接使用继承的属性，以及函数
{
public:
iterator() {//普通的构造方法
}
iterator(_Nodeptr _P):const_iterator(_P) {//一个参数的构造方法
}
reference operator*()const {
return _Acc::_Value(_Ptr);
}
iterator operator++() {//前加加，喜欢前加加
_Ptr = _Acc::_Next(_Ptr);
return *this;
}
iterator operator++(int) {//后加加，里面加上参数
iterator _tmp = *this;//需要返回tmp出来
++* this;
return _tmp;
}
iterator operator--()//前置减减
{
_Ptr = _Acc::_Prev(_Ptr);
return *this;
}
iterator operator--(int)//后置减减
{
iterator _Tmp = *this;
--*this;
return *_Tmp;
}
bool operator==(const iterator& _X)const {
return _Ptr == _X._Ptr;
}
bool operator!=(const iterator& _X)const {
return !(*this == _X);
}
protected:
_Nodeptr _Ptr;
};
explicit list() :_Head(_Buynode()),_Size()//显式转换
//类构造函数初始化列表
//构造函数初始化列表以一个冒号开始，接着是以逗号分隔的数据成员列表，每个数据成员后面跟一个放在括号中的初始化式。例如：
//显式转换隐式转换https://www.cnblogs.com/lijiaxin/p/10659157.html
{
}
//数值大小的构造
explicit list(size_type _N, const _T& _V = _T()) :_Head(_Buynode()), _Size(0) {
insert(begin(), _N, _V);
}
//区间的构造
list(const _T* _F, const _T* L) :_Head(_Buynode()), _Size(0) {
insert(begin(), _F, L);
}      
size_type size()const {
return _Size;
}
bool empty() const {
return (size == 0);
}
//返回头节点指针，地址
reference front() {
return *begin();
}
reference back() {
return *--end();//--已经重写过了
}
const_iterator begin()const//先写一下begin，定义为常函数
{
return const_iterator(_Acc::_Next(_Head));//返回的是一个构造函数，他会构造一个类，所以我们之前的声明也需要是类名
}
iterator begin() {
return iterator(_Acc::_Next(_Head));
}
iterator end() {
return iterator(_Head);
}
const_iterator end() const
{
return const_iterator(_Head);
}
//尾插
void push_back(const _T &v) {
_Nodeptr _s = _Buynode(_Head,_Acc::_Prev(_Head));//直接调用方法，开辟节点
_Acc::_Vref(_s) = v;
//_s->_Value = v;
//_s->_Next = _Head;//新节点的下一个指向头节点（双向循环么）
//_s->_Prev = _Head->_Prev;//（新节点的前驱指向，头节点的前驱）
//_Head->_Prev->_Next = _s;
//_Head->_Prev = _s;
//以上版本也可以，但是他们喜欢你高端版本
_Acc::_Next(_Acc::_Prev(_s)) = _s;
_Acc::_Prev(_Head) = _s;
_Size++;
}
//头插
void push_front(const _T & v) {
insert(begin(), v);//头插
}
//尾删
void pop_back() {
erase(--end());
//end返回的是最后的下一个元素，所以要减减
}
//头删
void pop_front() {
erase(begin());
}
void clear() {
erase(begin(), end());
}
//赋值
void assign(size_type _N,const _T& _X = _T()) {
erase(begin(), end());
insert(begin(), _N, _X);
}
//我们写插入方法
public:
//给出位置，插入类型，插入，
/*
iterator insert(iterator _P, const _T& _X = _T())//和int a = int() 类似也就是 int *a = new int();
{
_Nodeptr _Ptr = _P._Mynode();//迭代器中mynode函数，表明节点的指向_Ptr指向了新加的上一个，也就是当前位置
_Nodeptr _S = _Buynode(_Ptr,_Acc::_Prev(_Ptr));//申请节点,s的后继,第一个后继，第二个前驱，s的前驱就是ptr的前驱
//到这儿只连了两根线，还有两根线
_Acc::_Prev(_Ptr) = _S;
_Acc::_Next(_Acc::_Prev(_S)) = _S;
//赋值
_Acc::_Value(_X);
//这里的赋值不安全
_Size++;
return iterator(_S);
}*/
iterator insert(iterator _P, const _T& _X = _T()) {
_Nodeptr _S = _P._Mynode();
_Acc::_Prev(_S) = _Buynode(_S, _Acc::_Prev(_S));
_S = _Acc::_Prev(_S);
_Acc::_Next(_Acc::_Prev(_S)) = _S;
///
_Acc::_Value(_S) = _X;
//
_Size++;
return iterator(_S);
}
iterator erase(iterator _P) {
_Nodeptr _S = (_P++)._Mynode();//这里已经变成了删除结点的下一个
_Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S);
_Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S);
//这里的删除同样不安全
free(_S);
--_Size;
return _P;
}
//删除区间的函数
iterator erase(iterator _F, iterator _L) {
while (_F != _L) {
erase(_F++);
}
return _F;
}
//给出位置，给出大小，给出值
void insert(iterator _P, size_type _M, const _T& _X) {//插入多少个
for (; 0 < _M; --_M) {
insert(_P, _X);
}
}
//insert 插入一个区间
void insert(iterator _P, const _T * _F, const _T &_X)
{
for (; _F != _X;++_F) {
insert(_P, *_F);
}
}
//保护成员的可访问范围比私有成员大，比公有成员小。能访问私有成员的地方都能访问保护成员
protected:
//_Narg后继参数，_Parg前驱参数
_Nodeptr _Buynode(_Nodeptr _Narg=0,_Nodeptr _Parg=0) {//开辟头节点，让他前一个指针指向自己下一个指针只想自己
_Nodeptr _S = (_Nodeptr)malloc(sizeof(_Node));
assert(_S != NULL);//断言
//_S->_Next = _Narg != 0 ? _Narg : _S;
//_S->_Prev = _Narg != 0 ? _Narg : _S;
_Acc::_Next(_S) = _Narg != 0 ? _Narg : _S;
_Acc::_Prev(_S) = _Parg != 0 ? _Parg : _S;
return _S;
}
private:
_Nodeptr _Head;
size_type _Size;
};
//缺少析构函数，不能将内存释放，只能将节点释放，只是把指针当前的内存释放掉，并没有把指向的空间释放掉

侯捷 stl 重学

C++ 标准库和内核分析

泛型编程

主要使用template（模板）

必须要正确的使用模板

C++ 标准库，头文件不带.h

新式C头文件 不带.h #include

旧时c头文件， #include<stdio.h>

命名空间，把自己的封装起来，

using namespace std

把命名空间打开，就不会不方便了

或者单个打开

using std::cout

https://cplusplus.com/

cppreference.com

gcc.gnu.org

Test-STL.cpp

STL 六大部件

容器（containers）

分配器（allocators）

算法（algorithms）

迭代器（iterators）

适配器（Adapters）

仿函数（Functors）

最重要的是，容器和算法

容器，让我们把内存解决掉

分配器去支持容器，

那么谁操作容器呢，模板函数，也就是算法

模板编程：数据在容器里，

操作和容器中间，使用迭代器，也就是泛化的指针进行相连

仿函数，作用像函数而已。

适配器：也就是变压器~每个电脑都会有

也就是做了转换~

尖括号就是模板，指定，数的类型，第二个参数，允许你放一个分配器，你可以不写，会有默认使用的分配器，大部分人不写~

分配器也是模板，你得告诉他分配器需要分配什么东西

也是int

前后两个参数，两者不匹配也会报错

count_if 算法。

vi，设置初值，一个迭代器对吧，

容器都有着begin，end函数

仿函数 less，套了一个适配器，

哪一个复杂度最低呢?

不知道咯

前闭后开区间

begin指向第一个元素，end指向最后一个元素的下一个元素

不一定是连续空间~

所有的容器都有iterator的哟~

iterator 就大概是一个泛化的指针

*，++。–。->

auto 什么类型呢？，你自己想，我不给你写

auto加引用，那么，出来的值都是引用，引用，乘三，原值就会改变，如果你不是引用，原来的值不会改变

可以适度使用auto

所有的容器

容器的分类

序列式，

关联式（key-value）方便查找

unordered containers 不定序容器

sequence container

array 数组，

vector 向量（没人这么叫） 他会自动增长，前面不能加~我们只管放入

deque：双端队列，两端可进可出~

list：双端链表

forward-list 单向链表

list比forwoard耗用内存多，list多带两个指针，32位电脑，四个字节，会占用很多的~

associative container

用红黑树，来做set map

集合set。multiset

set key和value不分家

multiset key可以重复

map/multimap

一个key，一个value

multimap key可以重复

hashTable separate chaining

一个篮子有一个链表

没记错的话，是有一个hash表来存储的

有一些算法的~

碰撞没关系，你直接放链表，

其中的一个链表太长，他查找特别慢

array

get_a_target_Long

我选个容器，

get_a_target_string()

放到空间的数值转换为字符串

模拟放入object，

方便快排，qsort，他的排序规则

array.data() 会传回来 这个数组的首地址

clock() 从程序执行到这个代码，所消耗的毫秒数

bsearch 二分查找，先排序，才能二分查找。

vector

设定namespace 在这namespace中，不会和其他冲突，

每个测试，每个片

vector 不存在push front 只有push back， 单项嘛，

push back 从尾巴放

同时vector 是倍增的，按空间增长的。

这里try catch 因为他会一直增长，保证用户输入！ 他会内存不够，总不能响应你1亿对吧

abort（） 退出程序

103 106 行夹住时间点

然后去找自己想要输入的值，

调用c++ 库中的 find

她传回来的iterator比较长，我们使用auto

我们使用两种查找方式，第一个find，第二个二分查找，先排序哟

binary search

find 就正常一个一个找，循序查找，看看谁快

但是，结果，find 0毫秒

qsort sort后，查找 2毫秒

vector 成长，是要找另一个比自己大两倍的地方，直接挪过去

list

list，一个一个加

list有个特殊的，max_size()

排序一遍，两秒多

调用的是，容器的自己sort，标准库有sort，容器自己也有sort

forwoard_list

他只有一端，从后面放会很慢，

push_front 会方便点

没有back，没有size函数

这里使用全局的find，

slist

devc++ 特性有的，非标准的

这个和forwardlist特别像，没有什么区别

deque

双向开容器，

连续的假象

使用者感觉是连续的，

++ 这个动作自动加过去的，deque分段连续，

五个指针，指出来，都有次序性

每次扩充一个buffer，

deque，她存着指针，每个指针指向一个buffer

list和forwardlist有sort，这儿只能用全局的sort了

关联式容器，查找非常快，几乎都是0毫秒

下面两个，都是使用的deque，其实下面两个都叫适配器，

使用容器 stack

栈，一端进，同一个口出

先进后出

push放元素，pop出元素

queue

队列，一个口进，另一个口出

先进先出

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vWQhpqJR-1629442745504)(https://gitee.com/dingpengs/image/raw/master/imgwin//20210819154239.png)]

他的动作也是push pop

stack和queue 不提供iterator，所以也没有去find，因为find返回迭代器

multiset

当然不能存set啦，不能重复set都

落在树里是有一定规则的

调用了下，size，max_size

容器本身就有find，总库也会有find，当然这是容器自己的find快~

可能安插的时候会慢点

multimap

有key和value

用key来找value

第一个参数，key，第二个参数value

insert 我们自己组合key和value，

pair 函数，将两个数据组合成一组数据,标准库提供的

着利用容器的find

这里取出来的也是pair类型，第一个key是first，第二个value是second

unordered_multiset

bucket_count() 篮子个数~

源码分布

include里面

后面

c++ 并不是面向对象，继承关系不多，

模板编程

OOP 和 GP

面向对象编程 和 泛型编程

OOP将data和method合在一起

GP是data 和method分开

sort算算法，vector 算容器，通过迭代器来加在一起~

GP的好处

OOP

在这里，为什么不能直接用全局的sort呢》？

迭代器进行加减除，一定是随机访问迭代器。

标准库的sort是需要一定条件的

而，list的迭代器，不能够随便跳，只能一个一个往下走

所有的算法，无非就是在比大小

max有两个版本，

我们可以定义按什么比

第一个按照ascii，第二个，我们加入了strlong

自己定义的strlog函数

操作符重载 operator overloading

++i

i++

一个操作数，两个操作数的

举一个例子

链表的迭代器

她一定会重载这四个

模板类class template

类模板

写一个T，这里随便，我不定，编译的时候定

函数模板function template

他会自动推导，T为stone

小于号是会作用在左边的值，找重载小于号

有推导这里就不用限制，而上一个必须要，他不知道推导

成员模板

目前不会看到

Specialization 特化

泛化之外写特化

如果指定的是int，就会有一个特别版本，如果指定的是double也会有一个特别版本

因为，之前有指定，所以template设置为空。

这样直接使用，foo不是int 不是double，她就默认选了第一个

_STL_TEMPLATE_NULL 这里typedef template

当T 是void的时候，有特别的设计

这个特化算全特化，

Partial Specialization 偏特化

有两个模板参数，绑定一个，有一个要写出来

另外一个是范围的偏特化

这里第二个，泛化的这里，可以，只要是一个指针，我就有独特的设计，指向什么都可以，

第三个，是指向const t的指针，第二个是指针，略微不同

篮子比元素多，合理吗?合理~

如果元素个数>=篮子，那么篮子就要扩充两倍

原来的篮子就会被打散

最大的载重因子不会变 1

我们试试find

set

key==value

insert进去即可

32768 我们从0-32767

正好都放了

map

mapsize却是100w，不是32768

multimap不能使用{} 座insertion

map可以

c[i] = string(buf)

i是key，buf是值

放入了红黑树

她自动变成pair

key不会重复，只有value会重复

使用分配器

allocator

分配内存给他他们使用喽

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bt4ORkWJ-1629442745517)(https://gitee.com/dingpengs/image/raw/master/imgwin//20210819174314.png)]

这里列出了很多，都是模板，他的第二个默认值，是std::allocator

ext 扩充性，非标准的分配器

这里把list 第二个参数明确的写出来了，

这些分配器在__gnu里面

第一个内存池，第二个bitmap_allocator

这样我们使用不同的容器，看看其他分配器。

当然可以直接使用分配器，她只有一个allocate和一个delloocate

这里的 1 是一个int，

我们完全可以用其他的，这种，

new搭配delete，malloc和free

deallocate（p,1） 还给她创建的指针，还要还当初要的几个

源码分布

include里面

后面

c++ 并不是面向对象，继承关系不多，

模板编程

OOP 和 GP

面向对象编程 和 泛型编程

OOP将data和method合在一起

GP是data 和method分开

sort算算法，vector 算容器，通过迭代器来加在一起~

GP的好处

OOP

在这里，为什么不能直接用全局的sort呢》？

迭代器进行加减除，一定是随机访问迭代器。

标准库的sort是需要一定条件的

而，list的迭代器，不能够随便跳，只能一个一个往下走

所有的算法，无非就是在比大小

max有两个版本，

我们可以定义按什么比

第一个按照ascii，第二个，我们加入了strlong

自己定义的strlog函数

操作符重载 operator overloading

++i

i++

一个操作数，两个操作数的

举一个例子

链表的迭代器

她一定会重载这四个

模板类class template

类模板

写一个T，这里随便，我不定，编译的时候定

函数模板function template

他会自动推导，T为stone

小于号是会作用在左边的值，找重载小于号

有推导这里就不用限制，而上一个必须要，他不知道推导

成员模板

目前不会看到

Specialization 特化

泛化之外写特化

如果指定的是int，就会有一个特别版本，如果指定的是double也会有一个特别版本

因为，之前有指定，所以template设置为空。

这样直接使用，foo不是int 不是double，她就默认选了第一个

_STL_TEMPLATE_NULL 这里typedef template

当T 是void的时候，有特别的设计

这个特化算全特化，

Partial Specialization 偏特化

有两个模板参数，绑定一个，有一个要写出来

另外一个是范围的偏特化

这里第二个，泛化的这里，可以，只要是一个指针，我就有独特的设计，指向什么都可以，

第三个，是指向const t的指针，第二个是指针，略微不同

分配器allocator

效率包括速度和空间

先谈谈 operator new（） 和malloc（）

c 上面最后都会跑到malloc

因为附加了很多，malloc 开空间附加了很多东西，

malloc 小内存，附加东西相较来说大，你要求的只有浅蓝色的

vc6stl allocator的使用

默认使用allocator

也是调用的malloc

allocator() 这样就是一个object

一个typedef 后面直接跟一个空括号，作为临时对象，没有名称

512个什么呢？使用const void * 没名字的参数，他不在乎传给他什么，什么都可以

那么归还呢？

allocator().deallocate 临时对象，归还512个分配的内存，归还指针

容器用就没问题，我们用很困难

BC5 STL对allocator的使用

我们得查他一下typedef

也是默认用的allocator

同时也是调用底层的free和malloc

如果我们，区块小小的，开个100w，额外开销就会很大

G2.9Stl 对allocator的使用

他补了一个注释

虽然有符合标准的，他自己的从来没有用过他allocator

他默认使用的是alloc

他的运行状况，本课不做讲解。

他要尽量减少malloc次数，减少额外开销（也就是cookie）。

他空间的大小，在首尾，写的

容器的元素大小一样，不管他几个喽，

容器的大小会被调整到8的倍数，

按照倍数找链表负责

100w个元素都不带cookie，可以省800w字节

G4.9 STL 对allocator的使用

他新版本直接没有alloc了

有一个父类，他有一个名字，在new_allocator

他又回到了malloc和free的时代，为什么不用好东西呢？

他的alloc还在的，放在了ext中的allocator

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xhqtnBzS-1629462378033)(…/…/…/AppData/Roaming/Typora/typora-user-images/image-20210820161905148.png)]

第一个是基层，后面是衍生层，不是继承，是复合

后退是衍生层

heap是一个特殊的容器

老师看了所有的source code

list大小都变了2.9和4.9版本

容器list

最具代表性的

list只有一个属性，node，link_type 是什么》？是一个指针指向list_node

一个list大小 四个字节 gnu2.9版

有一个向前的指针，向后的指针，还有一个数据

他的指针类型都是void，后面要使用的话需要转型

他用的alloc分配器，他自己的大小是多大》？ 就是link_type node 大小，4个字节，不大

iterator

希望他模拟指针的动作，但不完全是指针。

需要她足够聪明，让他自己找到地方

必须是一个class，所有的容器出了vector，array所有的iterator都是class

先看看用法

在list里面取iterator 其实也就是一个类的对象，

传三个模板参数，好神奇！

节点的设计

一定要有五个typedef

一大组的function

我们来看看++ 怎么实现的，

这里有两个加加

比较特别可以++i和i++

++i 前置型 i++后置xing

没参数 有int（没意义的）

我们来看++的动作

node的next赋值又给了node，，他就移动了，

–的话也就是将node的prev赋值给了node，他就–了

后加加有啥区别呢？

把原来的东西，寄存起来，加完之后，传回去

1、这里* 不是重载了吗？事实上不是，为什么不会唤起operator*呢？

因为编译器先遇到了另一个，星号动作之前

这个是一个拷贝构造，也就是等于号，

（拷贝构造函数和赋值运算符）

https://www.cnblogs.com/alantu2018/p/8459250.html

然后后佳佳调用了前加加

这样就会被拷贝复制

就会调用拷贝构造函数

前加加和后佳佳的返回类型并不相同

为什么呢?

按理说，后加加不能实现哟

后加加，为了阻止他的两次后佳佳，我们不带引用，

他除了移动，还需要提取，也就是* 和-》

通过*node取得整个节点 然后再取data

-> 和 *差不多

五个typedef是一定要的哟

这个void为什么呢？

这三个参数为什么呢？

完全没有必要传三个，void也没有必要

我们来看新的G4.9

G2.9 vs G4.9

我们上述的bug都更新了

point to 自己本身，他三部分，继承了base，加上data本身

容器list

G4.9 很麻烦，很复杂

G2.9他只是一个class

G4.9 直接一堆继承

一定要有一个虚的，才能保证前闭后开

begin，end指向

4.9版也一样

但是4.9版本，node为什么是8呢？

因为有父类，父类多大就多大他有继承

iterator需要遵循的原则

一定要有五个typedef

迭代器的设计原则和iterator traits的作用与设计

iterator需要遵循的原则

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-H6Ynt8gh-1629703042360)(https://gitee.com/dingpengs/image/raw/master/imgmac//20210822150938.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0dsq8SMH-1629703042362)(https://gitee.com/dingpengs/image/raw/master/imgmac//20210822162134.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6lsMUx3U-1629703042363)(https://gitee.com/dingpengs/image/raw/master/imgmac//20210822162200.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ofbLCLEM-1629703042369)(https://gitee.com/dingpengs/image/raw/master/imgmac//20210822162232.png)]

traits 用来萃取出iterator的特性

他有什么特性呢？

iterator是容器和算法之间的桥梁

iterator需要选一个最佳化的算法

我们看，ritate想要知道什么特性

他想萃取出iterator的分类

有的iterator可以增，减少，还有的可以跳着走，表明他是什么类型

这就叫iterator-category

这里他想知道value_type 值的类型对吧

diffrenecetype 是两个iterator之间距离用什么表示

iterator萃取要要萃取出算法的提问，

一共五种

reference pointer 这两个没有使用

iterator_category()

Difference_type

Value_type

必须要提出五种

他怎么提问呢？他想要知道东西

I::iterator_cateory 这样就是结果了，直接出值

那么链表的iterator之间的距离怎么定义？

ptfdiff_t 用这个可能是一个unsign int

链表的value——type是什么？

链表元素是t 这里就是t

iterator——category 使用双向的bidrectional-iterator-tag表示

如果c++的指针，那么如何回答问题呢？

指针不会回答问题，怎么办

那么萃取就需要有这样一个机制，去识别是class的iterator的智

还是普通的指针传进来

要加一个萃取机，

iterator-traits

间接问，放到traits里，让他去问，（中间层）

指针都到了2和3

既然收到普通指针，指针没法回答，直接value-type就是T 或者const T

这两个偏特化，为什么都是t呢？

因为加上一个const 变成了没有办法赋值的value-type没有用了，

因此需要都是t

完整的iterator——traits

上面就是五个完整的问题

那么指针如何分类嗯？

指针的话肯定是random—access

different
特别针对迭代器设计的萃取机

各种各样的traits

越加越多，

vector深度搜索

容器vector

内存不能原地扩充，我们必须找另外一个地方！

如果找不到两倍大，就结束了

哪个环境也是两倍成长

三个指针，就能控制整个vector

那么sizeof。vector 本身就是这三个指针的大小，32位电脑一个指针4个字节

每一个容器有begin，end。size

end里面finish取的是下一个单元块

size永远不会变

两次函数调用～

capacity 容量，

比如一可以放入8个元素，capacity也就是8个

先看看有没有剩余的空间，如果没有，那么我们就开辟新的了

里面又做了一次检查，看看空间是否没了（其他函数调用会用到）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ysGMBWM3-1629703042396)(https://gitee.com/dingpengs/image/raw/master/imgmac//20210822165041.png)]

判断，旧的大小是多少。

看看。是不是开始，是不是0，是0就给一个1

直接原来的大小✖️2，大小两倍增长

分配好空间后，这里有trycatch

先把旧的拷贝到新的地方去

然后把第九个放进去，让那好把安插点之后的传了进去，（其他函数会用到）就比如insert 你插入到第三个，得把安插点之后的也放进去对吧

每次成长，会有大量的拷贝，就会发生拷贝构造，也需要一个一个删除原来的

vector iterator

vector按理说直接就是指针，不存在什么一个一个节点的前后

他有一个定义是iterator， 也就是t*

当使用vector的时候

声明一个变量，直接指向起点

他这里写了三个的解答

他直接把iterator 丢给traits，

一个泛化，两个偏特化，

五种类型，他的category都是randomaccess

g4.9 变成了魔鬼

父类的大小就是他的大小。

容器array

为什么要包装容器呢？

盲猜一手iterator

TR1 容易读

struct和class差不多的

他的data在那儿，传进来就是nm

其他容器可扩充，array不能，先定大小

如果是0的时候，直接给个1

不是0，指定多少就多少

begin就是第0个，end就是第n个

array没有构造和xigou函数

array本身是一个连续的空间

他的迭代器本身就可以用指针来

一部分针对指针，一部分针对class

我们来看4.9

g4.9 版本

——M——elem 其实就是 ——type【nm】

语言规定了，第二个就不允许哟

容器forward—list

单向链表，和list差不多，

容器deque

单向就成了vector喽，他会找一个新的开辟对吧

那么deque怎么做》？

分段串接，灰色的格子就是node一些节点，一些缓冲区

里面都是指针，一个指针后面一个缓冲区

新分配缓冲区，然后串在后面即可，

如果前面要插入元素，也是新分配好缓冲区，然后串接在前面即可

deque的迭代器是一个class 有四个元素

其中的node就是指控制中心

他能跳到其他分段，first和last 指的是 node 的头和 尾

也就是标兵，设定边界，每次加加减减都会判断是否处于一个新的结尾，然后会跳转，

deque是一个分段连续， node 指针，回到控制中心，

cur 指的是当前到底指在哪里

first lat不会变，cur变动，

如果变了缓冲区，那么他这四个都会进行变动，

我们为什么要写三个迭代器？

所有的容器 都会维持着两个迭代器。

begin传回start end传回finish

G2.9

他的数据部分

map-size 是控制中心的大小，

8—-16——32—–64。他也是两倍成长

map类型是 T**

指向指针的指针，其实32位，大小为4

一个迭代器。deque中，就是 16字节。

参数4*4=16

一个deque 本身，就是40 字节

这个三个参数，4.9 就不是喽

最后一个参数，buffsiz 缓冲区大小，之前可以指定，4.9 不行

0表示使用默认值，不是0的话，开始计算，

如果大于512 字节，那么就会让一个缓冲区放一个元素

如果小于512 ，比如放4。那么一个缓冲区放多少呢，512/4

deque iterator

我们来看看迭代器。

遵循的规则，定义五个相关的类型，

自己的分类是 random accesss iterator

因为可以制造出连续的假象

deque::insert()

允许指定位置，然后放一个参数进去

第一个是一个迭代器，用迭代器的指定位置，因为他可以往前往后，他必须推动，往前还是往后，他需要进行运算。

先判断，是起点么？最前端，直接pushfront

然后再判断，是尾端么，pushback

或者，我们走辅助函数，aux

判断往头，往尾，谁短

如果插入小于中点，就靠前，

大于中点，靠近尾端，

都做完后，在空处的位置放一个新值

deque 如何模拟连续空间

back，返回最后一个，然后相当于把finish倒退一个

两个迭代器要算出距离的元素，

buffer_size 这个里面是8 他们× 有几个节点

一个是末尾距离，一个是起始的元素

加加和减减

如果到达边界，就会跳到下一个缓冲区

first last需要重新设置

如上是移动一个位置，我们移动多个位置

跳的时候有时候会跨越缓冲区的

不跨越缓冲区，很简单，跨越缓冲区，就要进行计算跨几个

同时提供了中括号操作符，

G4.9

他扩充肯定需要copy，他做法是，copy到16的中段，

让左边和右边有空余

容器queue

stack和queue 内涵一些deque，封掉一些功能，就可以

都是转调用

当然deque会快

stack和queue不支持遍历，当然也没有迭代器

stack可以选择vector，queue不行

vector没有popfront

如果我们没有调用pop，他也会通过检查

st map都不可以作为底部支撑，因为不满足调用的一些函数

编译会通过哟

不会做全面性的检查

容器rb-tree

关联式容器

用key去寻找value

高度平衡的二分树

排序规则有利于search 和insert

红黑树是一个sorted排序状态

begin最左边，end最右边

先从最左边的子树，最左边的元素开始，

5-6-7-6-8-11-10-11-13-12-15

不应该去改红黑树的iterator的元素值

编程层面没有阻止这件事情，我们不应该改

因为这里是key当value所以才可以该，map里面就不行喽

第一个是表示不允许重复，第二个是允许重复，

红黑树的实现，

同时有五个模板参数

key是什么类型，value是什么类型，value是key|data一块儿的

keyofvalue 怎么拿出来，compare 用什么比呢?key是啥呢？如果key是石头呢，

三个数据

header指针，

函数，可能是仿函数~

header 并不会有值放进去，一个虚的点

左上角，我们进行告诉他怎么取值

key of value

compare 是 他的比大小的方式

红黑树，没有必要这么写，因为你用的是他的上层

容器rb—tree 用例

当重复的时候，能放进去，但是也不会造成什么影响，

insert equal 放进去了，count 5 有3个

G4.9版本如下

为了复合OOP

面向对象编程，handle—–body， body是一个实现类

容器set，multiset

set 的话key不能重复，multiset可以重复

因为以红黑树为底，元素自动排序的特性。

无法使用set，multiset的iteraor去改变元素值

set的key必须独一无二的，他调用insert-unique（）

multiset 调用的是insert-equal（）

容器set

内含一个红黑树

其实他的迭代器，用的也是红黑树的迭代器，

直接给了你一个const迭代器，避免修改值

VC6 里面的，写在了内部，

容器map ，multimap

每个元素是value 包含key+value

一样会自动排序

没办法修改key，但是可以修改data，而且是合理的

map要求放入四个参数

这个红黑树，所有的参数都有了，默认值，指定值~

select1st 选择第一个是key，我们告诉他，如何去选择

key of value

他的迭代器就是红黑树的迭代器

pair 包裹了key t

key设置为const，保证了无论如何无法被更改

容器map in vc6

他select1st的函数

给我pair，他把pair的第一个成分给你，

放进去100w

使用自己的find，很方便

容器map，独特的operator[]

要几个，他会返回第几个，

327 它会返回第327个，key是327的咯

如果不存在，他会创造一个，然后放到map里面

map如果有7个hello，她一定会排在一起，

lower-bound 她一定会找到七个里面的第一个回来，

如果没找到就传回来，最适合这个迭代器的存放地方，

括号和insert一样的，

insert会比[ ] 快

源码分析

stl_algo.h

#pragma once
//这个函数是算法的基础库，包括algo，algobase
#ifndef __STL_ALGO_H__
#define __STL_ALGO_H__
#include "stl_config.h"
__STL_BEGIN_NAMESPACE
//lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素。
//这里只写一个lowerbound函数
// Binary search (lower_bound, upper_bound, equal_range, binary_search).
//返回指向范围 [first, last) 中首个不小于（即大于或等于） value 的元素的迭代器，或若找不到这种元素则返回 last 。
template<class _ForwardIter,class _Tp,class _Distance>
_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp & __val, _Distance *) {
_Distance __len = 0;
distance(__first, __last, __len);//求出两个指向之间的距离
_Distance __half;
_ForwardIter __middle;
while (__len > 0) {
__half = __len >> 1;//位运算符，右移一位，相当于除2，先找到一半的位置
__middle = __first;
advance(__middle, __half);//前进后退，把当前的跳转一半的距离，然后进行比较。
if (*__middle < __val) {//相当于一个小二分法。
++__first;
__len = __len - __half - 1;
}
else {
__len = __half;
}
}
return __first;
}
//封装好的接口调用，输入开始结尾，和想要对比的值
template<class _ForwardIter, class _Tp>
inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,const _Tp &__val) {
return __lower_bound(__first, __last, __val,
__DISTANCE_TYPE(__first));
}
//接下来是自带cmp函数的lower—bound
template<class _ForwardIter, class _Tp, class _Compare, class _Distance>
_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,const _Tp &__val, _Compare __comp, _Distance *) {
_Distance __len = 0;
distance(__first, __last, __len);//这里的len相当于会求出他的距离
_Distance __half;
_ForwardIter __middle;
while (__len > 0) {
__half = __len >> 1;
__middle = __first;
advance(__middle, __half);
if (__comp(*__middle, __val)) {
__first = __middle;
++__first;
__len = __len - __half - 1;
}
else
__len = __half;
}
return __first;
}
template<class _ForwardIter, class _Tp, class _Compare>
inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,const _Tp &__val, _Compare __comp) {
return __lower_bound(__first, __last, __val, __comp,__DISTANCE_TYPE(__first));
}
__STL_END_NAMESPACE
#endif // !__STL_ALGO_H__

stl_algobase.h

#ifndef __STL_ALGOBASE_H__
#define __STL_ALGOBASE_H__
#include "type_traits.h"
#include "stl_config.h"
#include <string.h>
#include "stl_iterator_base.h"
#include "stl_iterator.h"
__STL_BEGIN_NAMESPACE
//如下相当于是一个copy_backward函数
/*在一个vector中
将每个元素向后移一位。
如果正向遍历并copy的话，
后面的元素被前面覆盖了，
copy的结果就不对了。
所以必须反向copy。
http://\c.biancheng.net/view/605.html
就只是反向复制了而已
*/
//这里算偏特化，指定了萃取机，只有双向迭代器可以backward
template<class _BidirectionalIter1, class _BidirectionalIter2, class _Distance>
inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first, _BidirectionalIter1 __last, _BidirectionalIter2 __result, bidirectional_iterator_tag, _Distance *) {
while (__first != __last) {
*--__result = *--__last;
}
return __result;
}
template<class _BidirectionalIter1, class _BidirectionalIter2, class _Distance>
inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first, _BidirectionalIter1 __last, _BidirectionalIter2 __result, random_access_iterator_tag, _Distance *) {
for (_Distance __n = __last - __first; __n > 0; --__n) {
*--__result * --__last;
}
return __result;
}
//https://\blog.csdn.net/dongyu_1989/article/details/80061944
//https://\blog.csdn.net/chengzi_comm/article/details/51974119
//按我的理解，就相当于是 copy backward的预处理函数
template<class _BidirectionalIter1, class _BidirectionalIter2, class _BoolType>
struct __copy_backward_dispatch {
//两个萃取
typedef typename iterator_traits<_BidirectionalIter1>::iterator_category _Cat;
typedef typename iterator_traits<_BidirectionalIter1>::difference_type _Distance;
static _BidirectionalIter2
copy(_BidirectionalIter1 __first, _BidirectionalIter1 __last, _BidirectionalIter2 __result) {
return __copy_backward(__first, __last, __result, _Cat(), (_Distance *)0);
}
};
//特化版本1，有“无关紧要的赋值操作符” 会执行下面这个函数：
/*
memmove的处理措施：
（1）当源内存的首地址等于目标内存的首地址时，不进行任何拷贝
（2）当源内存的首地址大于目标内存的首地址时，实行正向拷贝
（3）当源内存的首地址小于目标内存的首地址时，实行反向拷贝
memcpy和memmove都是标准C库函数，在库函数string.h中，它们都是从src所指向的内存中复制count个字节到dest所指向的内存中，并返回dest的值
void *memmove(void *dest,const void *src,size_t count);
*/
template<class _Tp>
struct __copy_backward_dispatch<_Tp *, _Tp *, __true_type> {
static _Tp *copy(const _Tp *__first, const _Tp *__last, _Tp *__result) {
const ptrdiff_t _Num = __last - __first;
memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
return __result - _Num;
}
};
//特化版本2，没有“无关紧要的赋值操作符” 会执行下面这个函数,两个都是truetype,上面针对普通，下面针对const
template<class _Tp>
struct __copy_backward_dispatch<const _Tp *, _Tp *, __true_type> {
static _Tp *copy(const _Tp *__first, const _Tp *__last, _Tp *__result) {
return __copy_backward_dispatch<_Tp *, _Tp *, __true_type>::copy(__first, __last, __result);
}
};
template<class _BI1, class _BI2>
inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) {
typedef typename __type_traits<typename iterator_traits<_BI2>::value_type>::has_trivial_assignment_operator _Trivial;
return __copy_backward_dispatch<_BI1, _BI2, _Trivial>::copy(__first, __last, __result);
}
//copy assignment operator 赋值函数
没有显式定义ctor/dtor/copy/assignemt所以都是trivial
//显式定义了构造函数，所以是non-trivial ctor
//https://\www.daimajiaoliu.com/daima/4edeeb6bc100410
//如果构造函数中写了，那就是no-trivial
//可能大家会有疑问，trivial_assignment_operator 的用途，即不重要的，还有non-trivial 就是重要的，这两个知识点会包含虚函数，或者，虚函数表，即虚表，也就是多态的基础，
//https://\blog.csdn.net/lihao21/article/details/50688337
/*
其次是泛化,再针对原生指针做出特化,如果指针所指对象拥有的是trivial assignment operator,复制操作可以不通过它(也就是ctor),也就是说我们直接用memmove来完成拷贝.如果对于原生指针,它指向的对象拥有的是non-trivial assignment operator,我们就使用for循环来慢慢拷贝了.
*/
template<class _Tp>
inline _Tp *__copy_trivial(const _Tp *__first, const _Tp *__last, _Tp *__result) {
memmove(__result, __first, sizeof(_Tp) * (__last - __first));
return __result + (__last - __first);
}
//以下为copy函数
template<class _Tp>
inline _Tp *__copy_aux2(const _Tp *__first, const _Tp *__last, _Tp *__result, __true_type) {
return __copy_trivial(__first, __last, __result);
}
template<class _InputIter, class _OutputIter, class _Tp>
inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last, _OutputIter __result, _Tp *) {
typedef typename __type_traits<_Tp>::has_trivial_assignment_operator _Trivial;
return __copy_aux2(__first, __last, __result, _Trivial());
}
//https://\www.jianshu.com/p/dc81e085b445
//第一个相当于copy的接口，调用里面的copy辅助函数进行copy，三个迭代器，头，尾，输出
template<class _InputIter, class _OutputIter>
inline _OutputIter copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
return __copy_aux(__first, __last, __result, __VALUE_TYPE(__first));
}
//copy辅助函数，调用copy辅助2
template<class _InputIter, class _OutputIter, class _Distance>
inline _OutputIter __copy(_InputIter __first, _InputIter __last, _OutputIter __result, input_iterator_tag, _Distance *) {
for (; __first != __last; ++__first, ++__result) {
*__result = *__first;
}
return *__result;
}
/*
fill函数的作用是：将一个区间的元素都赋予val值。函数参数：fill(first,last,val);//first为容器的首迭代器，last为容器的末迭代器，val为将要替换的值。
fill_n函数的作用是：给你一个起始点，然后再给你一个数值count和val。 把从起始点开始依次赋予count个元素val的值。 注意： 不能在没有元素的空容器上调用fill_n函数例题：给你n个数，然后输入一些操作：start,count,paint
*/
//fill
template<class _ForwardIter, class _Tp>
void fill(_ForwardIter __first, _ForwardIter __last, const _Tp &__value) {
for (; __first != __last; ++__first) {
*__first = __value;
}
}
//fill_n
template<class _OutputIter, class _Size, class _Tp>
_OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp &__value) {
for (; __n > 0; --__n, ++__first) {
*__first = __value;
}
return __first;
}
//min and max 最基本的，当然我们可以自己增加比较函数
template<class _Tp>
inline const _Tp &min(const _Tp &__a, const _Tp &__b) {
return __b < __a ? __b : __a;
}
template<class _Tp>
inline const _Tp &max(const _Tp &__a, const _Tp &__b) {
return __a < __b ? __b : __a;
}
template<class _Tp, class _Compare>
inline const _Tp &min(const _Tp &__a, const _Tp &__b, _Compare __comp) {
return __comp(__b, __a) ? __b : __a;
}
template<class _Tp, class _Compare>
inline const _Tp &max(const _Tp &__a, const _Tp &__b, _Compare __comp) {
return __comp(__a, __b) ? __b : __a;
}
//swap and iterator_swap
template<class _ForwardIter1, class _ForwardIter2, class _Tp>
inline void __iter_swap(_ForwardIter1 __a, _ForwardIter2 __b, _Tp *) {
_Tp __tmp = *__a;
*__a = *__b;
*__b = __tmp;
//    swap(*__a, *__b);
}
//迭代器的swap
template<class _ForwardIter1, class _ForwardIter2>
inline void iter_swap(_ForwardIter1 __a, _ForwardIter2 __b) {
__iter_swap(__a, __b, __VALUE_TYPE(__a));
}
template<class _Tp>
inline void swap(_Tp &__a, _Tp &__b) {
//引用本身是不能变的，只会变引用指向的值。
_Tp __tmp = __a;
__a = __b;
__b = __tmp;
}
//equal
template<class _InputIter1, class _InputIter2, class _BinaryPredicate>
inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _BinaryPredicate __binary_pred) {
for (; __first1 != __last1; ++__first1, ++__first2)
if (!__binary_pred(*__first1, *__first2))
return false;
return true;
}
template<class _InputIter1, class _InputIter2>
inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2) {
for (; __first1 != __last1; ++__first1, ++__first2)
if (*__first1 != *__first2)
return false;
return true;
}
//--------------------------------------------------
// lexicographical_compare and lexicographical_compare_3way.
// (the latter is not part of the C++ standard.)
template<class _InputIter1, class _InputIter2>
bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2) {
for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) {
if (*__first1 < *__first2)
return true;
if (*__first2 < *__first1)
return false;
}
return __first1 == __last1 && __first2 != __last2;
}
template<class _InputIter1, class _InputIter2, class _Compare>
bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_Compare __comp) {
for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) {
if (__comp(*__first1, *__first2))
return true;
if (__comp(*__first2, *__first1))
return false;
}
return __first1 == __last1 && __first2 != __last2;
}
inline bool
lexicographical_compare(const unsigned char *__first1,
const unsigned char *__last1,
const unsigned char *__first2,
const unsigned char *__last2) {
const size_t __len1 = __last1 - __first1;
const size_t __len2 = __last2 - __first2;
const int __result = memcmp(__first1, __first2, min(__len1, __len2));
return __result != 0 ? __result < 0 : __len1 < __len2;
}
__STL_END_NAMESPACE
#endif // !__STL_ALGOBASE_H__

stl_alloc.h

#pragma once
#ifndef __STL_ALLOC_H__
#define __STL_ALLOC_H__
#include<cstdio>
#include<cstdlib>
#include <cstddef>
#include "stl_config.h"
#include "stl_construct.h"
/*
stdlib.h是C标准函数库的头文件，声明了数值与字符串转换函数, 伪随机数生成函数, 动态内存分配函数, 进程控制函数等公共函数。 C++程序应调用等价的cstdlib头文件.
常用的函数如malloc()、calloc()、realloc()、free()、system()、atoi()、atol()、rand()、srand()、exit()等等。 具体的内容可以打开编译器的include目录里面的stdlib.h头文件查看。
*/
__STL_BEGIN_NAMESPACE
//第一级配置器，直接使用malloc realloc free实现功能
template<int _inst>
class __malloc_alloc_template {
public:
static void *allocate(size_t __n) {//unsignted int == size_t
void *__result = malloc(__n);//(void * 可以表示任意指针)
if (0 == __result) {
//C 库函数 int fprintf(FILE *stream, const char *format, ...) 发送格式化输出到流 stream 中。
fprintf(stderr, "out of memory\n");
//这里相当于把out xxx 写入了stderr
//stderr 标准错误
/*标准错误流
标准错误流是错误消息和其他诊断警告的默认目标。与stdout一样，它通常也默认定向到文本控制台（通常在屏幕上）。
stderr可以用作任何函数的参数，该函数采用FILE*类型的参数，期望输出流，如fputs或fprintf。
*/
exit(1);
}
return __result;
}
static void deallocate(void *__p,size_t /*__n*/) {
free(__p);
}
//C++ 中的 realloc() 函数重新分配先前分配但尚未释放的内存块。
static void *reallocate(void *__p, size_t /* old_size*/,size_t __new_sz) {
void *__result = realloc(__p, __new_sz);//直接使用了realloc，
if (0 == __result) {//没分配上
fprintf(stderr, "out of memory\n");
exit(1);
}
return __result;
}
};
//类结束，成员函数开始
//这里使用typedef一下，方便后续使用，同时，inst在如下没有起到作用，这里设置为0
typedef __malloc_alloc_template<0> malloc_alloc;
//https:\//github.com/jasonblog/note/blob/master/c%2B%2B/c%2B%2B_stl_xue_xi_zong_7d5028_quan_976229.md
//包装，相当于适配器，simple_alloc使得alloc具备标准接口
//第二个参数是让你进行选择使用哪个分配器
//在C++中，用户所需空间可能是任意类型的，有单个对象空间，有连续空间，每次让用户自己计算所需空间总大小不是很友好，因此SGI-STL将空间配置器重新再封装了一层：
//https:\//cloud.tencent.com/developer/article/1688439
template<class _Tp, class _Alloc>
class simple_alloc {
public:
static _Tp *alloc(size_t __n) {
申请n个T类型对象大小的空间
return 0 == __n ? 0 : (_Tp*)_Alloc::allocate(__n * sizeof(_Tp));
//这里只解释一个，相当于if判断对吧，判断，size是0么，是的话，返回0不是就分配n个类型大小
}
//这儿因为allocate里面写成void了，出bug了gan
static _Tp *allocate(size_t __n) {
//申请一个T类型对象大小的空间
return (_Tp *)_Alloc::allocate(sizeof(_Tp));
}
// 释放一个T类型对象大小的空间
static void deallocate(_Tp *__p) {
_Alloc::deallocate(__p, sizeof(_Tp));
}
//释放n个T类型对象大小的空间
static void deallocate(_Tp *__p, size_t __n) {
if (0 != __n) {
_Alloc::deallocate(__p, __n * sizeof(_Tp));
}
}
};
//将alloc定义为一级分配器
typedef malloc_alloc alloc;
__STL_END_NAMESPACE
#endif // !__STL_ALLOC_H__

stl_config.h

#pragma once
#ifndef __STL_CONFIG_H__
#define __STL_STL_CONFIG_H__
//这里是SGI版本stl为了兼容性
#define __STL_BEGIN_NAMESPACE namespace ding_stl{
#define __STL_END_NAMESPACE }
/*
__STL_BEGIN_NAMESPACE宏是在某个配置文件中定义的，就sgi来说，此宏为了兼容一些早期代码，允许stl模板库不是用std命名空间包裹，__STL_BEGIN_NAMESPACE根据用户配置，被定义为“空”或者“namespace std {”之类的实际代码。
*/
#endif // !__STL_CONFIG_H__

stl_construct.h

#pragma once
#ifndef __STL_CONSTRUCT_H__
#define __STL_CONSTRUCT_H__
#include<new>
#include "stl_config.h"
#include "type_traits.h"
#include "stl_iterator_base.h"
__STL_BEGIN_NAMESPACE
//https:\//blog.csdn.net/u014645632/article/details/78795466
//关于placement new 是new开辟内存空间的第四种方式，new算一个函数，可以进行重载
/*不懂得见这里
https:\//www.cnblogs.com/igloo1986/archive/2013/02/01/2888775.html
*/
template<class _T1,class _T2>
inline void _Construct(_T1 *__p, const _T2 &__value) {
//构造函数，在*p指针的位置，开辟空间，第二个是参数
new((void *)__p) _T1(__value);//重新在p的内存上初始化，使用它T1的构造函数，placement new 相当于T1::T1（value）
}
template<class _T1>//这里是只有一个参数的构造
inline void _Construct(_T1 *__p) {
new((void *) __p) _T1();
}
//析构函数
//https://\www.cnblogs.com/zsq1993/p/5838034.html
//显示调用析构函数，只会执行析构函数中的内容，不会释放栈内存，也不会摧毁对象（当然除非你写了）
//隐式调用析构函数，没有提供析构函数的时候，编译器会始终声明一个。
//https://\www.apiref.com/cpp-zh/cpp/language/destructor.html
//https://\www.cnblogs.com/zsq1993/p/5838034.html
template<class _Tp>
inline void _Destory(_Tp *__pointer) {
destroy_one(__pointer, typename __type_traits<_Tp>::has_trivial_destructor());
//第二个参数是萃取，去问萃取机，你这个答案是什么，有不重要的构造函数呢？
//回答有/没有,trivial destructor 就是隐式析构函数，true当然什么事儿都没有，如果是false trivial destructor那么就会调用它本身的显示析构函数
//使用typename 编译器确认他是一个类型，而不是一个变量。
}
template<class _Tp>
void destroy_one(_Tp * , __true_type){
}
template<class _Tp>
void destroy_one(_Tp *__pointer, __false_type) {
if (__pointer != nullptr) {
__pointer->~_Tp();//显示调用析构函数
}
//空指针类型关键字 nullptr
}
//aux辅助函数
template<class _ForwardIterator>
inline void _destory_aux(_ForwardIterator __first, _ForwardIterator __last, __false_type) {
for (; __first != __last; ++__first) {
_Destory(&*__first);//*一个迭代器，就表示迭代器指向的元素，迭代器只不过是一个指针而已，&引用，形参实参一起变（这里是逐个调用析构函数）
}
}
//list迭代器，一个一个往下走对吧，也就是前向迭代器
//这里命名是前向迭代器，方便识别，其他还有随机存取迭代器，双向迭代器，逆向迭代器（他是一个配接器）
//https:|//blog.csdn.net/nestler/article/details/25806567
template<class _ForwardIterator>
inline void __destory_aux(_ForwardIterator, _ForwardIterator, __true_type) {
//查阅资料，这里确实不写形参，
}
template<class _ForwardIterator,class _Tp>
inline void __destory(_ForwardIterator __first,_ForwardIterator __last,_Tp *) {
typedef typename __type_traits<_Tp>::has_trivial_destructor _Trivial_destructor;//起了一个新名字
__destory_aux(__first, __last, _Trivial_destructor());
//类型直接加括号，相当于临时对象，没名称
}
template<class _ForwardIterator>
inline void _Destory(_ForwardIterator __first, _ForwardIterator __last) {
__destory(__first, __last, __VALUE_TYPE(__first));
//typedef void value_type; in stl_iterator.h
}
/*
这是泛化的函数模板，如果是基本类型的指针，显然无法调用析构函数，书上说有基本类型指针的特化函数模板，但实际上源码里是非模板函数，由于非模板函数优先级高于模板函数，遇到类似int*的指针编译器会调用非模板函数，并且不做任何操作，如下所示。
*/
inline void _Destroy(char*, char*) {}
inline void _Destroy(int*, int*) {}
inline void _Destroy(long*, long*) {}
inline void _Destroy(float*, float*) {}
inline void _Destroy(double*, double*) {}
//接下来是构造
template<class _T1,class _T2>
inline void construct(_T1 *__p,const _T2 __value) {
_Construct(__p, __value);
}
template<class _T1>
inline void construct(_T1 *_p) {
_Construct(_p);
}
//接下来是析构
template<class _Tp>
inline void destory(_Tp *__pointer) {
_Destory(__pointer);
}
template<class _ForwardIterator>
inline void destory(_ForwardIterator __first, _ForwardIterator __last) {
_Destory(__first, __last);
}
__STL_END_NAMESPACE
#endif // !_STL_CONSTRUCT_H_

stl_iterator.h

#pragma once
#ifndef __STL_ITERATOR_H__
#define __STL_ITERATOR_H__
#include "stl_config.h"
#include "stl_iterator_base.h"
__STL_BEGIN_NAMESPACE
//http:\//ibillxia.github.io/blog/2014/06/21/stl-source-insight-2-iterators-and-traits/
/*
在 stl_iterator.h 文件中，设计了 back_insert_iterator, front_insert_iterator, insert_iterator, reverse_bidirectional_iterator, reverse_iterator, istream_iterator, ostream_iterator, 等标准的迭代器，其中前3中都使用 output_iterator 的只写特性（只进行插入操作，只是插入的位置不同而已），而第4种使用的是 bidirectional_iterator 的双向访问特性，第5种使用的是 random_access_iterator 的随机访问特性。而最后两种标准迭代器分别是使用 input_iterator 和 output_iterator 特性的迭代器。从这几个标准的迭代器的定义中可以看出，主要是实现了 operator=, operator*, operator->, operator==, operator++, operator--, operator+, operator-, operator+=, operator-= 等指针操作的标准接口。根据定义的操作符的不同，就是不同类型的迭代器了。
*/
//https:\//blog.csdn.net/weixin_42709632/article/details/104860823?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-1
//后插
template<class _Container>
class back_insert_iterator
{
protected:
_Container * container;
public:
typedef _Container container_type;
typedef output_iterator_tag iterator_category;
typedef void value_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
/*
explicit的主要用法就是放在单参数的构造函数中,防止隐式转换, 导致函数的入口参数, 出现歧义.
如果可以使用A构造B, 未加explicit的构造函数, 当使用B进行参数处理时, 就可以使用A, 使得接口混乱.
为了避免这种情况, 使用explicit避免隐式构造, 只能通过显示(explicit)构造.
*/
explicit back_insert_iterator(_Container &__x) : container(&__x) {}
/*
insert_iterator不支持–运算符重载，可以看出它是单向迭代器。另外ostream_iterator和insert迭代器一样，*、++等运算符都存在，也可以使用，但是都不对对象做任何操作，只是返回对象自身，这样做的原因就是为了迎合其他迭代器的口味，与迭代器这个大家庭的用法一致。方便阅读和修改。
*/
back_insert_iterator<_Container> &operator = (const typename _Container::value_type &__value) {
container->push_back(__value);
return *this;
}
back_insert_iterator<_Container> &operator*() { return *this; }
back_insert_iterator<_Container> &operator++() { return *this; }
back_insert_iterator<_Container> &operator++(int) { return *this; }
};
//前插
template<class _Container>
class front_insert_iterator {
protected:
_Container *container;
public:
typedef _Container container_type;
typedef output_iterator_tag iterator_category;
typedef void value_type;
typedef void pointer;
typedef void difference_type;
typedef void reference;
explicit front_insert_iterator(_Container &__x) : container(&__x){}
front_insert_iterator<_Container> &operator= (const typename _Container::value_type &__value) {
container->push_front(__value);
}
front_insert_iterator<_Container> &operator*() { return *this; }
front_insert_iterator<_Container> &operator++() { return *this; }
front_insert_iterator<_Container> &operator++(int) { return *this; }
};
template<class _Container>
inline front_insert_iterator<_Container> front_inserter(_Container &__x) {
return front_insert_iterator<_Container>(__x);
}
template<class _Container>
class insert_iterator {
protected:
_Container *container;
typename _Container::iterator iter;
public:
//常规五要素
typedef _Container container_type;
typedef output_iterator_tag iterator_category;
typedef void value_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
insert_iterator(_Container &__x,typename _Container::iterator __i):container(&__x),iter(__i){}
insert_iterator<_Container> &operator=(const typename _Container::value_type &__value) {
iter = container->insert(iter, __value);//将元素插入到iter指向的元素之前的位置
++iter;//递增，指向原来的元素
return *this;//谁访问地，你返回什么东西。
}
//同样的insert迭代器，没有*，之类的，也就没有运算符重载
insert_iterator<_Container> &operator*() { return *this; }
insert_iterator<_Container> &operator++() { return *this; }
insert_iterator<_Container> &operator++(int) { return *this; }
};
//这个应该相当于对外的接口
template<class _Container, class _Iterator>
inline insert_iterator<_Container> inserter(_Container &__x, _Iterator __i) {
typedef typename _Container::iterator __iter;
return insert_iterator<_Container>(__x, __iter(__i));
}
//反向迭代器
template<class _Iterator>
class reverse_iterator {
protected:
_Iterator current;
public:
typedef typename iterator_traits<_Iterator>::iterator_category iterator_category;
typedef typename iterator_traits<_Iterator>::value_type        value_type;
typedef typename iterator_traits<_Iterator>::difference_type   difference_type;
typedef typename iterator_traits<_Iterator>::pointer           pointer;
typedef typename iterator_traits<_Iterator>::reference         reference;
typedef _Iterator                                              iterator_type;
typedef reverse_iterator<_Iterator>                            _Self;
//习惯问题，定义函数另写一个public也可，public这里可写可不写
public:
reverse_iterator() {}
explicit reverse_iterator(iterator_type __x) : current(__x) {}
reverse_iterator(const _Self &__x) : current(__x.current) {}
template<class _Iter>
reverse_iterator(const reverse_iterator<_Iter> &__other) : current(__other.base()) {}
iterator_type base() const {
return current;
}
// 该迭代器是从后面end()开始，需要往前一步，才可以获取到有效的迭代器位置
reference operator*() const {
_Iterator __tmp = current;
return *--__tmp;
}
pointer operator->() const {
return &(operator*());
}
//反向，加加就相当于减减，下面都是一些运算符重载了
_Self &operator++() {
--current;
return *this;
}
_Self operator++(int) {
_Self __tmp = *this;
--current;
return __tmp;
}
_Self &operator--() {
++current;
return *this;
}
_Self operator--(int) {
_Self __tmp = *this;
++current;
return __tmp;
}
_Self operator+(difference_type __n) const {
return _Self(current - __n);
}
_Self operator-(difference_type __n) const {
return _Self(current + __n);
}
_Self &operator+=(difference_type __n) {
current -= __n;
return *this;
}
_Self &operator-=(difference_type __n) {
current += __n;
return *this;
}
reference operator[](difference_type __n) const {
//        base()[-n-1]
return *(*this + __n);
}
};
__STL_END_NAMESPACE
#endif // !__STL_ITERATOR_H__

stl_iterator_base.h

#pragma once
#ifndef __STL_ITERATOR_BASE_H__
#define __STL_ITERATOR_BASE_H__
#include<stddef.h>
#include "stl_config.h"
__STL_BEGIN_NAMESPACE
//使用以下五个标签进行优化，目的是为了让编译器在执行时就确定使用那种方法
//https:\//cloud.tencent.com/developer/section/1011037
//https :\//www.cnblogs.com/xiaoshiwang/p/11937275.html
//https :\//zhuanlan.zhihu.com/p/51999289
struct input_iterator_tag {
};
struct output_iterator_tag {
};
//public继承，因为forward就必须完全支持input的所有功能更对吧，
struct forward_iterator_tag :public input_iterator_tag {
};
struct bidirectional_iterator_tag : public forward_iterator_tag {
};
struct random_access_iterator_tag :public bidirectional_iterator_tag {
};
/*
这里他想知道value_type 值的类型对吧
diffrenecetype 是两个iterator之间距离用什么表示
iterator萃取要要萃取出算法的提问，
一共五种
reference pointer 这两个没有使用
iterator_category()
Difference_type
Value_type
必须要提出五种
*/
// 为什么是五种，以及，到底几个，见侯捷stl，array，vector 等iterator 不是类传进来，而是指针，所以我们需要写偏特化，指针的偏特化
/*
紧接着定义了一个类模板 iterator 。该类模板有五个模板形参, _Category 是上面定义的五种迭代器标记之一，用来标识迭代器的类型。_Tp 表示迭代器指向的元素。 。两个迭代器之间可以计算其差值，_Distance 表示用什么类型的数据存储其差值。_Distance 的缺省实参为 ptrdiff_t ，其中 ptrdifff_t 是 signed long 的类型别名。迭代器可以通常都可以索引某个元素， _Pointer 表示可以指向这种类型的元素的指针，_Reference 表示对这种类型的元素的引用。
*/
template<class _Tp, class _Distance>
struct input_iterator
{
typedef input_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp *pointer;
typedef _Tp &reference;
};
struct output_iterator
{
typedef output_iterator_tag iterator_category;
typedef void value_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
};
template<class _Tp, class _Distance>
struct forward_iterator
{
typedef forward_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp *pointer;
typedef _Tp &reference;
};
template<class _Tp, class _Distance>
struct bidirectional_iterator {
typedef bidirectional_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp *pointer;
typedef _Tp &reference;
};
template<class _Tp, class _Distance>
struct random_access_iterator {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp *pointer;
typedef _Tp &reference;
};
template<class _Category, class _Tp, class _Distance = ptrdiff_t, class _Pointer = _Tp * , class _Reference = _Tp & >
struct iterator {
typedef _Category iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Pointer pointer;
typedef _Reference reference;
};
template<class _Iterator>
struct iterator_traits {
typedef typename _Iterator::iterator_categroy 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;
};
//对于指针类型的偏特化
template<class _Tp>
struct iterator_traits<_Tp *> {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef _Tp *pointer;
typedef _Tp &reference;
};
template<class _Tp>
struct iterator_traits<const _Tp *> {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef const _Tp *pointer;
typedef const _Tp &reference;
};
//既然收到普通指针，指针没法回答，直接value-type就是T 或者const T
//只解释一个，这个是萃取机的回答，传来一个迭代器，萃取出类型（例如：random_access_iterator_tag），然后直接定义了一个_iterator_category函数，供下面使用，最后输出他的类型
template<class _Iter>
//const _Iter &和const _Iter & __i 一样，只不过一个是占位符，一个没
inline typename iterator_traits<_Iter>::iterator_category __iterator_category(const _Iter &) {
typedef typename iterator_traits<_Iter>::iterator_category _Category;
return _Category();
//或者可以省略为：return typename iterator_traits<_Iter>::iterator_category()
}
//下面这个应该是供外部使用，
template<class _Iter>
inline typename iterator_traits<_Iter>::iterator_category iterator_category(const _Iter &__i) {
return __iterator_category(__i);
}
//static_cast 静态转换符 类型转换使用 static_cast <type-id> ( expression )
//https:\//e8859487.pixnet.net/blog/post/402001658-%5Bc%2B%2B%5D-static_cast-%E7%94%A8%E6%B3%95%E8%AA%AA%E6%98%8E---%28%E5%9F%BA%E7%A4%8E%E7%AF%87%29
//https:\//docs.microsoft.com/zh-cn/cpp/cpp/static-cast-operator?view=msvc-160
//https:\//bytes.com/topic/c/answers/475446-when-use-null-when-use-static_cast-some_pointer_type-0-a
/*
这里使用static_cast<pointer>(0) 表示null空指针，因为在 C++ 中，常量 0 总是可以自由转换为任何
指针类型
*/
template<class _Iter>
inline typename iterator_traits<_Iter>::difference_type *__distance_type(const _Iter &) {
return static_cast<typename iterator_traits<_Iter>::difference_type *>(0);
}
template<class _Iter>
inline typename iterator_traits<_Iter>::difference_type *distance_type(const _Iter &__i) {
return __distance_type(__i);
}
//value_type 同理
template<class _Iter>
inline typename iterator_traits<_Iter>::value_type *__value_type(const _Iter &) {
return static_cast<typename iterator_traits<_Iter>::value_type *>(0);
}
template<class _Iter>
inline typename iterator_traits<_Iter>::value_type *value_type(const _Iter &__i) {
return __value_type(__i);
}
//接下来搞宏定义，下面的不能被上面的代码调用
#define __ITERATOR_CATEGORY(__i) __iterator_category(__i)
#define __DISTANCE_TYPE(__i)     __distance_type(__i)
#define __VALUE_TYPE(__i)        __value_type(__i)
//advance()迭代器就是将迭代器it，移动n位。如果it是随机访问迭代器，那么函数进行1次运算符计算操作，否则函数将对迭代器进行n次迭代计算操作。
//distance()可处理迭代器之间的距离
//iter_swap()可交换两个迭代器所指内容（表示所指元素的内容）
//https:\//blog.csdn.net/xuanyin235/article/details/78526919
/*
函数模板 __distance 用来计算两个迭代器之间的差值，模板形参 _InputIterator 表示某种类型的迭代器，在该类型的迭代器中应该要对 operator++ 进行重载 (具体在定义迭代器时会对一些运算符函数进行重载，后续对容器进行介绍时，一并进行介绍)。
while 循环中对 __first 迭代器应用后置自增操作，使得迭代器 __first 朝着迭代器 __last 移动。直到 __first 和 __last 相等。自增运算作用的次数就是两个迭代器的差值。
第三个函数形参限定了 _InputIterator 为 input_iterator 类型的迭代器 。即 _InputIterator 中的 iterator_category 为 input_iterator_tag (或者为 input_iterator 的派生类)
*/
/*看到如下可能会觉得意外，这里是一个GUN2.9 旧版（目测），因为它可以自己控制n，然后下面的偏特化有不需要控制n的
特别全的博客
http:\//wujiantao.github.io/2013/11/07/iterator_base.html
*/
template<class _InputIterator, class _Distance>
inline void __distance(_InputIterator __first, _InputIterator __last, _Distance &__n, input_iterator_tag) {
while (__first != __last) {
++__first;
++__n;
}
}
//如下都相当于是偏特化了,随机存储，直接相减即可
template<class _RandomAccessIterator, class _Distance>
inline void __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, _Distance &__n,random_access_iterator_tag) {
__n += __last - __first;
}
//这个是外界调用的函数，函数 distance 根据迭代器的类型来决定采用上面定义的哪种 __distance 来计算两个迭代器的差值。
//__STL_REQUIRES 是stl种用来座模板参数约束的宏实现过于复杂，这里不做学习
template<class _InputIterator, class _Distance>
inline void distance(_InputIterator __first, _InputIterator __last, _Distance &__n) {
__distance(__first, __last, __n, iterator_category(__first));
}
//如果編譯器支持 partial specialization of class templates（模板類的部分特化），
//       就定義 __STL_CLASS_PARTIAL_SPECIALIZATION.
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
template<class _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type __distance(_InputIterator __first, _InputIterator __last, input_iterator_tag) {
typename iterator_traits<_InputIterator>::difference_type __n = 0;
while (__first != __last) {
++__first;
++__n;
}
return __n;
}
template<class _RandomAccessIterator>
inline typename iterator_traits<_RandomAccessIterator>::difference_type __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag) {
return __last - __first;
}
template<class _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type distance(_InputIterator __first, _InputIterator __last) {
typedef typename iterator_traits<_InputIterator>::iterator_category _Category;
return __distance(__first, __last, _Category());
}
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
//advance同上，这里是跳转，需要写距离，input迭代器，只需要向后
template<class _InputIterator, class _Distance>
inline void __advance(_InputIterator &__i, _Distance __n, input_iterator_tag) {
while (__n--) {
++__i;
}
}
//双向迭代器，需要考虑正负
template<class _BidirectionalIterator, class _Distance>
inline void __advance(_BidirectionalIterator &__i, _Distance __n, bidirectional_iterator_tag) {
if (__n > 0) {
while (__n--) {
++__i;
}
}
else {
while (__n++) {
--__i;
}
}
}
//随机存储，（调用了+=的重载）
template<class _RandomAccessIterator, class _Distance>
inline void __advance(_RandomAccessIterator &__i, _Distance __n, random_access_iterator_tag) {
__i += __n;
}
//外部调用的advance
template<class _InputAccessIterator, class _Distance>
inline void advance(_InputAccessIterator &__i, _Distance __n) {
__advance(__i, __n, __iterator_category(__i));
}
__STL_END_NAMESPACE
#endif // !__STL_ITERATOR_BASE_H__

stl_uninitialized.h

#ifndef __STL_UNINITIALIZED_H__
#define __STL_UNINITIALIZED_H__
#include "stl_config.h"
#include "stl_iterator_base.h"
#include "type_traits.h"
#include "stl_construct.h"
#include "stl_algobase.h"
//这里抄的淘哥的
/*
特化
____>___uninitialized_copy_aux(.,_false_type)
|
|NO _false_type --> _Construct
|
uninitialized_copy() -----> 泛化_>__uninitialized_copy -- is POD ？
|
|YES _true_type --> copy
|
|_特化_>__uninitialized_copy_aux(,_true_type)
如果是POD type，就是基本数据类型(就是内置类型或普通结构与类(没有指针的成员数据)等)那么就直接拷贝即可
如果不是POD type 就需要依次调用构造函数创建数据
*/
__STL_BEGIN_NAMESPACE
template <class _InputIter, class _ForwardIter>
inline _ForwardIter __uninitialized_copy_aux(_InputIter __first, _InputIter __last, _ForwardIter __result, __false_type) {
_ForwardIter __cur = __result;
try {
for (; __first != __last; ++__first, ++__cur) {
_Construct(&*__cur, *__first);
}
return __cur;
}
catch (...) { _Destroy(__result, __cur); throw; }
}
template <class _InputIter, class _ForwardIter>
inline _ForwardIter __uninitialized_copy_aux(_InputIter __first, _InputIter __last, _ForwardIter __result, __true_type) {
return copy(__first, __last, __result);
}
template<class _InputIter, class _ForwardIter, class _Tp>
inline _ForwardIter __uninitialized_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, _Tp *) {
typedef typename __type_traits<_Tp>::is_POD_type _Is_POD;
return __uninitialized_copy_aux(__first, __last, __result, _Is_POD());
}
//一些用于用于填充和拷贝大块内存的全局函数。 对象构造和/析构，与内存配置/释放是分离实现的
template<class _InputIter, class _ForwardIter>
inline _ForwardIter uninitialized_copy(_InputIter __first, _InputIter __last, _ForwardIter __result) {
return __uninitialized_copy(__first, __last, __result, __VALUE_TYPE(__result));
}
/*
先看看两个函数功能:
1.fill是直接对每个元素进行填充value.
2.uninitialized_fill(未初始化填充) 是要根据value的类型来判断使用哪一种方式填充,
如果是POD类型(就是内置类型或普通结构与类(没有指针的成员数据)),就直接调用fill函数.
不是POD类型时,就要遍历每个元素进行构造(调用construct函数).为什么呢?
那是因为*first = value; 类的赋值操作符必须要*first的对象已经生成.
uninitialized_fill一般都是用于未初化填充,也就是说内存区间根本没有对象可言.
此外相关的还有两个: uninitialized_fill_n, uninitialized_copy.原理一样
*/
/*
特化
____>__uninitialized_fill_aux(.,_false_type)
|
|NO _false_type --> _Construct
|
uninitialized_fill() -----> 泛化_>__uninitialized_fill -- is POD ？
|
|YES _true_type --> fill
|
|_特化_>__uninitialized_fill_aux(,_true_type)
*/
template <class _ForwardIter, class _Tp>
inline void uninitialized_fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __x) {
__uninitialized_fill(__first, __last, __x, __VALUE_TYPE(__first));
}
template <class _ForwardIter, class _Tp, class _Tp1>
inline void __uninitialized_fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __x, _Tp1*) {
typedef typename __type_traits<_Tp1>::is_POD_type _Is_POD;
return __uninitialized_fill_aux(__first, __last, __x, _Is_POD());
}
template<class _ForwardIter, class _Tp>
inline void __uninitialized_fill_aux(_ForwardIter __first, _ForwardIter __last, const _Tp& __x, __false_type) {
_ForwardIter __cur = __first;
try {
//这里的构造，在stl_construct 有写
for (; __cur != __last; ++__cur) {
construct(&*__cur, __x);
}
}
catch (...) {
destory(__first, __cur);
}
}
//是POD 所以可以直接进行fill
template <class _ForwardIter, class _Tp>
inline void
__uninitialized_fill_aux(_ForwardIter __first, _ForwardIter __last,
const _Tp& __x, __true_type)
{
fill(__first, __last, __x);
}
//和上面一样的，只不过是成了填入n个，，uniniyialized_fill_n()接受输入端的开始处的迭代器(此分配的内存是未构造的)和初始化空间的大小，最重要的是它会给指定范围内的未构造的内存指定相同的对象。
/*
特化
____>__uninitialized_fill_n_aux(.,_false_type)
|
|NO _false_type --> _Construct
|
uninitialized_fill_n() -----> 泛化_>__uninitialized_fill_n -- is POD ？
|
|YES _true_type --> fill
|
|_特化_>__uninitialized_fill_n_aux(,_true_type)
*/
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __uninitialized_fill_n_aux(_ForwardIter __first, _Size __n, const _Tp& __x, __false_type) {
_ForwardIter __cur = __first;
try {
for (; __n > 0; --__n, ++__cur) {
construct(&*__cur, __x);
}
//note
return __cur;
}
catch (...) {
destroy(__first, __cur);
}
}
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __uninitialized_fill_n_aux(_ForwardIter __first, _Size __n, const _Tp& __x, __true_type) {
return fill_n(__first, __n, __x);
}
template <class _ForwardIter, class _Size, class _Tp, class _Tp1>
inline _ForwardIter __uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x, _Tp1*) {
typedef typename __type_traits<_Tp1>::is_POD_type _Is_POD;
return __uninitialized_fill_n_aux(__first, __n, __x, _Is_POD());
}
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x) {
return __uninitialized_fill_n(__first, __n, __x, __VALUE_TYPE(__first));
}
__STL_END_NAMESPACE
#endif // !__STL_UNINITIALIZED_H__

stl_vector.h

#ifndef __STL_VECTOR_H__
#define __STL_VECTOR_H__
#include "stl_config.h"
#include "stl_alloc.h"
#include "stl_iterator.h"
#include "stl_uninitialized.h"
__STL_BEGIN_NAMESPACE
/*
vector的数据结构为简单连续线性空间，分别用start和finish指向连续空间中已被使用的范围，而end_of_storage指向整个空间的尾部（包括备用空间）。
//https://\www.kancloud.cn/digest/stl-sources/177267
*/
template<class _Tp, class _Alloc>
class _Vector_base {
public:
typedef _Alloc allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
//_Alloc get_allocator() const { return allocator_type(); }
_Vector_base(const _Alloc &)
: _M_start(0), _M_finish(0), _M_end_of_storage(0) {}//冒号后面相当于赋值，c++特有写法
//特化版本
_Vector_base(size_t __n, const _Alloc &)
: _M_start(0), _M_finish(0), _M_end_of_storage(0) {
_M_start = _M_allocate(__n);
_M_finish = _M_start;
_M_end_of_storage = _M_start + __n;
}
//析构函数
~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
//定义三个指针
protected:
_Tp *_M_start;
_Tp *_M_finish;
_Tp *_M_end_of_storage;
typedef simple_alloc<_Tp, _Alloc> _M_data_allocator;
_Tp * _M_allocate(size_t __n) {
return _M_data_allocator::allocate(__n);
}
void _M_deallocate(_Tp *__p, size_t __n) {
_M_data_allocator::deallocate(__p, __n);
}
};
//Alloc是SGI STL的空间配置器，默认是第二级配置器
template<class _Tp, class _Alloc = alloc>
//这里是继承
class vector : protected _Vector_base<_Tp, _Alloc> {
private:
typedef _Vector_base<_Tp, _Alloc> _Base;
public://vector的内嵌型别定义,是iterator_traits<I>服务的类型
typedef _Tp value_type;
typedef value_type *pointer;
typedef const value_type *const_pointer;
typedef value_type *iterator;//vector容器的迭代器是普通指针
typedef const value_type *const_iterator;
typedef value_type &reference;
typedef const value_type &const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef typename _Base::allocator_type allocator_type;
//typedef typename _Base::_Alloc allocator_type
allocator_type get_allocator() const { return _Base::get_allocator(); }
typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
protected:
//这里相当于直接using namespace std;对吧，也就是他直接调用了上面的一些属性
using _Base::_M_allocate;
using _Base::_M_deallocate;
using _Base::_M_end_of_storage;
using _Base::_M_finish;
using _Base::_M_start;
protected:
void _M_insert_aux(iterator __position, const _Tp & __x);
void _M_insert_aux(iterator __position);
public:
//以下为vector的迭代器
iterator begin() {
return _M_start;
}
const_iterator begin() const {
return _M_start;
}
iterator end() {
return _M_finish;
}
const_iterator end() const {
return _M_finish;
}
//反向迭代器，rbegin
reverse_iterator rbegin() {
return reverse_iterator(end());
}
const_reverse_iterator rbegin() const {
return reverse_iterator(end());
}
reverse_iterator rend() {
return reverse_iterator(begin());
}
const_reverse_iterator rend() const {
return reverse_iterator(begin());
}
//下面是三个容量
size_type size() const {
return size_type(end() - begin());
}
size_type max_size() const {
return size_type(-1) / sizeof(_Tp);
}
size_type capacity() const {
return size_type(_M_end_of_storage - begin());
}
//判断为空
bool empty() const {
return begin() == end();
}
//迭代器是特殊指针，也可以用相当于数组类型进行读取
reference operator[](size_type __n) {
return *(begin() + __n);
}
const_reference operator[](size_type __n) const {
return *(begin() + __n);
}
//好像是判断是否越界
void _M_range_check(size_type __n) const {
if (__n >= size())
//todo
{
throw;
};
}
//at()会做边界检查，可以用try catch捕获异常，程序可以不直接退出。，是另一种元素访问，比如vecint.at(3)
reference at(size_type __n) {
_M_range_check(__n);
return (*this)[__n];
}
const_reverse_iterator at(size_type __n) const {
_M_range_check(__n);
return (*this)[__n];
}
//这里把vector容器的构造函数列出来讲解，主要是我们平常使用vector容器时，首先要要定义相应的容器对象，所以，如果我们对vector容器的构造函数了解比较透彻时，在应用当中就会比较得心应手。在以下源码的前面我会总结出vector容器的构造函数及其使用方法。
//默认的构造函数
explicit vector(const allocator_type &__a = allocator_type()) : _Base(__a) {}
//具有初始值和容器大小的构造函数
vector(size_type __n, const _Tp &__value, const allocator_type &__a = allocator_type()) : _Base(__n, __a) {
_M_finish = uninitialized_fill_n(_M_start, __n, __value);
}
//只有容器大小的构造函数
explicit vector(size_type __n) : _Base(__n, allocator_type()) {
_M_finish = uninitialized_fill_n(_M_start, __n, _Tp());
}
拷贝构造函数，不指定的话，默认复制构造函数也就是默认拷贝构造函数，注意，默认构造函数（即无参构造函数）不一定存在，但是复制构造函数总是会存在。
/*
#include<iostream >
using namespace std;
class Complex
{
public:
double real, imag;
Complex(double r, double i) {
real= r; imag = i;
}
};
int main(){
Complex cl(1, 2);
Complex c2 (cl);  //用复制构造函数初始化c2
cout<<c2.real<<","<<c2.imag;  //输出 1,2
return 0;
}
*/
vector(const vector<_Tp, _Alloc> &__x) : _Base(__x.size(), __x.get_allocator()) {
_M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start);
}
//用两个迭代器区间表示容器大小的构造函数
template<class _InputIterator>
vector(_InputIterator __first, _InputIterator __last, const allocator_type &__a = allocator_type()) : _Base(__a) {
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_initialize_aux(__first, __last, _Integral());
}
template<class _Integer>
void _M_initialize_aux(_Integer __n, _Integer __value, __true_type) {
_M_start = _M_allocate(__n);
_M_end_of_storage = _M_start + __n;
_M_finish = uninitialized_fill_n(_M_start, __n, __value);
}
template<class _InputIterator>
void _M_initialize_aux(_InputIterator __first, _InputIterator __last, __false_type) {
_M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
}
//析构函数
~vector() {
destory(_M_start, _M_finish);
}
vector<_Tp, _Alloc> &operator=(const vector<_Tp, _Alloc> &__x);
//当要增加的空间大于备用空间，则需要该函数配置新的vector空间，该操作会释放掉之前的空间，并将之前的内容copy到新的空间。
void reserve(size_type __n) {
if (capacity() < __n) {
const size_type __old_size = size();
iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
destory(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __tmp;
_M_finish = __tmp + __old_size;
_M_end_of_storage = _M_start + __n;
}
}
//assign ，赋值函数，对vector中的元素赋值，和构造相类似，可以按照迭代器来赋值，ve1.assign(ve2.begin(), ve2.end());很好理解，就是复制操作，如果你想把ve1复制为ve2的前三个元素可以这样：ve1.assign(ve2.begin(), ve2.begin() + 3);
//把容器内容替换为n个初始值为value
void assign(size_type __n, const _Tp &__val) {
_M_fill_assign(__n, __val);
}
void _M_fill_assign(size_type __n, const _Tp & __val);
template<class _InputIterator>
void assign(_InputIterator __first, _InputIterator __last) {
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_assign_dispatch(__first, __last, _Integral());
}
template<class _Integer>
void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) {
_M_fill_assign((size_type)__n, (_Tp)__val);
}
template<class _InputIterator>
void _M_assign_dispatch(_InputIterator __first, _InputIterator __last, __false_type) {
_M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first));
}
template<class _InputIterator>
void _M_assign_aux(_InputIterator __first, _InputIterator __last, input_iterator_tag);
template<class _ForwardIterator>
void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag);
//front函数，返回第一个
reference front() {
return *begin();
}
const_reference front() const {
return *begin();
}
//back函数，返回最后一个，也就是指针的前一个
reference back() {
return *(end() - 1);
}
const_reference back() const {
return *(end() - 1);
}
//push back ，从后面插入
void push_back(const _Tp &__value) {
if (_M_finish != _M_end_of_storage) {
construct(_M_finish, __value);
++_M_finish;
}
else {
_M_insert_aux(end(), __value);
}
}
void push_back() {
if (_M_finish != _M_end_of_storage) {
construct(_M_finish);
++_M_finish;
}
else {
_M_insert_aux(end());
}
}
/*交换容器的内容
*这里使用的方法是交换迭代器所指的地址
*/
void swap(vector<_Tp, _Alloc> &__x) {
if (this != &__x) {
ding_stl::swap(_M_start, __x._M_start);
ding_stl::swap(_M_finish, __x._M_finish);
ding_stl::swap(_M_end_of_storage, __x._M_end_of_storage);
}
}
//把x值插入到指定的位置
iterator insert(iterator __position, const _Tp & __x) {
size_type __n = __position - begin();
//插入分很多情况
/*
v.insert(v.begin(),8);//在最前面插入新元素。
v.insert(v.begin()+2,1);//在迭代器中第二个元素前插入新元素
v.insert(v.end(),3);//在向量末尾追加新元素。
v.insert(v.end(),4,1);//在尾部插入4个1
*/
//第一种是插入到vector的末位
if (_M_finish != _M_end_of_storage && __position == end()) {
construct(_M_finish, __x);
++_M_finish;
}
//插入到其他地方
else {
_M_insert_aux(__position, __x);
}
return begin() + __n;
}
//这里我感觉像偏特化，这个是int的
template<class _InputIterator>
void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_insert_dispatch(__pos, __first, __last, _Integral());
}
template<class _Integer>
void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, __true_type) {
_M_fill_insert(__pos, (size_type)__n, (_Tp)__val);
}
//如果不知道是什么，就去问萃取机
template<class _InputIterator>
void _M_insert_dispatch(iterator __pos, _InputIterator __first, _InputIterator __last, __false_type) {
_M_range_insert(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
}
void insert(iterator __pos, size_type __n, const _Tp &__x) {
_M_fill_insert(__pos, __n, __x);
}
void _M_fill_insert(iterator __pos, size_type __n, const _Tp &__x);
//也就是从最后一个地方出
void pop_back() {
--_M_finish;
destroy(_M_finish);
}
//erase，擦除，其中擦除函数是擦除输入迭代器之间的元素，但是没有回收内存空间，只是把内存空间作为备用空间，首先看下该函数的源代码，根据上面函数的定义，我们可以知道，迭代器start和end_of_storage并没有改变，只是调整迭代器finish，并析构待擦除元素对象
iterator erase(iterator __position) {
//如果position后面还有元素，需要拷贝;如果position是最后一个元素，则后面没有元素，直接destroy即可
if (__position + 1 != end()) {
copy(__position + 1, _M_finish, __position);
}
--_M_finish;
destory(_M_finish);
return __position;
}
//erase的例子
//https://\blog.csdn.net/dongyanxia1000/article/details/52838922
//从last开始，拷贝到finish，目标开头到first
iterator erase(iterator __first, iterator __last) {
iterator __i = copy(__last, _M_finish, __first);
destory(__i, _M_finish);
_M_finish = _M_finish - (__last - __first);
return __first;
}
/*
resize(n，t)
多一个参数t，将所有新添加的元素初始化为t。
*/
void resize(size_type __new_size, const _Tp &__x) {
if (__new_size < size()) {
erase(begin() + __new_size, end());
}
else {
insert(end(), __new_size - size(), __x);
}
}
void resize(size_type __new_size) {
resize(__new_size, _Tp());
}
//清除
void clear() {
erase(begin(), end());
}
protected:
template<class _ForwardIterator>
iterator _M_allocate_and_copy(size_type __n, _ForwardIterator __first, _ForwardIterator __last) {
iterator __result = _M_allocate(__n);
try {
uninitialized_copy(__first, __last, __result);
return __result;
}
catch (...) {
_M_deallocate(__result, __n);
}
}
template<class _InputIterator>
void _M_range_initialize(_InputIterator __first, _InputIterator __last, input_iterator_tag) {
for (; __first != __last; ++__first) {
push_back(*__first);
}
}
// This function is only called by the constructor.按我的理解，应该是，开始构造的时候进行初始化用的
template<class _ForwardIterator>
void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag) {
size_type __n = 0;
distance(__first, __last, __n);
_M_start = _M_allocate(__n);
_M_end_of_storage = _M_start + __n;
_M_finish = uninitialized_copy(__first, __last, _M_start);
}
//上面有调用他的函数
template<class _InputIterator>
void _M_range_insert(iterator __pos, _InputIterator __first, _InputIterator __last, input_iterator_tag);
template<class _ForwardIterator>
void _M_range_insert(iterator __pos, _ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag);
};
//接下来是操作符重载
template<class _Tp, class _Alloc>
inline bool operator==(const vector<_Tp, _Alloc> &__x, const vector<_Tp, _Alloc> &__y) {
return __x.size() == __y.size() && equal(__x.begin(), __x.end(), __y.begin());
}
//在算法中有实现lexixxx的那个比较函数
template<class _Tp, class _Alloc>
inline bool operator<(const vector<_Tp, _Alloc> &__x, const vector<_Tp, _Alloc> &__y) {
return lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
}
//重载=
template<class _Tp, class _Alloc>
vector<_Tp, _Alloc> & vector<_Tp, _Alloc>::operator=(const vector<_Tp, _Alloc> &__x) {
if (this != &__x) {
const size_type __xlen = __x.size();
if (__xlen > capacity()) {
iterator __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
destory(_M_start, _M_finish);
destory(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __tmp;
_M_end_of_storage = _M_start + __xlen;
}
else if (__xlen <= size()) {
iterator __i = copy(__x.begin(), __x.end(), begin());
destory(__i, _M_finish);
}
else {
copy(__x.begin(), __x.begin() + size(), _M_start);
uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish);
}
_M_finish = _M_start + __xlen;
}
return *this;
}
//接下来应该全部都是insert的其他情况
template<class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp &__val) {
if (__n > capacity()) {
vector<_Tp, _Alloc> __tmp(__n, __val, get_allocator());
__tmp.swap(*this);
}
else if (__n > size()) {
fill(begin(), end(), __val);
_M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val);
}
else {
//size() >= __n
erase(fill_n(begin(), __n, __val), end());
}
}
template<class _Tp, class _Alloc>
template<class _InputIter>
void vector<_Tp, _Alloc>::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag) {
iterator __cur = begin();
for (; __first != __last && __cur != end(); ++__cur, ++__first)
*__cur = *__first;
//如果size > __n(__last-__first)，则擦除从超过__n个的元素
if (__first == __last)
erase(__cur, end());
//如果size < __n, 则向后插入少了的元素
else
insert(end(), __first, __last);
}
template<class _Tp, class _Alloc>
template<class _ForwardIter>
void vector<_Tp, _Alloc>::_M_assign_aux(_ForwardIter __first, _ForwardIter __last, forward_iterator_tag) {
size_type __len = 0;
//统计从__First到__last的元素个数
distance(__first, __last, __len);
if (__len > capacity()) {
//重新初始化并拷贝元素从first到last
iterator __tmp = _M_allocate_and_copy(__len, __first, __last);
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __tmp;
_M_end_of_storage = _M_finish = _M_start + __len;
}
else if (size() >= __len) {
iterator __new_finish = copy(__first, __last, _M_start);
destroy(__new_finish, _M_finish);
_M_finish = __new_finish;
}
else {
// size < __len <=capacity
_ForwardIter __mid = __first;
advance(__mid, size());
copy(__first, __mid, _M_start);
_M_finish = uninitialized_copy(__mid, __last, _M_finish);
}
}
template<class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp &__x) {
if (_M_finish != _M_end_of_storage) {
construct(_M_finish, *(_M_finish - 1));
++_M_finish;
_Tp __x_copy = __x;
copy_backward(__position, _M_finish - 2, _M_finish - 1);
*__position = __x_copy;
}
else {
const size_type __old_size = size();
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
try {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
construct(__new_finish, __x);
++__new_finish;
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
catch (...) {
destory(__new_start, __new_finish);
_M_deallocate(__new_start, __len);
}
destory(begin(), end());
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
template<class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::_M_insert_aux(iterator __position) {
if (_M_finish != _M_end_of_storage) {
construct(_M_finish, *(_M_finish - 1));
++_M_finish;
copy_backward(__position, _M_finish - 2, _M_finish - 1);
*__position = _Tp();
}
else {
const size_type __old_size = size();
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
try {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
construct(__new_finish);
++__new_finish;
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
catch (...) {
destroy(__new_start, __new_finish);
_M_deallocate(__new_start, __len);
}
destroy(begin(), end());
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
template<class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n,
const _Tp &__x) {
if (__n != 0) {
//剩余空间足够，无需重新开辟
if (size_type(_M_end_of_storage - _M_finish) >= __n) {
_Tp __x_copy = __x;
const size_type __elems_after = _M_finish - __position;
iterator __old_finish = _M_finish;
if (__elems_after > __n) {
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
_M_finish += __n;
copy_backward(__position, __old_finish - __n, __old_finish);
fill(__position, __position + __n, __x_copy);
}
else {
uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
_M_finish += __n - __elems_after;
uninitialized_copy(__position, __old_finish, _M_finish);
_M_finish += __elems_after;
fill(__position, __old_finish, __x_copy);
}
}
else {
const size_type __old_size = size();
const size_type __len = __old_size + max(__old_size, __n);
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
try {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
__new_finish = uninitialized_fill_n(__new_finish, __n, __x);
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
catch (...) {
destory(__new_start, __new_finish);
_M_deallocate(__new_start, __len);
}
destory(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_finish + __len;
}
}
}
template<class _Tp, class _Alloc>
template<class _InputIterator>
void vector<_Tp, _Alloc>::_M_range_insert(iterator __pos,
_InputIterator __first,
_InputIterator __last,
input_iterator_tag) {
for (; __first != __last; ++__first) {
__pos = insert(__pos, *__first);
++__pos;
}
}
template<class _Tp, class _Alloc>
template<class _ForwardIterator>
void vector<_Tp, _Alloc>::_M_range_insert(iterator __position,
_ForwardIterator __first,
_ForwardIterator __last,
forward_iterator_tag) {
if (__first != __last) {
size_type __n = 0;
distance(__first, __last, __n);
if (size_type(_M_end_of_storage - _M_finish) >= __n) {
const size_type __elems_after = _M_finish - __position;
iterator __old_finish = _M_finish;
if (__elems_after > __n) {
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
_M_finish += __n;
copy_backward(__position, __old_finish - __n, __old_finish);
copy(__first, __last, __position);
}
else {
_ForwardIterator __mid = __first;
advance(__mid, __elems_after);
uninitialized_copy(__mid, __last, _M_finish);
_M_finish += __n - __elems_after;
uninitialized_copy(__position, __old_finish, _M_finish);
_M_finish += __elems_after;
copy(__first, __mid, __position);
}
}
else {
const size_type __old_size = size();
const size_type __len = __old_size + max(__old_size, __n);
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
try {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
__new_finish = uninitialized_copy(__first, __last, __new_finish);
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
catch (...) {
destroy(__new_start, __new_finish);
_M_deallocate(__new_start, __len);
}
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
}
__STL_END_NAMESPACE
#endif // !__STL_VECTOR_H__

type_traits.h

#pragma once
#ifndef __STL_TYPE_TRAITS_H__
#define __STL_TYPE_TRAITS_H__
//两个true，flase结构体，作为是否重要的参数，方便萃取的时候使用
struct __true_type {
};
struct __false_type {
};
//模板类，萃取作为回答
template<class _Tp>
struct __type_traits {
typedef __true_type this_dummy_member_must_be_first;
/* Do not remove this member. It informs a compiler which automatically specializes __type_traits that this __type_traits template is special. It just makes sure that things work if an implementation is using a template called __type_traits for something unrelated. */
/*
不要移除该成员。它通知自动专一__type_traits的编译器这个__type_traits模板是特殊的。它只是确保如果一个实现使用了一个名为__type_traits的模板来处理一些不相关的事情，那么事情能够正常工作。*/
/*
为了让编译器自动生成该类的特定类型专门化，应该遵守以下限制:
-如果你愿意，你可以重新排列下面的成员
-如果您愿意，您可以删除以下任何成员
—不能在没有创建相应成员的情况下重命名成员
编译器中的名称更改
-你添加的成员将像普通成员一样对待，除非
在编译器中添加适当的支持。
*/
//默认构造器 不重要吗，  不是，所以是重要的，
typedef __false_type has_trivial_default_constructor;
typedef __false_type has_trivial_copy_constructor;
typedef __false_type has_trivial_assignment_operator;
typedef __false_type has_trivial_destructor;
typedef __false_type is_POD_type;
};
//以下都是一些偏特化版本/特化版本，定义
template<> struct __type_traits<bool> {
typedef __true_type    has_trivial_default_constructor;
typedef __true_type    has_trivial_copy_constructor;
typedef __true_type    has_trivial_assignment_operator;
typedef __true_type    has_trivial_destructor;
typedef __true_type    is_POD_type;
};
template<> struct __type_traits<char> {
typedef __true_type    has_trivial_default_constructor;
typedef __true_type    has_trivial_copy_constructor;
typedef __true_type    has_trivial_assignment_operator;
typedef __true_type    has_trivial_destructor;
typedef __true_type    is_POD_type;
};
template<> struct __type_traits<signed char> {
typedef __true_type    has_trivial_default_constructor;
typedef __true_type    has_trivial_copy_constructor;
typedef __true_type    has_trivial_assignment_operator;
typedef __true_type    has_trivial_destructor;
typedef __true_type    is_POD_type;
};
template<> struct __type_traits<unsigned char> {
typedef __true_type    has_trivial_default_constructor;
typedef __true_type    has_trivial_copy_constructor;
typedef __true_type    has_trivial_assignment_operator;
typedef __true_type    has_trivial_destructor;
typedef __true_type    is_POD_type;
};
template<> struct __type_traits<short> {
typedef __true_type    has_trivial_default_constructor;
typedef __true_type    has_trivial_copy_constructor;
typedef __true_type    has_trivial_assignment_operator;
typedef __true_type    has_trivial_destructor;
typedef __true_type    is_POD_type;
};
template<> struct __type_traits<unsigned short> {
typedef __true_type    has_trivial_default_constructor;
typedef __true_type    has_trivial_copy_constructor;
typedef __true_type    has_trivial_assignment_operator;
typedef __true_type    has_trivial_destructor;
typedef __true_type    is_POD_type;
};
template<> struct __type_traits<int> {
typedef __true_type    has_trivial_default_constructor;
typedef __true_type    has_trivial_copy_constructor;
typedef __true_type    has_trivial_assignment_operator;
typedef __true_type    has_trivial_destructor;
typedef __true_type    is_POD_type;
};
template<> struct __type_traits<unsigned int> {
typedef __true_type    has_trivial_default_constructor;
typedef __true_type    has_trivial_copy_constructor;
typedef __true_type    has_trivial_assignment_operator;
typedef __true_type    has_trivial_destructor;
typedef __true_type    is_POD_type;
};
template<> struct __type_traits<long> {
typedef __true_type    has_trivial_default_constructor;
typedef __true_type    has_trivial_copy_constructor;
typedef __true_type    has_trivial_assignment_operator;
typedef __true_type    has_trivial_destructor;
typedef __true_type    is_POD_type;
};
template<> struct __type_traits<unsigned long> {
typedef __true_type    has_trivial_default_constructor;
typedef __true_type    has_trivial_copy_constructor;
typedef __true_type    has_trivial_assignment_operator;
typedef __true_type    has_trivial_destructor;
typedef __true_type    is_POD_type;
};
template<> struct __type_traits<long long> {
typedef __true_type    has_trivial_default_constructor;
typedef __true_type    has_trivial_copy_constructor;
typedef __true_type    has_trivial_assignment_operator;
typedef __true_type    has_trivial_destructor;
typedef __true_type    is_POD_type;
};
template<> struct __type_traits<unsigned long long> {
typedef __true_type    has_trivial_default_constructor;
typedef __true_type    has_trivial_copy_constructor;
typedef __true_type    has_trivial_assignment_operator;
typedef __true_type    has_trivial_destructor;
typedef __true_type    is_POD_type;
};
template<> struct __type_traits<float> {
typedef __true_type    has_trivial_default_constructor;
typedef __true_type    has_trivial_copy_constructor;
typedef __true_type    has_trivial_assignment_operator;
typedef __true_type    has_trivial_destructor;
typedef __true_type    is_POD_type;
};
template<> struct __type_traits<double> {
typedef __true_type    has_trivial_default_constructor;
typedef __true_type    has_trivial_copy_constructor;
typedef __true_type    has_trivial_assignment_operator;
typedef __true_type    has_trivial_destructor;
typedef __true_type    is_POD_type;
};
template<> struct __type_traits<long double> {
typedef __true_type    has_trivial_default_constructor;
typedef __true_type    has_trivial_copy_constructor;
typedef __true_type    has_trivial_assignment_operator;
typedef __true_type    has_trivial_destructor;
typedef __true_type    is_POD_type;
};
//一个模板函数
template<class _Tp> 
struct _Is_integer {
typedef __false_type _Integral;
};
//剩余是他的特化和偏特化
template<>
struct _Is_integer<int> {
typedef __true_type _Integral;
};
template<>
struct _Is_integer<unsigned int> {
typedef __true_type _Integral;
};
template<>
struct _Is_integer<bool> {
typedef __true_type _Integral;
};
template<>
struct _Is_integer<char> {
typedef __true_type _Integral;
};
template<>
struct _Is_integer<signed char> {
typedef __true_type _Integral;
};
template<>
struct _Is_integer<unsigned char> {
typedef __true_type _Integral;
};
template<>
struct _Is_integer<short> {
typedef __true_type _Integral;
};
template<>
struct _Is_integer<unsigned short> {
typedef __true_type _Integral;
};
template<>
struct _Is_integer<long> {
typedef __true_type _Integral;
};
template<>
struct _Is_integer<unsigned long> {
typedef __true_type _Integral;
};
#endif // !__STL_TYPE_TRAITS_H__

main.cpp

#include "stl_vector.h"
#include<iostream>
#include<stdio.h>
//这里一定要指定namespace
using namespace ding_stl;
int main() {
vector<char> v2;
v2.push_back('h');
v2.push_back('e');
v2.push_back('l');
v2.push_back('l');
v2.push_back('o');
v2.push_back(',');
v2.push_back('w');
v2.push_back('o');
v2.push_back('r');
v2.push_back('l');
v2.push_back('d');
printf("%d",v2.capacity());
printf("\n");
printf("%d", v2.empty());
printf("\n");
printf("%d", v2.size());
printf("\n");
for (vector<char>::iterator m = v2.begin(); m != v2.end(); m++)    
{
std::cout << *m ; 
}
return 0;
}