|
|
1 vector概述
vector：自动增长的数组(2倍增长)，设计关键在扩容（1.配置新空间2.数据移动3.释放旧空间）。
array：定长数组
2 vector定义摘要
空vector的大小：12byte，3个指针的大小（start, finish, end_of_storage）
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;
// 三个指针（vector的迭代器就是普通指针），很重要！vector创建之后大小：12byte 3个指针的大小
iterator start;
iterator finish;
iterator end_of_storage;
// 声明插入函数（带扩容）
void insert_aux(iterator position, const T& x);
// 释放整个vector的内存
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(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;
}
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;
}
// 析构函数
~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);// 全局函数
}
//删除元素
iterator erase(iterator position) {
if (position + 1 != end())
copy(position + 1, finish, position);//后续元素往前移动
--finish;
destroy(finish);//全局函数
return position;//返回的迭代器指向原来的位置（其实就指向了下一个）
}
//resize不仅可以将size变大，还可以将size变小
void resize(size_type new_size, const T& x) {
//将size变小，erase掉后边所有元素
if (new_size < size())
erase(begin() + new_size, end());
//将size变大
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);
__STL_TRY {
uninitialized_fill_n(result, n, x);// 全局函数
return result;
}
__STL_UNWIND(data_allocator::deallocate(result, n));
}
//用于拷贝构造
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));
}
//...
};
4 vector的迭代器
（本文基于GNU2.9版本，GNU4.9版本的迭代器单独出类，侯杰的评价的“乱七八糟，舍近求远，何必如此！！”）
因为vector是连续空间，迭代器不必设计太复杂。
迭代器直接在vector类里定义，就是普通指针，没有再封装（不像list的迭代器单独封装成一个类，因为其指向的是node，不是原始的data），属于RandomAccess Iterators。
*、->、++、--、 +、-、 +-、-=等运算普通指针天生就具备，就没有运算符重载。
template <class T, class Alloc = alloc>
class vector {
public:
typedef T value_type;
typedef value_type* iterator;
typedef const value_type* const_iterator;
typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
iterator begin() { return start; }
const_iterator begin() const { return start; }
iterator end() { return finish; }
const_iterator end() const { return finish; }
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const {
return const_reverse_iterator(end());
}
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const {
return const_reverse_iterator(begin());
}
//...
};
例子：通过萃取traits获得iterator关联类型
template<class I>
typename iterator_traits<I>::value_type func(I iter) {
return *iter;
}
int main(void) {
vector<int> vec = {1, 2, 3};
vector<int>::iterator iter = vec.begin();
int x = func(iter);
}
由于vector的iterator是普通指针，匹配偏特化的traits类，即
//偏特化：传入类型为原生指针
template <class T>
struct iterator_traits<T*> {
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
};
3 insert
- list新增一个元素是先申请一个node的空间再construct（可以原地扩容）
- vector新增一个元素是提前把一段空间申请出来，直接construct（不能原地扩容），在扩容的过程中调用的拷贝构造函数和析构函数。多次拷贝会构成性能瓶颈。
//在position插入一个元素，如果没有备用空间就扩容
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); //全局方法，像 copy() 那样复制元素，但是从最后一个元素开始直到第一个元素。把从finish-2到position的元素复制到finish-1的位置
*position = x_copy;
}
//已无备用空间
else {
const size_type old_size = size();
//新创建的vector old_size为0，扩容为1；否则二倍扩容
const size_type len = old_size != 0 ? 2 * old_size : 1;
//1. 配置新空间
iterator new_start = data_allocator::allocate(len);
iterator new_finish = new_start;
__STL_TRY {
//2. 数据移动
//2.1拷贝position之前的内容
new_finish = uninitialized_copy(start, position, new_start);
//2.2为新元素设置初值x
construct(new_finish, x);
++new_finish;
//2.3拷贝positon之后的内容
new_finish = uninitialized_copy(position, finish, new_finish);
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
destroy(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
//3. 释放旧空间
destroy(begin(), end());//析构
deallocate();//释放旧空间
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
//在position插入n个元素，如果没有备用空间就扩容
template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
if (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;
copy_backward(position, old_finish - n, old_finish);
fill(position, position + n, x_copy);
}
else {
uninitialized_fill_n(finish, n - elems_after, x_copy);
finish += n - elems_after;
uninitialized_copy(position, old_finish, 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);
iterator new_start = data_allocator::allocate(len);
iterator new_finish = new_start;
__STL_TRY {
new_finish = uninitialized_copy(start, position, new_start);
new_finish = uninitialized_fill_n(new_finish, n, x);
new_finish = uninitialized_copy(position, finish, new_finish);
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
destroy(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
destroy(start, finish);
deallocate();
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
} |
|
发表于 2022-11-28 13:33:09