Skip to content

Latest commit

 

History

History
251 lines (198 loc) · 8.66 KB

11 vector 上.md

File metadata and controls

251 lines (198 loc) · 8.66 KB
Raw

vector

前言

在STL编程中, 容器就是我们经常会用到的, 容器分为序列容器和关联式容器. 而这一篇我们就分析序列容器之一vector. 关于用过vector三的人肯定对其一点都不陌生, vector基本能够支持任何类型的对象, 同时是一个可以动态增长数组. 马上就来分析关于vector是怎么实现这些功能.

vector的简单调用

相信都对vector有一定的认识, 这里我就将本节会讲到关于vector源码的操作执行一次, 让大家先有一个回忆.

int main()
{
	vector<int> v1;
	vector<int> v2(4);
	vector<int> v3(4, 1);

	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	
	if(!v1.empty())	// 不为空
	{
		cout << *v1.begin() << " " << v1.front() << " " << *(v1.end() - 1) << " " << v1.back() <<  endl;
		cout << "size = " << v1.size() << endl;
        v1.~vector();
	}

	exit(0);
}

输出:

1 1 4 4
size = 4

回忆了vector最基本的操作, 现在我们就来分析其实现.

vector容器

vector基本数据结构

vector为自己定义嵌套型别. 为了符合traits编程规则( 规则要求每个使用traits萃取器的都必须自己定义五个嵌套型别 ), 有一点很重要, vector迭代器就是一个普通指针.  普通类型可以有不同于其他类型的操作, 比如uninitialized_copy可以尽可能的优化执行等. 因为vector必须是存放一个连续的现行空间中, 并且连续空间的大小都要比用户自己要求的空间要大两倍, 剩余的空间是留着作备用, 毕竟vector可是能动态增长的, 所以留着部分空间以备增长. 这里也可以发现vector很大的问题, 当以备空间也用完之后, vector需要重新更大的申请空间然后释放掉之前的空间, 这样的代价也很大啊, 但是为了动态增长, 这点问题我们也可以接受的.

template <class T, class Alloc = alloc>
class vector 
{
public:
  	// 定义vector自身的嵌套型别
    typedef T value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    // 定义迭代器, 这里就只是一个普通的指针
    typedef value_type* iterator;
    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;
    ...
  protected:
    typedef simple_alloc<value_type, Alloc> data_allocator;	// 设置其空间配置器
    iterator start;				// 使用空间的头
    iterator finish;			// 使用空间的尾
    iterator end_of_storage;	// 可用空间的尾
    ...
};

因为vector 需要表示用户的数据的起始地址, 结束地址, 还需要其真正的最大地址, 所以总共需要3个迭代器分别指向数据的头(start), 数据的尾(finish), 数组的尾(end_of_storage).

    iterator start;				// 使用空间的头
    iterator finish;			// 使用空间的尾
    iterator end_of_storage;	// 可用空间的尾

构造函数

vector有多个构造函数, 为了满足多种初始化.

vector() : start(0), finish(0), end_of_storage(0) {}		// 默认构造函数
explicit vector(size_type n) { fill_initialize(n, T()); } 	// 必须显示的调用这个构造函数, 接受一个值
vector(size_type n, const T& value) { fill_initialize(n, value); } // 接受一个大小和初始化值. int和long都执行相同的函数初始化
vector(int n, const T& value) { fill_initialize(n, value); }	
vector(long n, const T& value) { fill_initialize(n, value); }
vector(const vector<T, Alloc>& x); 	// 接受一个vector参数的构造函数
// 初始化vector的使用空间头和空间的尾
void fill_initialize(size_type n, const T& value) 
{
    start = allocate_and_fill(n, value);	// 初始化并初始化值
    finish = start + n;
    end_of_storage = finish;
}

初始化满足要么都初始化成功, 要么一个都不初始化并释放掉抛出异常

// 调用默认的第二配置器分配内存, 分配失败就释放所分配的内存
iterator allocate_and_fill(size_type n, const T& x)
{
    iterator result = data_allocator::allocate(n);	// 申请n个元素的线性空间.
    __STL_TRY 	// 对整个线性空间进行初始化, 如果有一个失败则删除全部空间并抛出异常.
    {
         uninitialized_fill_n(result, n, x);	
         return result;
    }
    __STL_UNWIND(data_allocator::deallocate(result, n));
}

