❤️ STL 序列式容器 vector 超硬核源码剖析 ❤️

目录

  • 前言
  • 第4章 序列式容器
    • 4.1 容器的概念与分类
      • 4.1.1 序列式容器
    • 4.2 vector
      • 4.2.1 vector概述
      • 4.2.2 vector定义摘要
      • 4.2.3 vector的迭代器
      • 4.2.4 vector的数据结构
      • 4.2.5 vector的构造与内存管理
      • 4.2.6 vector的元素操作

前言

国庆七天假宛如一天假,定睛一看又要上班…
国庆档电影院热闹了不少,《长津湖》真的值回票价,吴京真不错,意外的是易烊千玺竟然演出了小戏骨的感觉,整部电影很有感染力,点赞!
外滩一如既往的人山人海,不过每次抱着去看人的心态还是能玩得开心的,节日就要有节日的氛围
总之,国庆快乐最重要!也祝各位节日快乐!祖国生日快乐! ❤️
❤️ STL 序列式容器 vector 超硬核源码剖析 ❤️_第1张图片

❤️❤️❤️ 如果本文对你有所帮助,请不要忘了点赞、关注、收藏哦!灰常感谢! ❤️❤️❤️

第4章 序列式容器

4.1 容器的概念与分类

容器,置物之所也。
研究数据的特定排列方式,以利于搜寻或排序或其它特殊目的,这一专门学科我们称为数据结构(Data Structures)。大学信息类相关教育里面,与编程最有直接关系的科目,首推数据结构与算法(Algorithms)。几乎可以说,任何特定的数据结构都是为了实现某种特定的算法。STL 容器即是将运用最广的一些数据结构实现出来(图4-1)。未来,在每五年召开一次的C++标准委员会的会议中,STL容器的数量还有可能增加。
众所周知,常用的数据结构不外乎array(数组)、list(链表)、tree(树)、stack(堆栈)、queue(队列)、hash table(散列表)、set(集合)、map(映射表)···等等。根据“数据在容器中的排列”特性,这些数据结构分为序列式(sequence)和关联式(associative)两种。本章探讨序列式容器,下一章探讨关联式容器。容器是大多数人对STL的第一印象,这说明了容器的好用与受欢迎。容器也是许多人对STL 的唯一印象,这说明了还有多少人利器(STL)在手而未能善用。
❤️ STL 序列式容器 vector 超硬核源码剖析 ❤️_第2张图片
这里所谓的衍生,并非派生(inheritance)关系,而是内含(containment)关系。例如 heap内含一个 vectorpriority-queue 内含一个 heapstackqueue 都含一个dequeset/map/multiset/multimap 都内含一个 RB-treehast_x 都内含一个hashtable

4.1.1 序列式容器

4.2 vector

4.2.1 vector概述

vector 的数据安排以及操作方式,与 array非常相似。两者的唯一差别在于空间的运用的灵活性。array 是静态空间,一旦配置了就不能改变;要换个大(或小)一点的房子,可以,一切琐细得由客户端自己来:首先配置一块新空间,然后将元素从旧址一一搬往新址,再把原来的空间释还给系统。vector 是动态空间,随着元素的加入,它的内部机制会自行扩充空间以容纳新元素。因此,vector 的运用对于内存的合理利用与运用的灵活性有很大的帮助,我们再也不必因为害怕空间不足而一开始就要求一个大块头 array了,我们可以安心使用vector,吃多少用多少。vector的实现技术,关键在于其对大小的控制以及重新配置时的数据移动效率。一旦 vector旧有空间满载,如果客户端每新增一个元素, vector内部只是扩充一个元素的空间,实为不智,因为所谓扩充空间(不论多大),一如稍早所说是“配置新空间/数据移动/释还旧空间”的大工程,时间成本很高,应该加人某种未雨绸缪的考虑。稍后我们便可看到 SGI vector的空间配置策略。

4.2.2 vector定义摘要

以下是 vector定义的源代码摘录。虽然STL规定,欲使用 vector者必须先包括< vector>,但 SGISTL将 vector实现于更底层的

// alloc 是 SGI STL 的空间配置器
template<class T, class Alloc = alloc>
class vector {
     
public:
    typedef T value_type;
    typedef value_type* pointer;
    typedef value_type* iterator;
    typedef value_type& reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

protected:
    // simple_alloc 是 SGI STL 的空间配置器,是源码所有容器都使用这个接口
    typedef simple_alloc<value_type, Alloc> data_allocator;

    iterator start;           //表示目前使用空间的头
    iterator finish;          //表示目前使用空间的尾
    iterator end_of_storage;  //表示目前可用空间的尾

    void insert_aux(iterator position, const T& x);
    void deallocate() {
     
        if(start)
            data_allocator::deallocate(start, end_of_storage - start);
    }
    void fill_initialize(size_type n, const T& value) {
     
        start = allocate_and_fill(n, value);
        finish = start + n;
        end_of_storage = finish;
    }

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);
    }
    
    vector() : start(0), finish(0), end_of_storage(0) {
     }
    vector(size_type n, const T& value) {
     
        fill_initialize(n, value);
    }
    vector(int n, const T& value) {
     
        fill_initialize(n, value);
    }
    vector(long n, const T& value) {
     
        fill_initialize(n, value);
    }
    explicit vector(size_type n) {
     
        fill_initialize(n, T());
    }

    ~vector() {
     
        destroy(start, finish);  //全局变量
        deallocate();
    }

    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);  //成员函数,后续会分析
    }
    
    void pop_back() {
     
        --finish;
        destroy(finish);    //finish->~T 这里仅仅是调用指针finish所指对象的析构函数,不能释放内存
    }
  
    iterator erase(iterator position) {
     
        //如果移除的不是最后一个元素
        if (position + 1 != end())
            copy(position + 1, finish, position);  //全局函数

        --finish;
        destroy(finish);
        return position;
    }
    void resize(size_type new_size, const T& 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, T()); }
    void clear() {
      erase(begin(), end()); }

protected:
    //配置空间并填满内容
    iterator allocate_and_fill(size_type n, const T& x) {
     
        iterator result = data_allocator::allocate(n);
        {
     
            uninitialized_fill_n(result, n, x);
            return result;
        }
    }

4.2.3 vector的迭代器

vector维护的是一个连续线性空间,所以不论其元素型别为何,普通指针都可以作为 vector的迭代器而满足所有必要条件,因为 vector迭代器所需要的操作行为, 如 operator*, operator->, operator++, operator--, operator+, operator-,operator+=, operator-=,普通指针天生就具备。 vector支持随机存取,而普通指针正有着这样的能力。所以, vector提供的是 Random Access Iterators。

template <class T, class Alloc = alloc>
class vector {
     
public:
	typedef T value_type;
	typedef value_type* iterator;	// vector的迭代器是普通指针
...
}

根据上述定义,如果客户端写出这样的代码:

vector<int>::iterator ivite;
vector<Shape>::iterator svite;

ivite的型别其实就是int*, svite的型别其实就是 Shape*。

4.2.4 vector的数据结构

vector所采用的数据结构非常简单:线性连续空间。它以两个迭代器 startfinish分别指向配置得来的连续空间中目前已被使用的范围,并以迭代器end_of_ storage指向整块连续空间(含备用空间)的尾端:

template<class T, class Alloc = alloc>
class vector {
     
protected:
	iterator start;				//表示目前使用空间的头
	iterator finish;			//表示目前使用空间的尾
	iterator end_of_storage;	//表示目前可用空间的尾
...
}

