由于是指针管理内部数据，因此交换两个容器就只需要交换3个指针即可，所以是常数时间复杂度。同时，在 C++ 11 以后，移动构造函数、移动赋值函数也只需要移动三个指针即可，因此也是常数时间复杂度，其十分高效。而拷贝构造、拷贝赋值等操作则是一个一个的拷贝元素，时间复杂度为线性。
size() 和 capacity()
前面有讲过，size() 返回的是内部存放的元素的个数，而capacity() 则是已经预留空间的元素数，也已经举例讲过。更详细的说，我们可以把 vector 内部看作维护了三个指针 head,tail,end。其中 head 指向申请的内存块的首地址，end 指向了申请的内存块的尾地址(0-base，所以其实是在最后一个可用元素后面一个的位置)，tail 则是指向当前存放最后一个元素后面一个的位置。此时，size() 就等于 tail - head，而 capacity() 就等于 end - head，满足 head $\lt$ tail $\le$ end 。需要注意的是，[head,tail) 之间的元素都是执行过一次构造函数的，但是 [tail,end) 之间的元素的都是未初始化的，没有执行过构造函数。对于一些复杂类，这样的初始构造函数是十分重要的。
push_back() 和 emplace_back()
前面提到的 push_back() 和 emplace_back()，不同便是在于 emplace_back() 极大地利用了 C++ 11 的特性。push_back() 只能接受一个 T 类型参数，可以是左值或者右值。对于左值，新的元素将通过拷贝构造初始化；对于右值，将会执行移动构造函数来初始化新的元素。而emplace_back()可以接受多个参数，其可以通过完美转发，直接用这些参数作为新元素的构造函数，来构造尾部的新元素。
两者在用 T 类型、单个参数初始化的时候表现几乎一致，但是在非 T 类型或者多个参数初始化的时候，emplace_back() 效率显著高于 push_back()。具体来说，如果往尾部添加一个左值 T 对象，那么两者完全一致，都是执行一次拷贝构造。同理，传入一个右值 T 类型的对象，那么两者也同样，都是执行一次移动构造。但是，当传入一系列参数作为新元素的构造参数时，push_back()需要显式的调用 T() 在外部构造，然后vector 内部还会移动构造一次。而emplace_back()则直接在内部构造，只有一次构造，可以省去一次移动构造。
在以上这段代码中，push_back 非 T (本例中为 temp) 类的参数需要先构造出一个 T 类对象 ，而内部则用这个临时对象来移动构造出一个元素。而emplace_back 则直接在内部用这些参数执行构造函数。而如果 T 类对象的移动构造并不是非常高效，甚至可能等同拷贝构造(例如用固定长度的字符数组表示的字符串，正如本例子中的temp，那么此时，emplace_back便可以省去不必要的移动构造过程，大大提升效率。
值得注意的是，emplace_back和push_back有强异常保证。这意味着当扩容过程中发生了异常，那么原来的 vector 不会有任何的改变。这看起来没什么，但是这可能会极大的影响到程序的效率。因为在扩容时，需要将老的数据移到新的内存。一般来说，老数据都是没用的，应该调用的是移动构造而不是拷贝构造。但是，如果移动构造函数没有 noexcept 标识符，那么如果在移动某个元素 x 到 y 的过程中发生了异常，x的部分元素已经被移动到了 y ，我们不知道当前移动了多少，不知道如何把这部分数据移回 x ，也不确定移动回去会不会再发生异常。因此，原来 x 元素损坏了，数据丢失。为了满足强异常保证，此时只能使用拷贝构造。注意到了这点，我们对于明显不会抛出异常的移动构造函数应该加上 noexcept，否则可能影响程序效率，特别是对于拷贝开销大而移动开销小的类。详见cppreference。
在 C++ 11 之后，笔者认为应当用 emplace_back()替代push_back()以追求更高的效率。如果要减少模板的实例化(emplace_back是模板)并且对象易于移动(例如 std::string)，或者 追求旧版本的兼容性，那么再用push_back()。
/** * @brief A dynamic %array that can expand itself automatically. * In other words, user don't need to consider the allocation and * deallocation of space. * Note that if the elements within are pointers, the data pointed * to won't be touched. It's user's responsibility to manage them. * * @tparam value_t The type of elements stored within the %array. */ template <classvalue_t> classdynamic_array : private std::allocator <value_t> { protected: value_t *head; /* Head pointer to first element. */ value_t *tail; /* Tail pointer to one past the last element. */ value_t *term; /* Terminal pointer to the end of storage. */
/* Allocate memory of __n elements. */ value_t *alloc(size_t __n){ returnthis->allocate(__n); } /* Deallocate of the memory of head. */ voiddealloc(){ this->deallocate(head,capacity()); }
/* End of unfolding. */ voidreserved_push_back()noexcept{}
/* Push back a sequence of elements with space reserved in advance. */ template <classU,class ...Args> voidreserved_push_back(U &&obj,Args &&...objs){ this->construct(tail++,std::forward <U> (obj)); reserved_push_back(std::forward <Args> (objs)...); }
public:
/* Construct a new empty %array. */ dynamic_array() : head(nullptr),tail(nullptr),term(nullptr) {} /* Destroy all the elements and deallocate the space. */ ~dynamic_array() noexcept { this->destroy_n(head,size()); dealloc(); }
/* Construct a new %array from an initializer_list. */ dynamic_array(std::initializer_list <value_t> __l) : dynamic_array(__l.size()) { for(auto &iter : __l) { this->construct(tail++,std::move(iter)); } }
/* Construct a new %array with __n elements' space reserved. */ dynamic_array(size_t __n) { term = (head = tail = alloc(__n)) + __n; }
/** * @brief Construct a new %array filled with given length and element. * * @param __n The initial length of the %array. * @param obj The element to fill the %array. */ dynamic_array(size_t __n,constvalue_t &obj) : dynamic_array(__n) { while(tail != term) { this->construct(tail++,obj); } }
/** * @brief Construct a new %array with identical elements with another %array. * Note that no vacancy of %array remains, * which means the new %array's size() equals its capacity(). * * @param rhs The %array to copy from. * @attention Linear time complexity with respect to the size() of rhs, * multiplied by the construction time of one element. */ dynamic_array(const dynamic_array &rhs) : dynamic_array(rhs.size()) { for(constauto &iter : rhs) { this->construct(tail++,iter);} }
/** * @brief Construct a new %array with identical elements with another %array. * It will just take away the pointers from another %array. * * @param rhs The %array to move from. * @attention Constant time complexity in any case. */ dynamic_array(dynamic_array &&rhs) noexcept { head = rhs.head; tail = rhs.tail; term = rhs.term; rhs.head = rhs.tail = rhs.term = nullptr; }
/** * @brief Copy assign a new %array with identical elements with another %array. * Note that no vacancy of %array remains, * which means the new %array's size() equals its capacity(). * * @param rhs The %array to copy from. * @attention Linear time complexity with respect to the size() of rhs, * multiplied by the construction time of one element, * Note that there might be an additional time cost linear to the * elements destroyed. */ dynamic_array &operator = (const dynamic_array &rhs) { if(this != &rhs) { copy_range(rhs.begin(),rhs.size()); } return *this; }
/** * @brief Construct a new %array with identical elements with another %array. * It will just move the pointers from another %array. * * @param rhs The %array to move from. * @attention Constant time complexity in any case. */ dynamic_array &operator = (dynamic_array &&rhs) noexcept { if(this != &rhs) { this->~dynamic_array(); head = rhs.head; tail = rhs.tail; term = rhs.term; rhs.head = rhs.tail = rhs.term = nullptr; } return *this; }
/* Swap the content of two %array in constant time. */ dynamic_array &swap(dynamic_array &rhs)noexcept{ std::swap(head,rhs.head); std::swap(tail,rhs.tail); std::swap(term,rhs.term); return *this; } /* Swap the content of two %array in constant time. */ friendvoidswap(dynamic_array &lhs,dynamic_array &rhs)noexcept{ std::swap(lhs.head,rhs.head); std::swap(lhs.tail,rhs.tail); std::swap(lhs.term,rhs.term); }
public: /* Count of elements within the %array. */ size_tsize()constnoexcept{ return tail - head; } /** * @brief Count of elements the %array can hold * before the next allocation. */ size_tcapacity()constnoexcept{ return term - head; } /** * @brief Count of vacancy in the back of the %array * before the next allocation. */ size_tvacancy()constnoexcept{ return term - tail; } /* Test whether the %array is empty */ boolempty()constnoexcept{ return head == tail; }
/* Doing nothing to the %array. */ voidpush_back()noexcept{}
/** * @brief Push one element to the back of the %array. * * @param obj The object pushed back to initialize the element. * @attention Amortized constant time complexity, * multiplied by the construction time of one element. */ template <classU> voidpush_back(U &&obj){ if(tail == term) { reserve(size() << 1 | empty()); } this->construct(tail++,std::forward <U> (obj)); }
/** * @brief Push a sequnce of elements to the back of the %array. * * @param objs The objects pushed back to initialize the element. * @attention Amortized linear time complexity with respect to count of objs, * multiplied by the construction time of one element. */ template <class ...Args> voidpush_back(Args &&...objs){ size_t count = sizeof...(objs); // count >= 2 if(vacancy() < count) { size_t space = capacity() + empty(); reserve(space << (LOG2((size() + count - 1) / space) + 1)); } reserved_push_back(std::forward <Args> (objs)...); }
/** * @brief Construct one element after the back of the %array. * * @param obj The object pushed back to initialize the element. * @attention Amortized constant time complexity, * multiplied by the construction time of one element. */ template <class ...Args> voidemplace_back(Args &&...objs){ if(tail == term) { reserve(size() << 1 | empty()); } this->construct(tail++,std::forward <Args> (objs)...); }
/* Destroy the last element in the back, with no returning. */ voidpop_back()noexcept{ this->destroy(--tail); }
/** * @brief Clear all the elements in the %array. * Note that the capacity() of the %array won't shrink. * * @attention Linear complexity with respect to size(), * multiplied by the deconstruction time of one element. */ voidclear()noexcept{ this->destroy_n(head,size()); tail = head; }
/** * @brief Clear the vacancy of the %array. * Note that it will disable the optimization of the %array. * * @attention Linear complexity with respect to size(), * multiplied by the deconstruction time of one element. */ voidshrink(){ if(tail != term) { value_t *temp = alloc(size()); for(size_t i = 0 ; i < size() ; ++i) { this->construct(temp + i,std::move(head[i])); }
this->~dynamic_array(); term = tail = temp + size(); head = temp; } }
/** * @brief Resize the %array to __n. * The original data with index smaller than __n won't be touched. * If __n is greater than size(), elements will be appended to the back. * These new elements will be assigned by default construction function. * * @param __n The new size of the %array. * @attention Linear complexity with respect to __n , * multiplied by the construction time of one element. * Note that there might be an additional time cost linear to the * elements destroyed. */ voidresize(size_t __n){ if(__n <= size()) { size_t count = size() - __n; tail -= count; this->destroy_n(tail,count); } else { reserve(__n); size_t count = __n - size(); while(count--) { this->construct(tail++); } } }
/** * @brief Resize the %array to __n. * The original data with index smaller than __n won't be touched. * If __n is greater than size(), elements will be appended to the back. * These new elements will be assigned by val. * * @param __n The new size of the %array. * @param val The object to assign the new value. * @attention Linear complexity with respect to __n , * multiplied by the construction time of one element. * Note that there might be an additional time cost linear to the * elements destroyed. */ voidresize(size_t __n,constvalue_t &val){ if(__n <= size()) { size_t count = size() - __n; tail -= count; this->destroy_n(tail,count); } else { reserve(__n); size_t count = __n - size(); while(count--) { this->construct(tail++,val); } } }
/** * @brief Reserve space for __n elements. * If __n < capacity(), nothing will be done. * * @param __n The space reserved for elements. * @attention Linear time complexity with respect to __n, * only if __n >= capacity(), multiplied by the time of (de-)construction. * Otherwise, constant time complexity. */ voidreserve(size_t __n){ if(capacity() < __n) { value_t *temp = alloc(__n); for(size_t i = 0 ; i < size() ; ++i) { this->construct(temp + i,std::move(head[i])); }
this->~dynamic_array(); term = temp + __n; tail = temp + size(); head = temp; } }
/** * @brief Resize the %array to __n and assign all the elements by * default construction function of value_t. * * @param __n The new size of the %array. * @attention Linear complexity with respect to __n , * multiplied by the construction time of one element. * Note that there might be an additional time cost linear to the * elements destroyed. */ voidassign(size_t __n){ constvalue_t val = value_t(); if(__n <= size()) { size_t count = size() - __n; tail -= count; this->destroy_n(tail,count); for(auto &iter : *this) { iter = val; } } else { for(auto &iter : *this) { iter = val; } reserve(__n); size_t count = __n - size(); while(count--) this->construct(tail++); } }
/** * @brief Resize the %array to __n and assign all the elements by val. * * @param __n The new size of the %array. * @param val The object to assign the value. * @attention Linear complexity with respect to __n , * multiplied by the construction time of one element. * Note that there might be an additional time cost linear to the * elements destroyed. */ voidassign(size_t __n,constvalue_t &val){ if(__n <= size()) { size_t count = size() - __n; tail -= count; this->destroy_n(tail,count); for(auto &iter : *this) { iter = val; } } else { for(auto &iter : *this) { iter = val; } reserve(__n); size_t count = __n - size(); while(count--) this->construct(tail++,val); } } /** * @brief Copy elements from a range [first,last). * Note that the Iterator must be random access iterator. * Otherwise, you should provide the count of elements. * * @tparam Iterator A random access iterator type. * @param first Iterator to the first element. * @param last Iterator to one past the last element. * @attention Linear time complexity with respect to (last - first) * multiplied by the time of moving one element. * Note that there might be an additional time cost linear to the * elements destroyed. */ template <classIterator> voidcopy_range(Iterator first,Iterator last){ returncopy_range(first,last - first); }
/** * @brief Copy elements from a range [first,last). * The number of elements in the range should be exactly __n, * or unexpected error may happen. * * * @param first Iterator to the first element. * @param last Iterator to one past the last element. * @param __n Count of all the elements in the range. * @attention Linear time complexity with respect to __n, * multiplied by the time of copying one element. * Note that there might be an additional time cost linear to the * elements destroyed. */ template <classIterator> voidcopy_range(Iterator first,size_t __n){ if(__n <= capacity()) { value_t *temp = head; while(__n-- && temp != tail) { *(temp++) = *(first++); } ++__n; while(__n--) { this->construct(tail++,*(first++)); } this->destroy_n(temp,tail - temp); tail = temp; } else { this->~dynamic_array(); term = (tail = head = alloc(__n)) + __n; while(__n--) { this->construct(tail++,*(first++)); } } }
/** * @brief Move elements from a range [first,last). * Note that the Iterator must be random access iterator. * Otherwise, you should provide the count of elements. * * @tparam Iterator A random access iterator type. * @param first Iterator to the first element. * @param last Iterator to one past the last element. * @attention Linear time complexity with respect to (last - first), * multiplied by the time of moving one element. * Note that there might be an additional time cost linear to the * elements destroyed. */ template <classIterator> voidmove_range(Iterator first,Iterator last){ returnmove_range(first,last - first); }
/** * @brief Move elements from a range [first,last). * The number of elements in the range should be exactly __n, * or unexpected error may happen. * * @param first Iterator to the first element. * @param last Iterator to one past the last element. * @param __n Count of all the elements in the range. * @attention Linear time complexity with respect to __n, * multiplied by the time of moving one element. * Note that there might be an additional time cost linear to the * elements destroyed. */ template <classIterator> voidmove_range(Iterator first,size_t __n){ if(__n <= capacity()) { value_t *temp = head; while(__n-- && temp != tail) { *(temp++) = std::move(*(first++)); } ++__n; while(__n--) { this->construct(tail++,std::move(*(first++))); } this->destroy_n(temp,tail - temp); tail = temp; } else { this->~dynamic_array(); term = (tail = head = alloc(__n)) + __n; while(__n--) { this->construct(tail++,std::move(*(first++))); } } }
public: /* Return the pointer to the first element. */ value_t *data(){ return head; } /* Return the pointer to the first element. */ constvalue_t *data()const{ return head; } /* Subscript access to the data in the %array. */ value_t &operator [] (size_t __n) { return head[__n]; } /* Subscript access to the data in the %array. */ constvalue_t &operator [] (size_t __n) const { return head[__n]; }
/* Reference to the first element. */ value_t &front(){return *begin();} /* Reference to the last element. */ value_t &back(){return *--end();} /* Const reference to the first element. */ constvalue_t &front()const{return *cbegin();} /* Const reference to the last element. */ constvalue_t &back()const{return *--cend();}
using iterator = RandomAccess::iterator <value_t>; using const_iterator = RandomAccess::const_iterator <value_t>; using reverse_iterator = RandomAccess::reverse_iterator <value_t>; using const_reverse_iterator = RandomAccess::const_reverse_iterator <value_t>;
/* Iterator to the first element. */ iterator begin(){ return head; } /* Iterator to one past the last element. */ iterator end(){ return tail; }
/* Const_iterator to the first element. */ const_iterator begin()const{return head;} /* Const_iterator to one past the last element. */ const_iterator end()const{return tail;} /* Const_iterator to the first element. */ const_iterator cbegin()const{return head;} /* Const_iterator to one past the last element. */ const_iterator cend()const{return tail;}
/* Reverse iterator to the last element. */ reverse_iterator rbegin(){ return tail - 1; } /* Reverse iterator to one before the first element. */ reverse_iterator rend(){ return head - 1; }
/* Const_reverse_iterator to the last element. */ const_reverse_iterator rbegin()const{return tail - 1;} /* Const_reverse_iterator to one before the first element. */ const_reverse_iterator rend()const{return head - 1;} /* Const_reverse_iterator to the last element. */ const_reverse_iterator crbegin()const{return tail - 1;} /* Const_reverse_iterator to one before the first element. */ const_reverse_iterator crend()const{return head - 1;}
Wechat
