STL,即标准模板库(Standard Template Library,STL),内部封装了常见的容器和算法。
由六部分组成:1.容器(Containers)2.分配器(Allocators)3.算法(Algorithm) 4.迭代器(Iterators) 5.适配器(Adapters) 6.仿函数(Functors)
容器通过分配器获取内存空间,算法通过迭代器获取容器内容,仿函数协助算法完成策略变化,适配器可以修改仿函数;
实现了数据结构和算法的分离,是C++模版编程和C++面向对象的最佳实践之一;
本系列希望通过对源码的学习,加深对C++模版编程的理解,精进编程思想;
vector本身是连续型数据结构,类似于C语言中标准数组。
标准数组在分配空间后,想要进行扩展,需要如下步骤
1.新分配内存空间
2.把原数组拷贝至新空间;
3.释放原空间;
而vector的动态扩容,实际也是通过对这些行为进行封装,类内自动进行内存管理;
声明vector类,用sizeof查看大小,可得到vectory的大小,24(64位机的大小,不受数组内元素的影响),由三个指针构成
pointer __begin_;
pointer __end_;
__compressed_pair<pointer, allocator_type> __end_cap_;
</pointer,>
和数组类似,verctory实际是一个在内存中连续分配的内存空间;(在堆中,由alloc分配)
begin,指向数组0号元素地址;
end;指向数组最后一个元素的下一个地址;
end_cap;表示数组声明后,分配空间的终点内存地址;
begin到end,表示已经初始化的内存空间;
end到capacity,属于vectory,但是没有初始化的内存空间;
end – begin = size, 容器内容的数据大小;
end_cap – begin = capacity, 分配的内存大小,可以存储的数据量的多少;
vectory最大的特点是可以动态分配内存,涉及动态分配的函数有这些:
构造函数,操作符=,push_back(),shrink_to_fit(),insert()
构造函数:
待补充;
template <class _allocator>
void
vector<bool, _allocator>::push_back(const value_type& __x)
{
// _size = capacity时进行扩容;
if (this->__size_ == this->capacity())
reserve(__recommend(this->__size_ + 1));
++this->__size_;
back() = __x;
}
// 自动扩容
template <class _allocator>
inline _LIBCPP_INLINE_VISIBILITY
typename vector<bool, _allocator>::size_type
vector<bool, _allocator>::__recommend(size_type __new_size) const
{
const size_type __ms = max_size();
if (__new_size > __ms)
this->__throw_length_error();
const size_type __cap = capacity();
if (__cap >= __ms / 2)
return __ms;
return _VSTD::max(2 * __cap, __align_it(__new_size));
}
</bool,></bool,></class></bool,></class>
简单解析:
1.push_back(),当发现size() == capacity(),需要扩容,使用reserve函数重新对空间进行分配(reserve会在内存中开辟一片新空间,并把原容器进行拷贝);
2.分配大小为__recommend函数返回值;
缩小: if (__cap >= __ms / 2) return __ms; // size小于容量的一半,这个分支在push_back的时候不会调用;
扩大: max(2 * __cap, __align_it(__new_size));
template <class _allocator>
typename vector<bool, _allocator>::iterator
vector<bool, _allocator>::insert(const_iterator __position, const value_type& __x)
{
iterator __r;
if (size() < capacity())
{
const_iterator __old_end = end();
++__size_;
_VSTD::copy_backward(__position, __old_end, end());
__r = __const_iterator_cast(__position);
}
else
{
vector __v(__alloc());
__v.reserve(__recommend(__size_ + 1));
__v.__size_ = __size_ + 1;
__r = _VSTD::copy(cbegin(), __position, __v.begin());
_VSTD::copy_backward(__position, cend(), __v.end());
swap(__v);
}
*__r = __x;
return __r;
}
</bool,></bool,></class>
插入时,校验是否size < capacity, true, 使用迭代器插入元素;
否则使用reserve+recommend进行扩容;
设置元素数目,少的填充,实际就是初始化;
调用vectory中所有成员的析构函数,但是不会是否capacity,不会真正释放内存
更改内存容量函数,动态扩容通过本函数完成
释放capacity > size的部分
移除指定位置的元素;
Original: https://www.cnblogs.com/Albert-lihai/p/16576769.html
Author: Albert_禄遥
Title: 个人学习-STL深入学习01-vectory源码研习 // 需要补充
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/577716/
转载文章受原作者版权保护。转载请注明原作者出处!