vector有一个接受vector参数的构造函数, 调用的是uninitialized_copy执行初始化, 我们在上一篇分析过该函数.

vector(const vector<T, Alloc>& x) 
{
    start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());
    finish = start + (x.end() - x.begin());	// 初始化头和尾迭代器位置
    end_of_storage = finish;
}
// 同样进行初始化
template <class ForwardIterator> 
iterator allocate_and_copy(size_type n, ForwardIterator first, ForwardIterator last) 
{
	iterator result = data_allocator::allocate(n);
	__STL_TRY 
    {
          uninitialized_copy(first, last, result);	// 这里采用的是uninitialized_copy, 进行复制. 
          return result;
    }
    __STL_UNWIND(data_allocator::deallocate(result, n));
}

#else /* __STL_MEMBER_TEMPLATES */
// 支持两个迭代器表示范围的复制
    iterator allocate_and_copy(size_type n,
        const_iterator first, const_iterator last) 
    {
      iterator result = data_allocator::allocate(n);
      __STL_TRY {
        uninitialized_copy(first, last, result);
        return result;
      }
      __STL_UNWIND(data_allocator::deallocate(result, n));
    }
#endif /* __STL_MEMBER_TEMPLATES */
};

构造函数, 接受两个迭代器, 构造一个范围的数据.

#ifdef __STL_MEMBER_TEMPLATES
template <class InputIterator>
vector(InputIterator first, InputIterator last) :
        start(0), finish(0), end_of_storage(0)
  {
    range_initialize(first, last, iterator_category(first));
  }
#else /* __STL_MEMBER_TEMPLATES */
vector(const_iterator first, const_iterator last) {
      size_type n = 0;
      distance(first, last, n);
      start = allocate_and_copy(n, first, last);
      finish = start + n;
      end_of_storage = finish;
    }
#endif /* __STL_MEMBER_TEMPLATES */

析构函数

析构函数就是直接调用deallocate 空间配置器, 从头释放到数据尾部, 最后将内存还给空间配置器.

vector因为是类, 所以我们并不需要手动的释放内存, 生命周期结束后就自动调用析构从而释放调用空间, 当然我们也可以直接调用析构函数释放内存.

void deallocate() 
{
	if (start) 
        data_allocator::deallocate(start, end_of_storage - start);
}
// 调用析构函数并释放内存
~vector() 
{ 
	destroy(start, finish);
	deallocate();
}

属性获取

位置参数的获取. 因为end()返回的是finish, 而finish是指向最后一个元素的后一个位置的指针, 所以使用end的时候尽量注意一点.

public:
	// 获取数据的开始以及结束位置的指针. 记住这里返回的是迭代器, 也就是vector迭代器就是该类型的指针.
    iterator begin() { return start; }
    iterator end() { return finish; }
	// 获取值
	reference front() { return *begin(); }
    reference back() { return *(end() - 1); } 
	// 获取右值
	const_iterator begin() const { return start; }
    const_iterator end() const { return finish; }
	const_reference front() const { return *begin(); }
	const_reference back() const { return *(end() - 1); }
    // 获取基本数组信息
	size_type size() const { return size_type(end() - begin()); }	 // 数组元素的个数
    size_type max_size() const { return size_type(-1) / sizeof(T); }	// 最大能存储的元素个数
    size_type capacity() const { return size_type(end_of_storage - begin()); }	// 数组的实际大小

判断vector是否为空, 并不是比较元素为0, 是直接比较头尾指针.

bool empty() const { return begin() == end(); }

总结

本节中我们主要分析了关于vector满足traits编程规范的定义, 构造函数, 析构函数, 数组的基本信息获取函数, 将对vector的直接操作放到下一节进行分析.

最后回忆一下本节的重要点 :

  1. vector的迭代器是一个普通的指针
  2. 构造函数的重载满足不同的用户需求
  3. vector因为是类, 所以在生命周期结束后会自动调用析构函数, 用户不再手动的释放内存, 也不会出现内存泄露的问题, 用户也可以主动调用析构函数释放内存
  4. finish是指向最后一个元素的后一位地址, 不是直接指向最后一个元素.