为了降低空间配置时的速度成本, vector实际配置的大小可能比客户端需求量更大一些,以备将来可能的扩充。这便是容量( capacity)的观念。换句话说,一个 vector的容量永远大于或等其大小。一旦容量等于大小,便是满载,下次再有新增元素,整个 vector就得另觅居所,见图4-2运用 start, finish,end_of_storage三个迭代器,便可轻易地提供首尾标示、大小、容量、空容器判断、注标([1)运算子、最前端元素值、最后端元素值…等机能
❤️ STL 序列式容器 vector 超硬核源码剖析 ❤️_第3张图片

4.2.5 vector的构造与内存管理

千头万绪该如何说起?以客户端程序代码为引导,观察其所得结果并实证源代码,是一个良好的学习路径。下面是一个小小的测试程序,我的观察重点在构造的元素的添加,以及大小、容量的变化:

// filename: 4vector-test. cpp
#include 
#include 
#include 
using namespace std;

int main()
{
     
	//int i;
	vector<int>iv(2, 9);
	cout << "size = " << iv.size() << endl;			// size=2
	cout << "capacity = " << iv.capacity() << endl;	// capacity=2

	iv.push_back(1);
	cout << "size = " << iv.size() << endl;			// size=3
	cout << "capacity = " << iv.capacity() << endl; // capacity=4

	iv.push_back(2);
	cout << "size = " << iv.size() << endl;			// size=4
	cout << "capacity = " << iv.capacity() << endl; // capacity=4

	iv.push_back(3);
	cout << "size = " << iv.size() << endl;			// size=5
	cout << "capacity = " << iv.capacity() << endl; // capacity=8

	iv.push_back(4);
	cout << "size = " << iv.size() << endl;			// size=6
	cout << "capacity = " << iv.capacity() << endl; // capacity=8

	for (int i = 0; i < iv.size(); ++i)
	{
     
		cout << iv[i] << ' ';						// 9 9 1 2 3 4
	}
	cout << endl;

	iv.push_back(5);
	cout << "size = " << iv.size() << endl;			// size=7
	cout << "capacity = " << iv.capacity() << endl; // capacity=8

	for (int i = 0; i < iv.size(); ++i)
	{
     
		cout << iv[i] << ' ';						// 9 9 1 2 3 4 5
	}
	cout << endl;

	iv.pop_back();
	iv.pop_back();
	cout << "size = " << iv.size() << endl;			// size=5
	cout << "capacity = " << iv.capacity() << endl; // capacity=8

	iv.pop_back();
	cout << "size = " << iv.size() << endl;			// size=4
	cout << "capacity = " << iv.capacity() << endl; // capacity=8

	vector<int>::iterator ivite = find(iv.begin(), iv.end(), 1);
	if (ivite != iv.end())
	{
     
		iv.erase(ivite);
	}
	cout << "size = " << iv.size() << endl;			// size=3
	cout << "capacity = " << iv.capacity() << endl; // capacity=8

	for (int i = 0; i < iv.size(); ++i)
	{
     
		cout << iv[i] << ' ';						// 9 9 2 
	}
	cout << endl;

	ivite = find(iv.begin(), iv.end(), 2);
	if (ivite != iv.end())
	{
     
		iv.insert(ivite, 3, 7);
	}

	cout << "size = " << iv.size() << endl;			// size=6
	cout << "capacity = " << iv.capacity() << endl; // capacity=8
	for (int i = 0; i < iv.size(); ++i)
	{
     
		cout << iv[i] << ' ';						// 9 9 7 7 7 2 
	}
	cout << endl;

	iv.clear();
	cout << "size = " << iv.size() << endl;			// size=0
	cout << "capacity = " << iv.capacity() << endl; // capacity=8

	//system("pause");
	return 0;
}

vector缺省使用alloc(第二章)作为空间配置器,并据此另外定义了一个data_allocator,为的是更方便以元素大小为配置单位。

uninitialized_fill_n()会根据第一参数的型别特性( type traits,3.37节),决定使用算法fiill_n()或反复调用 construct()来完成任务(见2.3节描述)。
当我们以 push_back()将新元素插入于 vector尾端时,该函数首先检查是否还有备用空间,如果有就直接在备用空间上构造元素,并调整迭代器 finish,使vector变大;如果没有备用空间了,就扩充空间(重新配置、移动数据、释放原空间)。

void push_back(const T& x) {
     
	if (finish != end_of_storage) {
     	// 还有备用空间
		construct(finish, x);		// 全局函数, 见2.2.3节
		++finish;					// 调整水位高度
	}
	else							// 已无备用空间
	{
     
		insert_aux(end(), x);		// vector member function,见以下列表
	}
}

template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x)
{
     
	if (finish != end_of_storage) {
     		//还有备用空间
		// 在备用空间起始处构造一个元素, 并以 vector最后一个元素值为其初值
		construct(finish, *(finish - 1);
		// 调整水位
		++finish;
		T x_copy = x;
		copy_backward(position, finish - 2, finish - 1);
		*position = x_copy;
	}
	else {
     								// 已无备用空间
		const size_type old_size = size();
		const size_type len = old_size = 0 ? 2 * old_size; 1;
		//以上配置原则:如果原大小为0,则配置1(个元素大小)
		//如果原大小不为0,则配置原大小的两倍
		//前半段用来放置原数据,后半段准备用来放置新数据

		iterator new_ start = data_allocator::allocate(len);//实际配置
		iterator new_finish = new_start;
		try {
     
			// 将原 vector的内容拷贝到新 vector
			new finish = uninitialized_copy(start, position, new_start);
			//为新元素设定初值
			construct(new_finish, x);
			//调整水位
			++new_finish;
			//将原 vector的备用空间中的内容也忠实拷贝过来(侯捷疑惑:啥用途 ? )
			new_finish = uninitialized_copy(position, finish, new_finish);
		}
		catch (...) {
     
			//"commit or roll back" semantics
			destroy(new_start, new_finish);
			data_allocator::deallocate(new_start, len);
			throw;
		}

		// 析构并释放原 vector
		destroy(begin(), end());
		deallocate();

		//调整迭代器, 指向新 vector
		start = new_start;
		finish = new_finish;
		end_of_storage = new_start + len;
	}
}
	

注意,所谓动态增加大小,并不是在原空间之后接续新空间(因为无法保证原空间之后尚有可供配置的空间),而是以原大小的两倍另外配置一块较大空间,然后将原内容拷贝过来,然后才开始在原内容之后构造新元素,并释放原空间。因此对 vector的任何操作,一旦引起空间重新配置,指向原 vector的所有迭代器就都失效了。这是程序员易犯的一个错误,务需小心。

4.2.6 vector的元素操作

vector所提供的元素操作很多,无法在有限篇幅中一一讲解其实也没有这种必要。为搭配先前对空间配置的讨论,我挑选数个相关函数作为解说对象,这些函数也出现在先前的测试程序中。

//将尾端元素拿掉,并调整大小
void pop_back() {
     
	--finish;				// 将尾端标记往前移一格, 表示将放弃尾端元素
	destroy(finish);		// destroy是全局函数,见第2章
}

// 清除[ first, last)中的所有元素
iterator erase(iterator first, iterator last) {
     
	iterator i = copy(last, finish, first);		//copy是全局函数,第6章
	destroy(i, finish);							//destroy是全局函数, 第2章
	finish = finish - (last - first);
	return first;
}

//清除某个位置上的元素
iterator erase(iterator position) {
     
	if (position + 1 != end())
	{
     
		copy(position + 1, finish, position);	//copy是全局函数,第6章
	}
	--finish;
	destroy(finish);							// destroy是全局函数,2.2.3节
	return positlon;
}

void clear() {
     erase(begin(), end());}// erase()就定义在上面

❤️ STL 序列式容器 vector 超硬核源码剖析 ❤️_第4张图片
下面是 vector::insert()实现内容:

// 从 position开始, 插入n个元素, 元素初值为x
template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
     
	if (n != 0) {
     		//当n!=0才进行以下所有操作
		if (size_type(end_of_storage - finish) >= n) {
     
			//备用空间大于等于“新增元素个数
			T x_copy = x;
			//以下计算插入点之后的现有元素个数
			const size_type elems_after = finish - position;
			iterator old_finish = finish;
			if (elems_after > n) {
     
				// "插入点之后的现有元素个数"大于“新增元素个数
				uninitialized_copy(finish - n, finish, finish);
				finish += n;
				// 将 vector尾端标记后移
				copy_backward(position, old_finish - n, old_finish);
				fill(position, posltion + n, x_copy); // 从插入点开始填人新值

			}
			else {
     
				// “插入点之后的现有元素个数”小于等于“新增元素个数
				uninitialized_fill_n(finish, n - elems_after, x_copy);
				finish += n - elems_after;
				uninitialized_copy(position, old_position, finish);
				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);
			//以下配置新的 vector空间
			iterator new_start = data_allocator::allocate(len);
			iterator new_finish = new_start;
			__STL_TRY
				// 以下首先将旧 vector的插入点之前的元素复制到新空间
				new_finish = uninitialized_copy(start, position, new_start);
			//以下再将新增元素(初值皆为n)填人新空间
			new_finish = uninitialized_fill_n(new_finish, n, x);
			//以下再将旧 vector的插入点之后的元素复制到新空间
			new_finish = uninitialized_copy(position, finish, new_finish);
#ifdef __STL_USE_EXCEPTIONS
			catch (...) {
     
				// 如有异常发生, 实现" commit or ro11back" semantics
				destroy(new_start, new_finish);
				data_allocator::deallocate(new_start, len);
				throw;
#endif	 /*STL _USE_EXCEPTIONS */
				//以下清除并释放旧的 vector
				destroy(start, finish);
				deallocate();
				// 以下调整水位标记
				start = new_start;
				finish = new_finish;
				end_of_storage = new_start + len;
		}
	}
}

注意,插人完成后,新节点将位于哨兵迭代器(例之 position,标示出插入点)所指之节点的前方一一这是STL对于“插入操作”的标准规范。图4-3b展示了 Insert( position,n,x)的操作
❤️ STL 序列式容器 vector 超硬核源码剖析 ❤️_第5张图片
在这里插入图片描述

❤️ STL 序列式容器 vector 超硬核源码剖析 ❤️_第6张图片

❤️ STL 序列式容器 vector 超硬核源码剖析 ❤️_第7张图片
❤️ STL 序列式容器 vector 超硬核源码剖析 ❤️_第8张图片

❤️❤️❤️ 如果本文对你有所帮助,请不要忘了点赞、关注、收藏哦!灰常感谢! ❤️❤️❤️

你可能感兴趣的