精华内容
下载资源
问答
  • C++STL库中sort函数用法
    千次阅读 多人点赞
    2018-08-01 20:22:36

      首先sort函数因为它使用的排序方法是类似于快排的方法,时间复杂度为n*log2(n),执行效率较高。所以一般数据量很大的数据排序都可以用它来进行。

    1)Sort()函数的头文件为#include<algorithm>    

    (2)Sort函数有三个参数:

    第一个是要排序的数组的起始地址。

    第二个是结束地址(最后一位要排序的地址)

    第三个参数是排序的方法,可以从小到大也可以是从大到小,当不写第三个参数时默认的排序方法时从小到大排序

    1.对数组的排序:

    分为升序和降序,先来看升序,

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int a[10]={9,5,7,8,4,1,2,6,3,10};
        sort(a,a+10);//当最后一个参数不写的时候,默认为升序排序;
        for(int i=0;i<10;i++)
            cout<<a[i]<<" ";
    }

    排序结果为1  2 3 4 5 6  7 8 9 10;

    降序:

    降序的话有两种方式,第一是直接调用函数,C++标准库的强大功能完全可以解决这个问题。greater<数据类型>()  //降序排序

    例如: sort(a,a+10,greater<int>());就是降序排序;还有就是直接写个cmp比较函数来完成:

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int a[10]={9,5,7,8,4,1,2,6,3,10};
        sort(a,a+10,greater<int>());//降序排序;
        for(int i=0;i<10;i++)
            cout<<a[i]<<" ";
    }
    

    写比较函数:

    #include<bits/stdc++.h>
    using namespace std;
    bool cmp(int a,int b)
    {
        return a>b;  //如果是return a<b 的话就是升序排序;
    }
    int main()
    {
        int a[10]={9,5,7,8,4,1,2,6,3,10};
        sort(a,a+10,cmp);//降序排序;
        for(int i=0;i<10;i++)
            cout<<a[i]<<" ";
    }
    

    最后就是对结构体变量的排序了:

    #include<bits/stdc++.h>
    using namespace std;
    struct sdut
    {
      int y;
    }a[123461];
    bool cmp(sdut a,sdut b)
    {
        return a.y<b.y;//升序排列;a>b为降序排列;
    }
    int main()
    {
        int m,n,t;
        while(cin>>t)
        {
            for(int i=0;i<t;i++)
                cin>>a[i].y;
            sort(a,a+t,cmp);
            for(int i=0;i<t;i++)
                cout<<a[i].y<<" "<<endl;
        }
    }
    

     

    更多相关内容
  • C++STL库开发文档

    2020-11-25 14:04:44
    查询一些熟悉又陌生的方法的参数与返回值、
  • c++中常用模板头文件及其源代码,例如<stl_queue.h>,<stl_vector.h>,<stl_map.h>等
  • C++ STL库应用汇总

    2020-12-20 20:18:13
    1、std::max_element的使用 std::min_element类似,求最小 #include #include #include bool myfn( int i, int j ) { return i < j> zx {1, 2, 3, 8, 5, 44}; //方法一 调用函数 auto biggest = std::max_
  • C++STL库.pdf

    2014-05-29 23:21:09
    里面包含vector,map,list,set等用法
  • c++stl标准源码

    2017-12-07 10:58:45
    c++ stl The Standard Template Library, 容器(Container) 迭代器(Iterator) 算法(Algorithm)仿函数(Function object)迭代适配器(Adaptor)空间配制器(allocator)
  • stl库手册_c++.rar

    2021-04-16 10:02:27
    用来查找算法 如 istream::read // read a file into memory #include #include using namespace std; int main () { int length; char * buffer; ifstream is; is.open ("test.txt", ios::binary );...
  • c++ STL 使用示例

    2018-04-18 13:18:42
    C++ STL库使用示例, 包含了基本上所有C++库函数使用, 是C++开发常用必备手册
  • C++模板与STL库介绍

    2019-03-18 16:16:29
    C++模板与STL库介绍 非常详细
  • C++ stl库 手写 源码分析

    多人点赞 2021-08-11 20:32:44
    C++ stl库 手写前言序列式关联式容器适配器ListVector 函数dequestringstack queuebitset关联式容器 set multisetmultiset算法库仿函数 前言 stl版本 abcd,四个版本, 接口肯定是一样的 代码复用性强,效率高,通用...

    C++ stl库 手写

    前言

    stl版本 abcd,四个版本,

    接口肯定是一样的

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

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

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

    image-20210811143055383

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

    仿函数就是一个对象

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

    image-20210811143213238

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

    image-20210811143246191

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

    序列式

    list,vector deque

    关联式

    set map multset multmap hashset hashmap

    容器适配器

    stack queue

    List

    双向链表

    image-20210811145004064

    头节点不计入

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

    你可以通过1 找到2,

    image-20210811151001076

    开辟出来都是0

    image-20210811151147710

    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 函数

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

    链表不是连续的

    image-20210811152638169

    last 放入元素的下一个,

    first 第一个

    end 空间结束的下一个

    image-20210811152909245

    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;
    }
    

    查看容量

    image-20210811154050527

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

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

    image-20210811154318026

    image-20210811154327946

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

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

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

    image-20210811155508758

    #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没有容量这一说

    想往哪儿插往哪儿插

    image-20210811160809658

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

    竖线叫中控器,很麻烦

    默认构造

    image-20210811164817093

    #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;
    }
    

    image-20210811165129702

    #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前面插入

    image-20210811165756164

    插入方法放在迭代器前面

    string

    image-20210811170220506

    #include<iostream>
    #include<string>
    
    using namespace std;
    void main() {
    	string str = "hello";
    	cout << "str = "<<str << endl;
    
    }
    

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

    iterator

    image-20210811170604590

    #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;
    }
    

    image-20210811170752539

    反向

    #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

    大小,长度, 容量

    image-20210811171002793

    size和length差不多,

    为什么容量不一样

    image-20210811171032830

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

    多开辟,未必会使用完

    resize(20) 会填充/0 ,然后capacity 会加上原来的大小,变大,

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

    image-20210811171806625

    指针和 数组的区别,

    image-20210811171817254

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

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

    image-20210811171942613

    替换,对吧,

    stack queue

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

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

    image-20210811172715621

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

    栈:先进后出,

    只让头插,头删

    或者

    只让尾插,尾删

    队列,先进先出

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

    image-20210811173449000

    #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

    image-20210811173611734

    #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;
    }
    

    image-20210811173853294

    先进先出

    #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;
    }
    

    image-20210811174404028

    front 是为了返回第一个数值

    bitset

    每一个元素只能是0和1

    他叫位图

    image-20210811175212398

    #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

    image-20210811180134874

    关联式容器 set multiset

    注重,快速,高效检索

    set multiset map multimap

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

    rbtree 动态平衡树

    二叉排序树

    set map

    如何查询,(也就是排序)

    image-20210811181301431

    image-20210811181305281

    #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里面放进去默认排好序了

    image-20210811182102528

    count 查看有12 ,只有一个

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

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

    我们来看一下,查找

    image-20210811183032777

    这个,可以重载小于号

    multiset

    image-20210811182459007

    可以重复

    #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()

    image-20210811192803044

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

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

    operator()(a,b)

    image-20210811193634422

    #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

    image-20210811194328717

    multipiles

    image-20210811194405649

    乘法

    仿函数如何结合算法呢?

    image-20210811194648151

    先打印出来

    vector有一个排序方法

    默认从小到大排序

    image-20210811195436561

    image-20210811195522257

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

    image-20210811195541411

    #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;
    }
    

    自己实现一个仿函数

    image-20210811201218951

    正常排序

    image-20210811201227702

    s我们上面使用模板

    image-20210811201351249

    添加模板类

    下面我们使用迭代器,

    #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;
    	}
    	
    }
    

    image-20210811203020897

    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(模板)

    必须要正确的使用模板

    image-20210819102039703

    image-20210819102440359

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

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

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

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

    image-20210819102709081

    using namespace std

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

    或者单个打开

    using std::cout

    image-20210819102914506

    https://cplusplus.com/

    cppreference.com

    gcc.gnu.org

    Test-STL.cpp

    
    

    STL 六大部件

    容器(containers)

    分配器(allocators)

    算法(algorithms)

    迭代器(iterators)

    适配器(Adapters)

    仿函数(Functors)

    最重要的是,容器和算法

    image-20210819103655426

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

    分配器去支持容器,

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

    模板编程:数据在容器里,

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

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

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

    也就是做了转换~

    image-20210819105544284

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

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

    也是int

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

    count_if 算法。

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

    容器都有着begin,end函数

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

    image-20210819110938972

    哪一个复杂度最低呢?

    不知道咯

    image-20210819112703851

    前闭后开区间

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

    不一定是连续空间~

    所有的容器都有iterator的哟~

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

    *,++。–。->

    image-20210819113507202

    auto 什么类型呢?,你自己想,我不给你写

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

    image-20210819114138223

    可以适度使用auto

    所有的容器

    image-20210819114243859

    容器的分类

    序列式,

    关联式(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

    image-20210819120722381

    一个篮子有一个链表

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

    有一些算法的~

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

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

    array

    image-20210819143515886

    get_a_target_Long

    我选个容器,

    get_a_target_string()

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

    模拟放入object,

    image-20210819143749691

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

    image-20210819143957960

    image-20210819142632222

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

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

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

    vector

    image-20210819144359621

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

    每个测试,每个片

    image-20210819144700776

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

    push back 从尾巴放

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

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

    abort() 退出程序

    103 106 行夹住时间点

    image-20210819150159927

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

    调用c++ 库中的 find

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

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

    binary search

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

    但是,结果,find 0毫秒

    qsort sort后,查找 2毫秒

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

    list

    image-20210819151358870

    list,一个一个加

    list有个特殊的,max_size()

    排序一遍,两秒多

    image-20210819151958764

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

    forwoard_list

    image-20210819152141848

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

    push_front 会方便点

    没有back,没有size函数

    这里使用全局的find,

    slist

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

    image-20210819152459213

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

    deque

    双向开容器,

    image-20210819152646731

    连续的假象

    使用者感觉是连续的,

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

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

    每次扩充一个buffer,

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

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

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

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

    使用容器 stack

    栈,一端进,同一个口出

    先进后出

    push放元素,pop出元素

    image-20210819154213995

    queue

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

    先进先出

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

    他的动作也是push pop

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

    multiset

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

    落在树里是有一定规则的

    image-20210819155444759

    调用了下,size,max_size

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

    可能安插的时候会慢点

    multimap

    有key和value

    用key来找value

    image-20210819155954432

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

    insert 我们自己组合key和value,

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

    着利用容器的find

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

    unordered_multiset

    image-20210819163626791

    bucket_count() 篮子个数~

    源码分布

    include里面

    后面

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

    模板编程

    OOP 和 GP

    面向对象编程 和 泛型编程

    image-20210819181324776

    OOP将data和method合在一起

    GP是data 和method分开

    image-20210819181419969

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

    GP的好处

    image-20210819181709896

    image-20210819181738935

    OOP

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

    image-20210819182316821

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

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

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

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

    image-20210819183150679

    max有两个版本,

    我们可以定义按什么比

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

    自己定义的strlog函数

    操作符重载 operator overloading

    image-20210820134849803

    ++i

    i++

    一个操作数,两个操作数的

    image-20210820134929918

    举一个例子

    链表的迭代器

    image-20210820134936866

    她一定会重载这四个

    模板类class template

    类模板

    image-20210820135205272

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

    函数模板function template

    image-20210820141342579

    他会自动推导,T为stone

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

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

    image-20210820141825440

    成员模板

    目前不会看到

    Specialization 特化

    泛化之外写特化

    image-20210820144308605

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

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

    image-20210820144707326

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

    image-20210820144733277

    _STL_TEMPLATE_NULL 这里typedef template

    image-20210820144951534

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

    这个特化算全特化,

    Partial Specialization 偏特化

    image-20210820145131769

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

    另外一个是范围的偏特化

    image-20210820145318382

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

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

    image-20210819163744535

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

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

    原来的篮子就会被打散

    最大的载重因子不会变 1

    image-20210819164252922

    我们试试find

    set

    image-20210819170448438

    key==value

    insert进去即可

    32768 我们从0-32767

    正好都放了

    map

    image-20210819170702150

    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

    image-20210819174455805

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

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

    这些分配器在__gnu里面

    image-20210819174622439

    第一个内存池,第二个bitmap_allocator

    image-20210819174846590

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

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

    image-20210819175125130

    这里的 1 是一个int,

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

    new搭配delete,malloc和free

    deallocate(p,1) 还给她创建的指针,还要还当初要的几个

    源码分布

    include里面

    后面

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

    模板编程

    OOP 和 GP

    面向对象编程 和 泛型编程

    image-20210819181324776

    OOP将data和method合在一起

    GP是data 和method分开

    image-20210819181419969

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

    GP的好处

    image-20210819181709896

    image-20210819181738935

    OOP

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

    image-20210819182316821

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

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

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

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

    image-20210819183150679

    max有两个版本,

    我们可以定义按什么比

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

    自己定义的strlog函数

    操作符重载 operator overloading

    image-20210820134849803

    ++i

    i++

    一个操作数,两个操作数的

    image-20210820134929918

    举一个例子

    链表的迭代器

    image-20210820134936866

    她一定会重载这四个

    模板类class template

    类模板

    image-20210820135205272

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

    函数模板function template

    image-20210820141342579

    他会自动推导,T为stone

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

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

    image-20210820141825440

    成员模板

    目前不会看到

    Specialization 特化

    泛化之外写特化

    image-20210820144308605

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

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

    image-20210820144707326

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

    image-20210820144733277

    _STL_TEMPLATE_NULL 这里typedef template

    image-20210820144951534

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

    这个特化算全特化,

    Partial Specialization 偏特化

    image-20210820145131769

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

    另外一个是范围的偏特化

    image-20210820145318382

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

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

    分配器allocator

    效率包括速度和空间

    先谈谈 operator new() 和malloc()

    c 上面最后都会跑到malloc

    image-20210820150327912

    image-20210820150612432

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

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

    vc6stl allocator的使用

    image-20210820150833461

    默认使用allocator

    image-20210820150924083

    也是调用的malloc

    image-20210820151158564

    allocator() 这样就是一个object

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

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

    那么归还呢?

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

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

    BC5 STL对allocator的使用

    我们得查他一下typedef

    image-20210820152900431

    也是默认用的allocator

    image-20210820152944639

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

    image-20210820153354537

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

    G2.9Stl 对allocator的使用

    image-20210820155130355

    他补了一个注释

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

    image-20210820155336271

    image-20210820155634610

    他默认使用的是alloc

    image-20210820155742446

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

    他要尽量减少malloc次数,减少额外开销(也就是cookie)。

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

    image-20210820155931531

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

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

    按照倍数找链表负责

    image-20210820160305920

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

    G4.9 STL 对allocator的使用

    image-20210820161353866

    image-20210820161420918

    他新版本直接没有alloc了

    image-20210820161502231

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

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

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

    image-20210820161806791

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

    image-20210820162202751

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

    后退是衍生层

    heap是一个特殊的容器

    image-20210820165550795

    老师看了所有的source code

    list大小都变了2.9和4.9版本

    容器list

    最具代表性的

    image-20210820170759970

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

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

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

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

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

    iterator

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

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

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

    image-20210820172818431

    先看看用法

    image-20210820173110848

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

    传三个模板参数,好神奇!

    image-20210820173321012

    节点的设计

    image-20210820173331380

    一定要有五个typedef

    一大组的function

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

    这里有两个加加

    image-20210820173542045

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

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

    没参数 有int(没意义的)

    我们来看++的动作

    image-20210820173942555

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

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

    后加加有啥区别呢?

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

    image-20210820174738259

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

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

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

    (拷贝构造函数和赋值运算符)

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

    image-20210820175953076

    然后后佳佳调用了前加加

    image-20210820180418009

    这样就会被拷贝复制

    就会调用拷贝构造函数

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

    image-20210820180700341

    为什么呢?

    image-20210820180801330

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

    image-20210820180818125

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

    image-20210820181103551

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

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

    image-20210820181140527

    -> 和 *差不多

    image-20210820181552015

    五个typedef是一定要的哟

    image-20210820181747090

    这个void为什么呢?

    image-20210820181758398

    这三个参数为什么呢?

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

    我们来看新的G4.9

    G2.9 vs G4.9

    image-20210820181916079

    image-20210820182001299

    我们上述的bug都更新了

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

    容器list

    G4.9 很麻烦,很复杂

    G2.9他只是一个class

    G4.9 直接一堆继承

    image-20210820182840873

    image-20210820183023307

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

    image-20210820183227101

    begin,end指向

    image-20210820183245612

    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)]

    image-20210822162218192

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

    traits 用来萃取出iterator的特性

    他有什么特性呢?

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

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

    image-20210822151147977

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

    image-20210822151300902

    他想萃取出iterator的分类

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

    这就叫iterator-category

    image-20210822151413331

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

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

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

    一共五种

    reference pointer 这两个没有使用

    iterator_category()

    Difference_type

    Value_type

    必须要提出五种

    image-20210822151827216

    image-20210822151928228

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

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

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

    ptfdiff_t 用这个可能是一个unsign int

    链表的value——type是什么?

    链表元素是t 这里就是t

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

    image-20210822152359328

    如果c++的指针,那么如何回答问题呢?

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

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

    还是普通的指针传进来

    image-20210822152637754

    要加一个萃取机,

    iterator-traits

    image-20210822152835143

    间接问,放到traits里,让他去问,(中间层)

    指针都到了2和3

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

    image-20210822153316826

    这两个偏特化,为什么都是t呢?

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

    因此需要都是t

    完整的iterator——traits

    image-20210822153616224

    上面就是五个完整的问题

    那么指针如何分类嗯?

    指针的话肯定是random—access

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

    各种各样的traits

    image-20210822161938299

    越加越多,

    vector深度搜索

    容器vector

    image-20210822163910784

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

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

    哪个环境也是两倍成长

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

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

    每一个容器有begin,end。size

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

    size永远不会变

    两次函数调用~

    capacity 容量,

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

    image-20210822164833052

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

    里面又做了一次检查,看看空间是否没了(其他函数调用会用到)

    image-20210822165032142

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

    判断,旧的大小是多少。

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

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

    分配好空间后,这里有trycatch

    image-20210822165210088

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

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

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

    vector iterator

    image-20210822170100128

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

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

    当使用vector的时候

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

    他这里写了三个的解答

    他直接把iterator 丢给traits,

    image-20210822170418385

    一个泛化,两个偏特化,

    五种类型,他的category都是randomaccess

    g4.9 变成了魔鬼

    image-20210822171106410

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

    image-20210822173312321

    image-20210822173324933

    容器array

    为什么要包装容器呢?

    盲猜一手iterator

    TR1 容易读

    image-20210822174343462

    struct和class差不多的

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

    image-20210822174508364

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

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

    不是0,指定多少就多少

    image-20210822174428223

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

    array没有构造和xigou函数

    image-20210822174617119

    array本身是一个连续的空间

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

    image-20210822174732552

    一部分针对指针,一部分针对class

    我们来看4.9

    g4.9 版本

    image-20210822174859092

    image-20210822174956393

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

    image-20210822175027209

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

    容器forward—list

    单向链表,和list差不多,

    image-20210822175130109

    image-20210822175140965

    容器deque

    image-20210822225114183

    image-20210822225122933

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

    那么deque怎么做》?

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

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

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

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

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

    image-20210822230345526

    其中的node就是指控制中心

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

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

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

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

    first lat不会变,cur变动,

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

    image-20210822230825042

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

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

    begin传回start end传回finish

    image-20210822230920524

    G2.9

    他的数据部分

    image-20210822230955027

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

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

    map类型是 T**

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

    image-20210822231216592

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

    参数4*4=16

    一个deque 本身,就是40 字节

    image-20210822231415905

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

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

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

    image-20210822231515787

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

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

    deque iterator

    image-20210822231905038

    我们来看看迭代器。

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

    自己的分类是 random accesss iterator

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

    deque::insert()

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

    image-20210822232145662

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

    先判断,是起点么?最前端,直接pushfront

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

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

    image-20210822232424141

    判断往头,往尾,谁短

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

    大于中点,靠近尾端,

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

    deque 如何模拟连续空间

    image-20210823102225115

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

    image-20210823103058997

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

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

    image-20210823103259209

    image-20210823103734088

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

    image-20210823104558653

    加加和减减

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

    image-20210823104814341

    first last需要重新设置

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

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

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

    image-20210823105426637

    image-20210823105709575

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

    G4.9

    image-20210823110107813

    image-20210823110330342

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

    让左边和右边有空余

    image-20210823112137667

    容器queue

    image-20210823112229427

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

    image-20210823112400049

    image-20210823112501521

    都是转调用

    image-20210823112625000

    当然deque会快

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

    image-20210823113013868

    stack可以选择vector,queue不行

    vector没有popfront

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

    image-20210823113259732

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

    编译会通过哟

    不会做全面性的检查

    容器rb-tree

    关联式容器

    用key去寻找value

    image-20210823114354352

    高度平衡的二分树

    排序规则有利于search 和insert

    红黑树是一个sorted排序状态

    begin最左边,end最右边

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

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

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

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

    image-20210823115426140

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

    image-20210823115541313

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

    image-20210823115721832

    红黑树的实现,

    同时有五个模板参数

    image-20210823115750179

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

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

    image-20210823120105526

    三个数据

    image-20210823120253363

    image-20210823120300100

    header指针,

    函数,可能是仿函数~

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

    image-20210823134208997

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

    key of value

    image-20210823134445164

    compare 是 他的比大小的方式

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

    容器rb—tree 用例

    image-20210823134806515

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

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

    G4.9版本如下

    image-20210823135255680

    image-20210823135553513

    为了复合OOP

    面向对象编程,handle-----body, body是一个实现类

    容器set,multiset

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

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

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

    image-20210823141947516

    set的key必须独一无二的,他调用insert-unique()

    multiset 调用的是insert-equal()

    容器set

    image-20210823142443003

    内含一个红黑树

    image-20210823143147414

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

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

    image-20210823144838337

    image-20210823144904724

    image-20210823145810068

    VC6 里面的,写在了内部,

    容器map ,multimap

    每个元素是value 包含key+value

    一样会自动排序

    image-20210823150503415

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

    image-20210823150935218

    map要求放入四个参数

    image-20210823150953928

    image-20210823151031507

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

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

    key of value

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

    pair 包裹了key t

    image-20210823151508856

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

    容器map in vc6

    image-20210823151653990

    他select1st的函数

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

    image-20210823152435437

    放进去100w

    使用自己的find,很方便

    容器map,独特的operator[]

    image-20210823152844275

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

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

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

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

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

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

    image-20210823153458385

    括号和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;
    }
    
    展开全文
  • 在本篇文章里小编给大家整理的是关于c++STL库容器之集合set代码实例,需要的朋友们可以参考下。
  • 定义 头文件 定义 常用函数

    定义

    队列和栈一样,也属于动态集合。但是队列的修改是按先进先出的原则进行的。在队列中,允许插入的一端称为队尾,允许删除的一端称为队头

    队列的示意图如下:
    在这里插入图片描述

    头文件

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

    定义

    queue<int>q;
    

    常用函数

    q.push();//在队尾添加一个元素
    q.pop(); //删除队头的第一个元素
    q.size();//返回队列中元素的个数
    q.empty();//判断队列q是否为空队列
    q.front();返回队列中的第一个元素(即队头元素)
    q.back();//返回队列中的最后一个元素(即队尾元素)

    #include <iostream>
    #include <queue>
    using namespace std;
    
    int main()
    {
       queue<int>q;
       q.push(1);
       q.push(2);
       q.push(3);
       q.push(4);
       //现在的队列中的元素为:1,2,3,4
    
       cout<<q.front()<<endl;//运算结果:1
       cout<<q.back()<<endl;//运算结果:4
       cout<<q.size()<<endl;//运算结果:4
    
       while(!q.empty())
       {
          cout<<q.front()<<' ';
          q.pop();//队列和栈一样不能遍历,输出一个删除一个
       }
       return 0;
    }
          
    

    上述代码最终运算结果如下:
    在这里插入图片描述

    展开全文
  • C++_标准模板(STL) pdf 高清版 C++ 标准模板(STL)
  • C++ stl 源代码下载

    2017-11-21 11:03:18
    C++ 的 stl 源代码下载,熟悉C++stl库的原理和机制, 了解array等数据结构的内在实现
  • STL是Standard Template Library的简称,中文名标准模板库,是由Alexander Stepanov、Meng Lee和David R Musser在惠普...STL库由于其对跨平台,对标准C++的支持,开源,高效等优点,如今已经被广泛运用于企业级开发。
  • C++ STL标准

    千次阅读 2020-05-23 11:32:58
    STLC++ 标准程序的核心。STL 内的所有组件都由模板构成,其元素可以是任意型别。程序员通过选用恰当的群集类别调用其成员函数和算法中的数据即可,但代价是 STL 晦涩难懂。 STL 组件主要包括容器,迭代器、...

    STL 组件

    STL 是 C++ 标准程序库的核心。STL 内的所有组件都由模板构成,其元素可以是任意型别。程序员通过选用恰当的群集类别调用其成员函数和算法中的数据即可,但代价是 STL 晦涩难懂。

    STL 组件主要包括容器,迭代器、算法和仿函数。

    容器
    容器即用来存储并管理某类对象的集合。每一种容器都有其优点和缺点。为满足程序的各种需求,STL 准备了多种容器类型,容器可以是 arrays 或是 linked lists,或者每个元素有特别的键值。
    迭代器
    迭代器用于在一个对象群集的元素上进行遍历动作。对象群集可能是容器,也可能是容器的一部分。
    迭代器的主要用途是为容器提供一组很小的公共接口。利用这个接口,某项操作可以行进至群集内的下一个元素。每种容器都提供了各自的迭代器。迭代器了解该容器的内部结构,所以能够正确行进。迭代器的接口和一般指针类似。
    算法
    算法用来处理群集内的元素,可以出于不同目的搜寻、排序、修改、使用那些元素。所有容器的迭代器都提供一致的接口,通过迭代器的协助,算法程序可以用于任意容器。
    STL 的一个特性是将数据和操作分离。数据由容器类别加以管理,操作则由可定制的算法定义。迭代器在两者之间充当“粘合剂”,以使算法可以和容器交互运作。
    STL 的另一个特性即组件可以针对任意型别运作。“标准模板库”这一名称即表示“可接受任意型别”的模板,并且这些型别均可执行必要操作。
    在 STL 中,容器又分为序列式容器和关联式容器两大类,而迭代器的功能主要是遍历容器内全部或部分元素的对象。迭代器可划分为 5 种类属,这 5 种类属归属两种类型:双向迭代器和随机存取迭代器。
    SIL 中提供的算法包括搜寻、排序、复制、重新排序、修改、数值运算等。
    仿函数
    STL中大量运用了仿函数。仿函数具有泛型编程强大的威力,是纯粹抽象概念的例证。

    STL基本结构

    在这里插入图片描述
    STL 中已经提供的主要容器:

    • vector :一种向量。
    • list :一个双向链表容器,完成了标准 C++ 数据结构中链表的所有功能
    • queue :一种队列容器,完成了标准 C++ 数据结构中队列的所有功能。
    • stack :一种栈容器,完成了标准 C++ 数据结构中栈的所有功能。
    • deque :双端队列容器,完成了标准 C++ 数据结构中栈的所有功能。
    • priority_queue :一种按值排序的队列容器。
    • set :一种集合容器。
    • multiset :一种允许出现重复元素的集合容器。
    • map <key, val>:一种关联数组容器。
    • multimap <key, val>:一种允许出现重复 key 值的关联数组容器。

    使用实例:

    #include<vector>//容器头文件
    #include<algorithm>//算法头文件
    #include<functional>//函数头文件
    #include<iostream>//标准输入输出头文件
    
    using namespace std;// 引入 std(输入和输出) 命名空间
    
    
    int main(void)
    {
    	int ia[6]{ 17,90,50,22,47,33 };
    
    	vector<int, allocator<int>> vi(ia, ia + 6);
    	cout << count_if(vi.begin(), vi.end(), not1(bind2nd(less<int>(), 40))); //输出大于或等于40的元素个数
    
    	return 0;
    }
    

    在这里插入图片描述
    各个组件协作
    在这里插入图片描述
    容器与算法 的组合使用 无法避免 复杂度 :线性的,指数的,对数的等。取决于对数据的具体操作和容器选择。
    在这里插入图片描述
    在这里插入图片描述

    STL的区间概念:

    在这里插入图片描述

    STL 容器的结构与分类:

    序列容器 Sequence Containers:
    在这里插入图片描述
    关联容器 (元素包含 (Key,Value)) Associative Containers:
    在这里插入图片描述
    不定序容器 (元素位置不固定) Unordered Containers:
    在这里插入图片描述

    展开全文
  • C++STL手册.rar

    2021-09-23 14:56:08
    stl查询手册
  • C++ STL文档合集.rar

    2014-11-06 10:59:46
    文档列表: C++_STL详解.ppt C++类模板与STL编程.ppt C++中vector使用范例.pdf C++Vector用法_合集.doc C++_中的map容器.pdf C+++中的set容器.pdf
  • C++ STL库函数总结(纯手打,主要偏向ACM竞赛方面使用)
  • c++标准库stl帮助文档

    2012-11-05 15:32:08
    c++标准库stl帮助文档,对初学stl十分有用
  • STLC++ 标准的一部分,不用单独安装。 C++ 对模板(Template)支持得很好,STL 就是借助模板把常用的数据结构及其算法都实现了一遍,并且做到了数据结构和算法的分离。例如,vector 的底层为顺序表(数组),...
  • C++ STL中文版.pdf

    2018-02-27 14:08:20
    STL(标准模板)是在惠普实验室中开发的,已纳入ANSI/ISO C++标准。其中的代码采用模板类及模板函数的方式,可以极大地提高编程效率。本书由P.J. Plauger等四位对C++ STL的实现有着卓越贡献的大师撰写,详细讨论了...
  • 经典图书C++ STL 标准程序开发指南(第2版)配套源代码
  • c++stl帮助文档

    2018-05-28 12:38:58
    标准模板STL是一个C++库的容器类,算法和迭代器;它提供了许多的计算机科学的基本算法和数据结构。STL是一个通用,意味着它的组件被大量参数化:STL中的几乎每个组件都是模板。你应该确保你了解模板在C++之前...
  • C++STL常用的详解和应用

    千次阅读 多人点赞 2019-04-06 21:26:17
    STL(Standard Template Library,标准模板)是惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。现在虽说它主要出现在C++中,但在被引入...
  • C++ STL标准程序开发指南.第2版.闫常友.pdf 扫描版
  • C++ STL详解超全总结(快速入门STL)

    千次阅读 多人点赞 2021-02-24 16:12:25
    一、 c++ STL常用内容总结 文章目录一、 c++ STL常用内容总结1.vector(数组)1.1 介绍1.2 方法函数1.3 注意点1.3.a 排序1.3.b 访问2.stack(栈)2.1 介绍2.2 方法函数2.3 注意点2.3.a.栈遍历2.3.b.模拟栈3.queue...
  • C++STL函数nth_element.
  • C++ STL库的总结以及实现原理

    千次阅读 2016-07-16 19:57:32
    STL的容器可以分为以下几个大类: 一:序列容器, 有vector, list, deque, string. 二 : 关联容器, 有set, multiset, map, mulmap  hash_set,hash_map, hash_multiset, hash_multimap 三: 其他的杂项: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 73,350
精华内容 29,340
关键字:

c++ stl库

c++ 订阅