STL很好用,用起来很顺手,这大概是STL给大家的第一印象同时也说明STL受到很多C++开发者的欢迎。
序列容器是指容器中的元素是可排序的,但并不能保证都是有序的。C++中提供了Array,STL中国提供vector、list、deque、stack、queue等常用的容器结构,本文将对这些容器的一些关键部分进行分析。
1 vector
一直以来很多人都把vector当做数组使用,主要是因为操作方式相似,但vector又比数组更加灵活,数组的大小是固定的,一旦声明,后面使用过程中就不能改变。vector不同,它是可以动态扩展的,空间不够时,底层会进行扩展,主动寻找一块更大的内存,除非物理内存不够,不然vector理论上可以无限扩展。
1.1 vector定义摘要
vector发展到今日,实现代码早已被人重构过很多次。相比侯捷老师源码分析书中摘录的代码也已经发生了很大的改变,下面是从GCC中的源码摘录,它来自stl_vactor.h头文件中。
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>
{
public:
//STL类型的定义
typedef _Tp value_type;
typedef typename _Base::pointer pointer;
typedef typename _Alloc_traits::const_pointer const_pointer;
typedef typename _Alloc_traits::reference reference;
typedef typename _Alloc_traits::const_reference const_reference;
typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
const_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef _Alloc allocator_type;
protected:
//STL空间适配器
using _Base::_M_allocate;
using _Base::_M_deallocate;
using _Base::_M_impl;
using _Base::_M_get_Tp_allocator;
};
在vector中,还有三个变量他们分别指向使用空间的头、尾以及目前可以用空间的尾,定义如下:
struct _Vector_impl_data
{
pointer _M_start;
pointer _M_finish;
pointer _M_end_of_storage;
};
struct _Vector_impl
: public _Tp_alloc_type, public _Vector_impl_data
{
};
template<typename _Tp> struct _Vector_base {
struct _Vector_impl { _Tp* _M_finish; };
_Vector_impl _M_impl;
};
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>
{
}
C++11后,vector的push_back方法通过调用emplace_back方法实现,实现源码为:
void push_back(value_type&& __x)
{
emplace_back(std::move(__x));
}
#if __cplusplus > 201402L
_GLIBCXX20_CONSTEXPR
reference
#else
void
#endif
emplace_back(_Args&&... __args);
在C++11后,推荐大家使用emplace_back或者empalce插入数据,从实现方式来说,比push_back更加高效,因为empalce使用了move减少了内存的拷贝操作。
1.2 vector迭代器
在1.1给出的源码摘录中可以看到以下几行:
typedef _Tp value_type;
typedef typename _Base::pointer pointer;
typedef typename _Alloc_traits::const_pointer const_pointer;
typedef typename _Alloc_traits::reference reference;
typedef typename _Alloc_traits::const_reference const_reference;
typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
const_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
从上面的定义看出,vector的迭代器就是普通的指针,在实际使用时如果我们定义一个保存了整型数据的vector迭代器,实际上就是一个整型指针,如:
vector<int>::iterator it; //迭代器
int *it; //上面d额迭代器可以等价成此形式。
1.3 vector数据结构
vector是连续的空间,有三个指针分别指向了vector容器不同的位置。如:
struct _Vector_impl_data
{
pointer _M_start; //指向使用空间的头
pointer _M_finish; //指向使用空间的尾
pointer _M_end_of_storage; //指向剩余空间的尾
};
使用这三个指针可以方便获取vector中头、尾元素以及对容器进行运算。
//清空容器
void clear() _GLIBCXX_NOEXCEPT
{ _M_erase_at_end(this->_M_impl._M_start); }
//返回容器开始位置
iterator begin()
{ return iterator(this->_M_impl._M_start); }
//返回容器结束位置
iterator end()
{ return iterator(this->_M_impl._M_finish); }
//返回容器已使用大小
size_type size() const _GLIBCXX_NOEXCEPT
{ return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
//返回容器空间大小
size_type capacity() const
{ return size_type(this->_M_impl._M_end_of_storage
- this->_M_impl._M_start); }
1.4 vector构造和内存原理
参考下面这篇文章,再次不在重复造轮子,链接如下:
1.5 vector元素的操作
vector中提供的操作方法很多,再次不一一列举,仅提供常用的操作方法。
//pop元素
void pop_back()
{
__glibcxx_requires_nonempty();
--this->_M_impl._M_finish;
_Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
_GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
}
iterator emplace(const_iterator __position, _Args&&... __args)
{ return _M_emplace_aux(__position, std::forward<_Args>(__args)...); }
iterator insert(const_iterator __position, value_type&& __x)
{ return _M_insert_rval(__position, std::move(__x)); }
C++20后,push_back实现也是通过调用empalce_back方法,因此如果在编译时没有启用20还是11的话在容器插入元素时推荐使用emplace和emplace_back方法。
- EOF -