开发成长之路（6）-- C++从入门到开发（C++知名库：STL入门·容器（一））

看、未来

发布于 2021-09-18 10:52:16

3350

发布于 2021-09-18 10:52:16

文章被收录于专栏：CSDN搜“看，未来”

文章目录

前言

其实我刚开始也没想到会写这么快，明显后面几篇的数据跟不上第一篇啦。可能是有一部分朋友对CSDN还不是很了解吧。

在文中的蓝字是可以点击的超链接，在文章标题下面有文章所属专栏，也是可以点击的，我这一系列的文章都在一个专栏下：

开发成长之路

你们可以慢慢看，不懂的随时私信我，我在CSDN上还是比较活跃的，一般一个小时内都能回复。

这个专栏你们可以放心，我绝对不会设置成付费专栏的。毕竟这儿是我最开始接触编程的地方，梦想开始的地方。

资源介绍

STL方面的知识，我也不藏着掖着，我就是“搬运工”，从侯捷老师的《STL源码剖析》中学习，再转述。

如果想要深入了解C++编程之美，一要看设计模式，二要看侯捷老师的书。

这本书我看了三遍，写了一个专栏，后来被删的差不多了。

因为经常翻新。

这一篇，我先挑最简单的“使用方法”来讲讲。

STL概述

STL，虽然是一套程序库，但却不仅仅是一套一般印象中的程序库，而是一个具有划时代意义的、有着深厚理论基础的发明。

说是软件组件史上的一大突破，也当之无愧。

为了建立数据结构与算法的一套标准，降低其间的耦合关系，以及提升各自的交互性、弹性、独立性，C++社群中诞生了STL.

STL是一个开源项目，所以有很多个版本。我讲解及使用的是SGI STL版本，不论是符号命名，还是编码风格上，这个版本的可读性非常高。

STL可不止有容器

对于大部分接触过STL的人来说，对于STL的印象应该是极好的，不过大部分人可能也是简单的将容器和STL的全部画起了等号，最多再加上算法，毕竟我们使用STL常用到的也就那两套头文件。说实话我也前也是这么认为的。

其实STL提供了六大组件，容器和算法只是其中一部分，它们分别是：

容器、算法、迭代器、仿函数、配接器、配置器。

这些组件都是什么？

不要急，就算知道也再看一遍吧。

容器
各种数据结构，如Vector、List、Map，用于存放数据。
算法
各种常见算法如：排序、增删查等。从实现来看，STL算法属于泛型函数。
迭代器
很惊奇，迭代器不属于容器，也不属于算法。
扮演起容器与算法之间的“粘合剂”，是“泛型指针”。
原生指针可以作为一种迭代器，不过迭代器一般是以智能指针的形式存在的。
仿真函数
行为类似函数，从实现来看是一种重载了operator()的类或模板类。
函数指针可视为狭义上的仿真函数。
配接器
说来话长，一种用于修饰容器、迭代器、仿真函数的东西。
配置器
空间配置与管理，如果要深入了解STL代码，则这一块将会是奠基石一般的存在。

来看一下STL六大组件联合工作的图示：

STL的序列式容器容器

源码之前，了无秘密

曾经面试官问过我这么一个问题：请你描述一下，STL中的所有容器，它们的底层实现机制、它们增删查改的时间复杂度是多少。

当时回答的迷迷糊糊的。本篇，就围绕这个话题展开。

Vector

什么是Vector？可以理解为是动态数组。

Vector所采用的数据结构非常简单，连续线性空间。

template <class T,class Alloc * alloc>	//模板，后面会专门出一篇写C++的模板编程
class vector{
···
protected:
	iterator start;	//表示目前使用空间的头
	iterator finish;	//表示目前使用空间的尾
	iterator end_of_storage;	//表示目前可用的空间的尾
···
}

为了降低空间配置的时间成本，vector实际配置的大小可能会比客户端需求的量更大一些，以备将来扩充的可能。

看图：

运用这三个算子，可以很轻易的实现一些功能：

template <class T,class Alloc * alloc>	
class vector{
···
public:
	iterator begin(){return start;}
	iterator end(){return finish;}
	size_type size() const{return size_type(end() - begin());}
	size_type capacity() const{return size_type(end_of_storage - begin());}	//还剩多少空间
	bool empty() const{return begin() == end();}
	reference operator[](size_type n){return *(begin()+n);}	//下标取值法
	reference front(){return *begin();}
	reference back(){return *(end()-1);}
	//返回首尾地址
···
}

再来看一些常用函数的底层实现：

void push_back(const T& x){
	if(finish != end_of_storage){	//还有备用空间
		construct(finish,x);	//一个插入函数，暂时知道这个就够了，偏底层
		++finish;
	}
	else{	//空间不够用了
		insert_aux(end(),x);	//更底层了，看上面那张图
	}
}

注意：一旦引起空间重新配置，指向原Vector的所有迭代器都将失效！！！

pop_back() 删除末端元素：

void pop_back(){
	--finish;
	destroy(finish);	//这个destory后面讲空间配置器的时候会讲到
	//就是这么简单
}

erase() 清除（first，last）中所有元素：

先看图：

iterator erase(iterase first,iterase last){
	iterator i = copy(last,finish,first)	//copy后面的篇章会有，先克服一下困难
	destroy(i,finish);
	finish = finish - (last - first);
	return first;
}

erase() 清除某个位置上的元素：

iterator erase(iterator position){
	if(position +1 != end())
		copy(position +1,finish,position)
	--finish;
	destroy(finish);
	return position;
}

clear() 方法：

void clear(){
	erase(begin(),end());
}

insert() 插入操作：

这个操作的代码实在是太多的底层细节了，还是看图吧：

List

Vector可以用数组的知识来覆盖，那么List，就用链表的知识来覆盖吧。

这里要注意：

list对于任何元素的插入和删除，永远都是常数时间，我也得去一探究竟啦，我当初回答错了。

先看看数据结构：

template <class T>
struct __list_node{
	typedef void* void_pointer;
	void_pointer prev;
	void_pointer next;
	T data;
}

双向链表！！！

list的迭代器和vector的不同，它的要求更高一些。因为链表使用的存储空间往往是零零散散的，所以list的迭代器必须有能力在杂乱的存储空间中快速的跳转。

相对于Vector，List还有一个优势，就是不论如何的插入和接合操作，都不会造成原有的List迭代器失效。List的删除操作也只有指向那个被删除的元素的迭代器失效，其它迭代器不会受影响。

SGI list不仅仅是一个双向链表，还是个环状双向链表，所以它只需要一个指针，便可以完整的表现链表。

template <class T,class Alloc = alloc>	//缺省使用alloc作为配置器
class list{
protected:
	typedef __list_node<T> list_node;
public:
	typedef list_node* link_type;
protected:
	link_type node;	//只要一个指针，便可以表示整个循环链表

如果让指针node指向刻意置于尾端的一个空白节点，node便能符合STL对于“前闭后开”的区间要求，成为list迭代器。

iterator begin(){return (link_type)((*node).next);}

iterator end(){return node;}

bool empty() const{return node->next == node;}

size_type size() const{
	size_type result = 0;
	disance(begin(),end(),result);	//一个全局函数
	return result;
}

reference front(){return *begin();}
reference back(){return *--end();}