/*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1996
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*/
/* NOTE: This is an internal header file, included by other STL headers.
* You should not attempt to use it directly.
*/
#ifndef __SGI_STL_INTERNAL_VECTOR_H
#define __SGI_STL_INTERNAL_VECTOR_H
#include <concept_checks.h>
__STL_BEGIN_NAMESPACE
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1174
#pragma set woff 1375
#endif
////////////////////////////////////////////////////////////
//首先 vector 的空间是连续的
//迭代器所要表达的几个操作符，全可以用原生的指针来表示
//因此 vector 直接使用 原生指针作为迭代器
////////////////////////////////////////////////////////////
// The vector base class serves two purposes. First, its constructor
// and destructor allocate (but don't initialize) storage. This makes
// exception safety easier. Second, the base class encapsulates all of
// the differences between SGI-style allocators and standard-conforming
// allocators.
#ifdef __STL_USE_STD_ALLOCATORS
// Base class for ordinary allocators.
template <class _Tp, class _Allocator, bool _IsStatic>
class _Vector_alloc_base {
public:
typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
allocator_type;
allocator_type get_allocator() const { return _M_data_allocator; }
_Vector_alloc_base(const allocator_type& __a)
: _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
{}
protected:
allocator_type _M_data_allocator;
_Tp* _M_start; // 表示数据/迭代器的首地址
_Tp* _M_finish; // 当前有效数据的结束位置
_Tp* _M_end_of_storage; // 容量的结束位置
_Tp* _M_allocate(size_t __n)
{ return _M_data_allocator.allocate(__n); }
void _M_deallocate(_Tp* __p, size_t __n)
{ if (__p) _M_data_allocator.deallocate(__p, __n); }
};
// Specialization for allocators that have the property that we don't
// actually have to store an allocator object.
template <class _Tp, class _Allocator>
class _Vector_alloc_base<_Tp, _Allocator, true> {
public:
typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
_Vector_alloc_base(const allocator_type&)
: _M_start(0), _M_finish(0), _M_end_of_storage(0)
{}
protected:
_Tp* _M_start;
_Tp* _M_finish;
_Tp* _M_end_of_storage;
typedef typename _Alloc_traits<_Tp, _Allocator>::_Alloc_type
_Alloc_type;
_Tp* _M_allocate(size_t __n)
{ return _Alloc_type::allocate(__n); }
void _M_deallocate(_Tp* __p, size_t __n)
{ _Alloc_type::deallocate(__p, __n);}
};
// 这是主要的模板，由 _Alloc_traits<_Tp, _Alloc>::_S_instanceless 进行了选择
template <class _Tp, class _Alloc>
struct _Vector_base
: public _Vector_alloc_base<_Tp, _Alloc,
_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
{
typedef _Vector_alloc_base<_Tp, _Alloc,
_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
_Base;
typedef typename _Base::allocator_type allocator_type;
_Vector_base(const allocator_type& __a) : _Base(__a) {}
_Vector_base(size_t __n, const allocator_type& __a) : _Base(__a) {
_M_start = _M_allocate(__n);
_M_finish = _M_start;
_M_end_of_storage = _M_start + __n;
}
~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
};
#else /* __STL_USE_STD_ALLOCATORS *///////////////////////////////////////////////////////////////////
template <class _Tp, class _Alloc>
class _Vector_base {
public:
typedef _Alloc allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
_Vector_base(const _Alloc&)
: _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
_Vector_base(size_t __n, const _Alloc&)
: _M_start(0), _M_finish(0), _M_end_of_storage(0)
{
_M_start = _M_allocate(__n); // 这是一个类内部定义的函数，封装了一下 simple_alloc::allocate
_M_finish = _M_start;
_M_end_of_storage = _M_start + __n;
}
// 在析构时自动归还内存，封装了一下 simple_alloc::deallocate
~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
protected:
_Tp* _M_start; // 表示数据/迭代器的首地址
_Tp* _M_finish; // 当前有效数据的结束位置
_Tp* _M_end_of_storage; // 容量的结束位置
typedef simple_alloc<_Tp, _Alloc> _M_data_allocator;
_Tp* _M_allocate(size_t __n)
{ return _M_data_allocator::allocate(__n); }
void _M_deallocate(_Tp* __p, size_t __n)
{ _M_data_allocator::deallocate(__p, __n); }
};
#endif /* __STL_USE_STD_ALLOCATORS */
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc>
{
// requirements:
__STL_CLASS_REQUIRES(_Tp, _Assignable);
private:
typedef _Vector_base<_Tp, _Alloc> _Base;
public:
// STL 规约要求的实现
typedef _Tp 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;
typedef typename _Base::allocator_type allocator_type;
allocator_type get_allocator() const { return _Base::get_allocator(); }
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
typedef reverse_iterator<const_iterator, value_type, const_reference,
difference_type> const_reverse_iterator;
typedef reverse_iterator<iterator, value_type, reference, difference_type>
reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
protected:
#ifdef __STL_HAS_NAMESPACES
using _Base::_M_allocate;
using _Base::_M_deallocate;
using _Base::_M_start;
using _Base::_M_finish;
using _Base::_M_end_of_storage;
#endif /* __STL_HAS_NAMESPACES */
protected:
void _M_insert_aux(iterator __position, const _Tp& __x);
void _M_insert_aux(iterator __position);
public:
iterator begin() { return _M_start; } // 返回数据起始位置
const_iterator begin() const { return _M_start; }
iterator end() { return _M_finish; } // 返回数据结束位置
const_iterator end() const { return _M_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()); }
size_type size() const // 当前数据大小
{ return size_type(end() - begin()); }
// 这里用溢出的办法，对象作除法 -1 转size_type 是内存寻址的最大值
// size_of(_Tp) 是数据对象的大小，因此，对象支持的个数应该作除
size_type max_size() const
{ return size_type(-1) / sizeof(_Tp); }
size_type capacity() const // 容量
{ return size_type(_M_end_of_storage - begin()); }
bool empty() const // 为空判断
{ return begin() == end(); }
// 返回对象的引用，左值
reference operator[](size_type __n) { return *(begin() + __n); }
// 返回对象的右值
const_reference operator[](size_type __n) const { return *(begin() + __n); }
#ifdef __STL_THROW_RANGE_ERRORS
void _M_range_check(size_type __n) const {
if (__n >= this->size())
__stl_throw_range_error("vector");
}
reference at(size_type __n)
{ _M_range_check(__n); return (*this)[__n]; }
const_reference at(size_type __n) const
{ _M_range_check(__n); return (*this)[__n]; }
#endif /* __STL_THROW_RANGE_ERRORS */
explicit vector(const allocator_type& __a = allocator_type())
: _Base(__a) {}
// 新建一个带有 __n 个 __value 值的 vector
vector(size_type __n, const _Tp& __value,
const allocator_type& __a = allocator_type())
: _Base(__n, __a)
{ _M_finish = uninitialized_fill_n(_M_start, __n, __value); }
// 分配几个空的对象
explicit vector(size_type __n)
: _Base(__n, allocator_type())
{ _M_finish = uninitialized_fill_n(_M_start, __n, _Tp()); }
// 拷贝构造函数，名字真长啊 : (
vector(const vector<_Tp, _Alloc>& __x)
: _Base(__x.size(), __x.get_allocator())
{ _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); }
#ifdef __STL_MEMBER_TEMPLATES ///////////////////////////////////////////////////////////////////
// Check whether it's an integral type. If so, it's not an iterator.
// 整数这样弄，速度巨快，因为最后模板竟然会展开到直接内存复制
template <class _Integer>
void _M_initialize_aux(_Integer __n, _Integer __value, __true_type) {
_M_start = _M_allocate(__n);
_M_end_of_storage = _M_start + __n;
_M_finish = uninitialized_fill_n(_M_start, __n, __value);
}
// 这个可能要一个一个复制了
template <class _InputIterator>
void _M_initialize_aux(_InputIterator __first, _InputIterator __last,
__false_type) {
_M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
}
// 从一个迭代器的区间范围，复制数据
// 模板技巧，检测是否为纯整数类型
// _Integral() 判别式，在 type_traits.h 中
template <class _InputIterator>
vector(_InputIterator __first, _InputIterator __last,
const allocator_type& __a = allocator_type()) : _Base(__a)
{
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_initialize_aux(__first, __last, _Integral());
}
#else ////////////////////////////////////////////////////////////////////////////////////////////
vector(const _Tp* __first, const _Tp* __last,
const allocator_type& __a = allocator_type())
: _Base(__last - __first, __a)
{ _M_finish = uninitialized_copy(__first, __last, _M_start); }
#endif /* __STL_MEMBER_TEMPLATES */ /////////////////////////////////////////////////////////////
// 只管把所有对象析构，内存回收是交给了基类
~vector() { destroy(_M_start, _M_finish); }
vector<_Tp, _Alloc>& operator=(const vector<_Tp, _Alloc>& __x);
void reserve(size_type __n)
{
if (capacity() < __n) {
const size_type __old_size = size();
iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __tmp;
_M_finish = __tmp + __old_size;
_M_end_of_storage = _M_start + __n;
}
}
// assign(), a generalized assignment member function. Two
// versions: one that takes a count, and one that takes a range.
// The range version is a member template, so we dispatch on whether
// or not the type is an integer.
void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }
void _M_fill_assign(size_type __n, const _Tp& __val);
#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
void assign(_InputIterator __first, _InputIterator __last) {
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_assign_dispatch(__first, __last, _Integral());
}
template <class _Integer>
void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
{ _M_fill_assign((size_type) __n, (_Tp) __val); }
template <class _InputIter>
void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
{ _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first)); }
template <class _InputIterator>
void _M_assign_aux(_InputIterator __first, _InputIterator __last,
input_iterator_tag);
template <class _ForwardIterator>
void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag);
#endif /* __STL_MEMBER_TEMPLATES */
reference front() { return *begin(); }
const_reference front() const { return *begin(); }
reference back() { return *(end() - 1); }
const_reference back() const { return *(end() - 1); }
// push back 的两个重载
void push_back(const _Tp& __x) {
if (_M_finish != _M_end_of_storage) { // 还有容量
construct(_M_finish, __x); // 全域的 place new : )
++_M_finish; // 移动未尾
}
else
_M_insert_aux(end(), __x); // 问题复杂了，容量不够，要搬运内存
}
void push_back() {
if (_M_finish != _M_end_of_storage) {
construct(_M_finish);
++_M_finish;
}
else
_M_insert_aux(end());
}
void swap(vector<_Tp, _Alloc>& __x) {
__STD::swap(_M_start, __x._M_start);
__STD::swap(_M_finish, __x._M_finish);
__STD::swap(_M_end_of_storage, __x._M_end_of_storage);
}
// insert 的两个重载，可以用拷贝构造函数，也可以用
iterator insert(iterator __position, const _Tp& __x) {
size_type __n = __position - begin();
// 如果数据未放满容量 && 现在是想往最未尾加数据，这实际上是等于 push back
if (_M_finish != _M_end_of_storage && __position == end())
{
construct(_M_finish, __x); // 全域的 place new : )
++_M_finish; // 移动未尾
}
else
_M_insert_aux(__position, __x); // 问题复杂了，可能容量不够，还要搬运内存
// 返回现在的指针位置：因为一旦出现数据搬移，这样原来的迭代器位置不再有效
// 返回的是现在的地址， + n 用数据偏移，在新地址下偏移量会正常有效
return begin() + __n;
}
iterator insert(iterator __position) {
size_type __n = __position - begin();
if (_M_finish != _M_end_of_storage && __position == end()) {
construct(_M_finish);
++_M_finish;
}
else
_M_insert_aux(__position);
return begin() + __n;
}
#ifdef __STL_MEMBER_TEMPLATES
// 这三个模板成员被我调整了一下序
// Check whether it's an integral type. If so, it's not an iterator.
template <class _Integer>
void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
__true_type)
{ _M_fill_insert(__pos, (size_type) __n, (_Tp) __val); }
template <class _InputIterator>
void _M_insert_dispatch(iterator __pos,
_InputIterator __first, _InputIterator __last,
__false_type) {
_M_range_insert(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
}
template <class _InputIterator>
void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_insert_dispatch(__pos, __first, __last, _Integral());
}
#else /* __STL_MEMBER_TEMPLATES */
void insert(iterator __position,
const_iterator __first, const_iterator __last);
#endif /* __STL_MEMBER_TEMPLATES */
void insert (iterator __pos, size_type __n, const _Tp& __x)
{ _M_fill_insert(__pos, __n, __x); }
void _M_fill_insert (iterator __pos, size_type __n, const _Tp& __x);
// 删未尾对象，很简单
void pop_back() {
--_M_finish; // 减未尾指针
destroy(_M_finish); // 全域回收
}
// 清除对象
// 请问，这里为什么调用的是最后边的数据的析构函数呢？？
// 这是STL的作法，我们没法评价，它为什么这么奇怪。
// 只要记住，它只是帮你管理空间，至于它是不是要正确地执行析构函数，它不知道。
iterator erase(iterator __position) {
// 如果它是未尾的对象，从该位置开始没有任何数据需要移动
if (__position + 1 != end())
copy(__position + 1, _M_finish, __position);
--_M_finish; // 直接退一格
destroy(_M_finish); // 全域的 destroy对象，并不回收内存，此时容量不变
return __position;
}
// 清除 [__first, __last) 之间的所有数据
iterator erase(iterator __first, iterator __last) {
// 把从 [__last 至 _M_finish之间的所有数据直接搬移到 __first 位置
iterator __i = copy(__last, _M_finish, __first);
// 这时 copy 后 __i 返回了结束位置
destroy(__i, _M_finish); // 并不回收内存，此时容量不变
// 这里的 __i 应该赋值给 _M_finish吧？ 不知道作者为什么又算了一遍
_M_finish = _M_finish - (__last - __first); // 修改结束的位置
return __first;
}
void resize(size_type __new_size, const _Tp& __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, _Tp()); }
void clear() { erase(begin(), end()); }
protected:
#ifdef __STL_MEMBER_TEMPLATES
template <class _ForwardIterator>
iterator _M_allocate_and_copy(size_type __n, _ForwardIterator __first,
_ForwardIterator __last)
{
iterator __result = _M_allocate(__n);
__STL_TRY {
uninitialized_copy(__first, __last, __result);
return __result;
}
__STL_UNWIND(_M_deallocate(__result, __n));
}
#else /* __STL_MEMBER_TEMPLATES */
iterator _M_allocate_and_copy(size_type __n, const_iterator __first,
const_iterator __last)
{
iterator __result = _M_allocate(__n);
__STL_TRY {
uninitialized_copy(__first, __last, __result);
return __result;
}
__STL_UNWIND(_M_deallocate(__result, __n));
}
#endif /* __STL_MEMBER_TEMPLATES */
#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
void _M_range_initialize(_InputIterator __first,
_InputIterator __last, input_iterator_tag)
{
for ( ; __first != __last; ++__first)
push_back(*__first);
}
// This function is only called by the constructor.
template <class _ForwardIterator>
void _M_range_initialize(_ForwardIterator __first,
_ForwardIterator __last, forward_iterator_tag)
{
size_type __n = 0;
distance(__first, __last, __n);
_M_start = _M_allocate(__n);
_M_end_of_storage = _M_start + __n;
_M_finish = uninitialized_copy(__first, __last, _M_start);
}
template <class _InputIterator>
void _M_range_insert(iterator __pos,
_InputIterator __first, _InputIterator __last,
input_iterator_tag);
template <class _ForwardIterator>
void _M_range_insert(iterator __pos,
_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag);
#endif /* __STL_MEMBER_TEMPLATES */
}; // end class : vector
template <class _Tp, class _Alloc>
inline bool
operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
{
return __x.size() == __y.size() &&
equal(__x.begin(), __x.end(), __y.begin());
}
template <class _Tp, class _Alloc>
inline bool
operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
{
return lexicographical_compare(__x.begin(), __x.end(),
__y.begin(), __y.end());
}
#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
template <class _Tp, class _Alloc>
inline void swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
{
__x.swap(__y);
}
template <class _Tp, class _Alloc>
inline bool
operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
return !(__x == __y);
}
template <class _Tp, class _Alloc>
inline bool
operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
return __y < __x;
}
template <class _Tp, class _Alloc>
inline bool
operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
return !(__y < __x);
}
template <class _Tp, class _Alloc>
inline bool
operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
return !(__x < __y);
}
#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
template <class _Tp, class _Alloc>
vector<_Tp,_Alloc>&
vector<_Tp,_Alloc>::operator=(const vector<_Tp, _Alloc>& __x)
{
if (&__x != this) {
const size_type __xlen = __x.size();
if (__xlen > capacity()) {
iterator __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __tmp;
_M_end_of_storage = _M_start + __xlen;
}
else if (size() >= __xlen) {
iterator __i = copy(__x.begin(), __x.end(), begin());
destroy(__i, _M_finish);
}
else {
copy(__x.begin(), __x.begin() + size(), _M_start);
uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish);
}
_M_finish = _M_start + __xlen;
}
return *this;
}
template <class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::_M_fill_assign(size_t __n, const value_type& __val)
{
if (__n > capacity()) {
vector<_Tp, _Alloc> __tmp(__n, __val, get_allocator());
__tmp.swap(*this);
}
else if (__n > size()) {
fill(begin(), end(), __val);
_M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val);
}
else
erase(fill_n(begin(), __n, __val), end());
}
#ifdef __STL_MEMBER_TEMPLATES /////////////////////////// IF ///////////////////////////////////////
template <class _Tp, class _Alloc> template <class _InputIter>
void vector<_Tp, _Alloc>::_M_assign_aux(_InputIter __first, _InputIter __last,
input_iterator_tag) {
iterator __cur = begin();
for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
*__cur = *__first;
if (__first == __last)
erase(__cur, end());
else
insert(end(), __first, __last);
}
template <class _Tp, class _Alloc> template <class _ForwardIter>
void
vector<_Tp, _Alloc>::_M_assign_aux(_ForwardIter __first, _ForwardIter __last,
forward_iterator_tag) {
size_type __len = 0;
distance(__first, __last, __len);
if (__len > capacity()) {
iterator __tmp = _M_allocate_and_copy(__len, __first, __last);
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __tmp;
_M_end_of_storage = _M_finish = _M_start + __len;
}
else if (size() >= __len) {
iterator __new_finish = copy(__first, __last, _M_start);
destroy(__new_finish, _M_finish);
_M_finish = __new_finish;
}
else {
_ForwardIter __mid = __first;
advance(__mid, size());
copy(__first, __mid, _M_start);
_M_finish = uninitialized_copy(__mid, __last, _M_finish);
}
}
#endif /* __STL_MEMBER_TEMPLATES */ ///////////////////// END IF //////////////////////////////
template <class _Tp, class _Alloc>
void
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
{
// 测试是否已经到达容量极限
if (_M_finish != _M_end_of_storage) {
// 在未尾处申请缓存，同时把当前的最后一个数据往新的末尾位置复制
// 这是由于 constrcut 全域式，使用 place new ，本身就要复制一个对象
// 如果不现在复制，那将会使用一个临时的对象，那可能有新的构造函数运行起来，速度可能并不快
construct(_M_finish, *(_M_finish - 1));
++_M_finish; // 尾部的位置，需要调整
_Tp __x_copy = __x; //
// 把从当前 __position 开始的数据向后移动一份，这样 __position 所在的数据空间就会空下来
copy_backward(__position, _M_finish - 2, _M_finish - 1);
// 调用赋值操作符拷贝需要插入的对象
*__position = __x_copy;
}
// 这是当前容量不足以满足新数据插入的要求，需要申请和拷贝数据
else {
// 这是递增数据 capacity 的算法，如果当前容量为 0，则分配 1，否则，分配空间为当前的 2 倍
const size_type __old_size = size();
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
// 注意，这里的分配器，已经是重定义了的，每次以 Tp 为数据单位来分配空间
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
__STL_TRY {
// 将原来的数据，拷贝到新位置
// 这段内容竟然源码解析的书里没写正确 STL作者的思路 - -
// 注意，因为发生了数据空间的整体地址迁移，所以，之前所有的迭代器都不再有效。
// STEP1: 先以 __position 为结束点，拷贝数据
// 此时 __new_finish 返回当前拷贝数据的结束位置
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
// STEP2: 把当前的数据构造在结束点
construct(__new_finish, __x);
++__new_finish; // 调整结束位置的指针
// 把当前 __position至 _M_finish 的数据拷贝至刚才的结束点位置
// 返回新的结束，也就是最终的结束点
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
__STL_UNWIND(
(
// 如果最到异常，把可能已经分配了的数据，都给干掉
// 注意这里要认正想一下STL作者的思路：
// 首先，如果运行在 uninitialized_copy 中发生异常，应该按照
// STL 规约，所有当前过种中生成的对象，都必须被清空
// 由这个标准，所以我们不用关心每个复制操作中发生错误时对象的销毁
// 其次，我们如果一旦遇到异常，会立即转到 catch 中来，
// 这样 __new_finish 变量作为临时变量没有来得急赋值，它恰好能反映在发生错误的步骤前
// 被正确构建的对象的位置。
// 于是我们要满足STL规约：发生错误时，不构建任何对象。
// 只需要销毁从 [ __new_start, __new_finish) 中的数据即可。
destroy(__new_start,__new_finish),
// 同时地，因为发生了错误，没有对象被构建，要把数据归还内存分配器
_M_deallocate(__new_start,__len)
)
);
// 至此，如果在搬运数据中没有发生任何错误，则数据已经被放置在适合的位置。
// PS：然而，{注意算法中的细节}，如果它发生了错误，这种算法会导致这样一个问题：
// 算法中在开始时，使用 _M_allocate 函数，给 __new_start 分配空间
// 在发生错误时，使用 _M_deallocate 把分配的空间回收了，它似乎并没有把 __new_start 赋于 0 值
// 这样 __new_start 就会指向一个被释放的空间，实际上是个错误。
// 可是，如果 __STL_USE_EXCEPTIONS 被打开，代码就会停止运行了，根本执行不到下面。
// 现在要把以前的对象删除
destroy(begin(), end());
// 及归还其占用的数据空间。
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
// 修改当前 vector 的数据指针
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
// 这是另一个版本，它和上面那是一个的算法，不知道作者为什么没有直接内联调用上面的函数
template <class _Tp, class _Alloc>
void
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position)
{
if (_M_finish != _M_end_of_storage) {
construct(_M_finish, *(_M_finish - 1));
++_M_finish;
copy_backward(__position, _M_finish - 2, _M_finish - 1);
*__position = _Tp();
}
else {
const size_type __old_size = size();
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
__STL_TRY {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
construct(__new_finish);
++__new_finish;
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
__STL_UNWIND((destroy(__new_start,__new_finish),
_M_deallocate(__new_start,__len)));
destroy(begin(), end());
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
template <class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n,
const _Tp& __x)
{
if (__n != 0) {
if (size_type(_M_end_of_storage - _M_finish) >= __n) {
_Tp __x_copy = __x;
const size_type __elems_after = _M_finish - __position;
iterator __old_finish = _M_finish;
if (__elems_after > __n) {
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
_M_finish += __n;
copy_backward(__position, __old_finish - __n, __old_finish);
fill(__position, __position + __n, __x_copy);
}
else {
uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
_M_finish += __n - __elems_after;
uninitialized_copy(__position, __old_finish, _M_finish);
_M_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 = _M_allocate(__len);
iterator __new_finish = __new_start;
__STL_TRY {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
__new_finish = uninitialized_fill_n(__new_finish, __n, __x);
__new_finish
= uninitialized_copy(__position, _M_finish, __new_finish);
}
__STL_UNWIND((destroy(__new_start,__new_finish),
_M_deallocate(__new_start,__len)));
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
}
#ifdef __STL_MEMBER_TEMPLATES ////////////////////////// IF ///////////////////////////
template <class _Tp, class _Alloc> template <class _InputIterator>
void
vector<_Tp, _Alloc>::_M_range_insert(iterator __pos,
_InputIterator __first,
_InputIterator __last,
input_iterator_tag)
{
for ( ; __first != __last; ++__first) {
__pos = insert(__pos, *__first);
++__pos;
}
}
template <class _Tp, class _Alloc> template <class _ForwardIterator>
void
vector<_Tp, _Alloc>::_M_range_insert(iterator __position,
_ForwardIterator __first,
_ForwardIterator __last,
forward_iterator_tag)
{
if (__first != __last) {
size_type __n = 0;
distance(__first, __last, __n);
if (size_type(_M_end_of_storage - _M_finish) >= __n) {
const size_type __elems_after = _M_finish - __position;
iterator __old_finish = _M_finish;
if (__elems_after > __n) {
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
_M_finish += __n;
copy_backward(__position, __old_finish - __n, __old_finish);
copy(__first, __last, __position);
}
else {
_ForwardIterator __mid = __first;
advance(__mid, __elems_after);
uninitialized_copy(__mid, __last, _M_finish);
_M_finish += __n - __elems_after;
uninitialized_copy(__position, __old_finish, _M_finish);
_M_finish += __elems_after;
copy(__first, __mid, __position);
}
}
else {
const size_type __old_size = size();
const size_type __len = __old_size + max(__old_size, __n);
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
__STL_TRY {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
__new_finish = uninitialized_copy(__first, __last, __new_finish);
__new_finish
= uninitialized_copy(__position, _M_finish, __new_finish);
}
__STL_UNWIND((destroy(__new_start,__new_finish),
_M_deallocate(__new_start,__len)));
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
}
#else /* __STL_MEMBER_TEMPLATES */ /////////////////// ELSE //////////////////////////////////
template <class _Tp, class _Alloc>
void
vector<_Tp, _Alloc>::insert(iterator __position,
const_iterator __first,
const_iterator __last)
{
// 注意，原文是 __first != __last 这个括号打得太远，所以加判断式直接返回了
if (__first == __last)
return;
size_type __n = 0;
distance(__first, __last, __n); // 求距离 __n
// 现在的容量剩余，还足以放下新的 __n 个数据
if (size_type(_M_end_of_storage - _M_finish) >= __n) {
// 自插入点后的元素个数
// 这些元素要往后移。
const size_type __elems_after = _M_finish - __position;
iterator __old_finish = _M_finish;
// 这里好像有类似于 memmove 的算法：
if (__elems_after > __n) {
// 注意： __n 是比较中较小的数值，它是 __last - __first 表示要插入的元素个数
// 在此情况下，在移动数据的过程中，会出现“相互覆盖的数据区域”。
// STEP1: 首先把没有相交的（或称覆盖）可能的数据区，给移走：
// 自 _M_finish - __n 开始的数据，迁移 __n 个
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
// STEP2: 修改现在的数据未尾处
_M_finish += __n;
// STEP3: 把有相交范围内的数据移走，因为刚才已经把别的数据移走了，再怎么覆盖都行
// 这里用的是反向拷贝器，注意哦
copy_backward(__position, __old_finish - __n, __old_finish);
// STEP4: 最后把数据复制到 __position 处，从 __first 至 __last
copy(__first, __last, __position);
}
else {
// 在这里就不会出现覆盖区域，所以我们可以直接完全拷贝数据至末尾。
// STEP1: 先把需要复制的区域中，靠后的一段复制到现在的结束位置
uninitialized_copy(__first + __elems_after, __last, _M_finish);
_M_finish += __n - __elems_after;
// STEP2: 把原缓冲区的后半部分，移到现在的数据末尾
uninitialized_copy(__position, __old_finish, _M_finish);
_M_finish += __elems_after; // 现在的有效数据结束位置
// STEP3: 把需要复制的区域中，剩下的，前面没复制完的拷贝到指针位置
copy(__first, __first + __elems_after, __position);
}
}
else {
// 空间不够，需要重新分配
// 这是计算所需要的空间大小
const size_type __old_size = size();
// 一般都是分配2倍容量，但如果它不够，就按现在的 __n 来增加
const size_type __len = __old_size + max(__old_size, __n);
// 分配一块目标缓存
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
__STL_TRY {
// 原来的，在插入点前面的数据
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
// 现在要插入的数据
__new_finish = uninitialized_copy(__first, __last, __new_finish);
// 原来的，在插入点后面的数据
__new_finish
= uninitialized_copy(__position, _M_finish, __new_finish);
}
__STL_UNWIND((destroy(__new_start,__new_finish),
_M_deallocate(__new_start,__len)));
// 删除以前的缓存区
destroy(_M_start, _M_finish);
// 回收以前的缓存区
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
// 把新分配的，作为缓存
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
#endif /* __STL_MEMBER_TEMPLATES */ ///////////////////////// END IF /////////////////////////////////
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1174
#pragma reset woff 1375
#endif
__STL_END_NAMESPACE
#endif /* __SGI_STL_INTERNAL_VECTOR_H */
// Local Variables:
// mode:C++
// End:
