1、概述
deque 是 double-ended queue 的縮寫,又稱雙端隊列容器。是由一段一段的定量連續空間構成,可以向兩端發展,是以不論在尾部或頭部安插元素都十分迅速。 在中間部分安插元素則比較費時,因為必須移動其它元素。
我們看下deque的示意圖。
2、與vector的差別
- vector是單向開口的連續性空間,deque則是雙向開口的連續空間(連續是假象)。
- deque 容器也擅長在序列尾部添加或删除元素(時間複雜度為O(1)),而不擅長在序列中間添加或删除元素。
- vector擴容時經曆了申請空間、複制、釋放原空間的過程,deque是在頭或尾增加一端定量的連續空間,動态的以分段連續空間組合而成。
- vector對頭部的操作比較耗時,但deque擅長對頭部元素進行操作,時間複雜度為O(1)。
- vector存儲的元素是在連續的空間中,deque不能保證連續空間。
- deque的疊代器較vector疊代器來說複雜的多,是以,除非必要,請盡可能選擇vector而非deque。
3、中控器的概念
上面我們看到了,deque與vector還是有明顯的差別的。并且deque的連續空間是斷章取義的。deque有一段一段的定量連續空間構成。如果在deque的頭或者尾增加新空間。deque便會配置一段定量的連續空間,拼接在deque的頭或者尾部。保證這些連續空間上的連續假象。避免和vector一樣申請、複制、釋放。代價是比較複雜的疊代器設計。
deque采取一塊有連續空間的map(該map非stl中map)作為中控。該map的元素(我們可以看作是連結清單中的節點 - node),都是指針。指向另一段比較大的連續空間(稱作緩沖區)。這些緩存區才是deque容器的存儲主體。
簡單來說,我們可以了解為:在記憶體中有大小相同、彼此不連續的 n 個空間(這些空間各自是連續的)。另外有一塊連續的空間,這個空間裡面儲存了前面的那 n 個空間的指針。我們把這一塊連續的空間,稱作是deque的中控器。
舉個簡單的例子,我家有好多糧倉,但是了這些糧倉遍布在整個城市的各個區域,而在郊外的大别墅裡面了,有一塊地方儲存着去這些糧倉的地圖。
template <class _Tp, class _Alloc>
class _Deque_base {
public:
typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator;
typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
protected:
_Tp** _M_map; //中控器
size_t _M_map_size; //中控器的大小
};
由上面的定義我們可以很明顯的看出,map是一個指針,并且定義了size_t類型的變量來表示map的大小。我們再來看下map的初始化。
template <class _Tp, class _Alloc>
void _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
{
size_t __num_nodes =
__num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
_M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
_M_map = _M_allocate_map(_M_map_size);
_Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
_Tp** __nfinish = __nstart + __num_nodes;
__STL_TRY {
_M_create_nodes(__nstart, __nfinish);
}
__STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size),
_M_map = 0, _M_map_size = 0));
_M_start._M_set_node(__nstart);
_M_finish._M_set_node(__nfinish - 1);
_M_start._M_cur = _M_start._M_first;
_M_finish._M_cur = _M_finish._M_first +
__num_elements % __deque_buf_size(sizeof(_Tp));
}
我們能夠看到,首先,計算了有多少個node,然後再跟
_S_initial_map_size
比較取較大值。
_S_initial_map_size
是一個固定值 8 ,後續會說明。我們以 int 類型距離說明,通過計算,隻有當入參
__num_elements
的值 ≥ 2560 時,map的大小才會大于8,否則map的初始大小均為 8 。
下面我們看一看中控器的圖。
4、疊代器
前面我們已經說過了,deque和vector相似,但是它維護了表面上的空間連續,那麼他是怎麼維護的。deque的疊代器就會顯得至關重要。而疊代器中的operator++和operator- -這兩個運算子,承擔起了這份責任。
- 疊代器首先必須能夠指出分段的連續空間在哪裡,也就是我們說的緩沖區。
- 其次需要能夠判斷是否已經在緩沖區的邊緣。因為下一次的跳躍就得指向下一個或上一個緩沖區。
下面是deque疊代器的定義。
template <class _Tp, class _Ref, class _Ptr>
struct _Deque_iterator {
typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Ptr pointer;
typedef _Ref reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef _Tp** _Map_pointer;
typedef _Deque_iterator _Self;
_Tp* _M_cur; //此疊代器所指緩沖區的current元素
_Tp* _M_first; //此疊代器所指緩沖區的頭 使用push_front時,包含前面的空間
_Tp* _M_last; //此疊代器所指緩沖區的尾 包含未使用的空間
_Map_pointer _M_node; //指向中控器
...
}
從上面定義來看,一個疊代器裡面包含了所指向緩沖區的頭、尾、current元素以及這塊緩沖區對應中控器中的節點。
這個疊代器内部對指針的操作都進行了重載操作,是以我們不能像對待vector疊代器那樣來對待他。特别是當疊代器在一個緩沖區的邊緣,下一次的跳躍會進行緩沖區的切換時,我們看下下面的函數。
void _M_set_node(_Map_pointer __new_node) {
_M_node = __new_node;
_M_first = *__new_node;
_M_last = _M_first + difference_type(_S_buffer_size());
}
當進行node切換時,該疊代器的所指的緩沖區指向新的緩沖區,頭指向新緩沖區的頭,尾指向尾。
我們同時結合operator++或者operator- -操作來看會比較清楚一點。
_Self& operator++() {
++_M_cur; //切換至下一個元素
if (_M_cur == _M_last) { //如果已到達尾端
_M_set_node(_M_node + 1); //設定新的緩沖區,進行跳轉
_M_cur = _M_first; //指向新緩沖區的第一個第一個元素
}
return *this;
}
_Self operator++(int) { //後置
_Self __tmp = *this;
++*this;
return __tmp;
}
_Self& operator--() {
if (_M_cur == _M_first) {
_M_set_node(_M_node - 1);
_M_cur = _M_last; //需要注意的是,如果進行了減減,則current是先指向新緩沖區的尾,這個在後面我們驗證一下
}
--_M_cur;
return *this;
}
_Self operator--(int) {
_Self __tmp = *this;
--*this;
return __tmp;
}
上面我們隻是看了疊代在自增和自減時如果面臨着緩沖區的跳躍時進行的轉換,也就是單步跳躍,那麼多步跳躍呢?
_Self& operator+=(difference_type __n)
{
difference_type __offset = __n + (_M_cur - _M_first);
if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
_M_cur += __n;
else {
difference_type __node_offset =
__offset > 0 ? __offset / difference_type(_S_buffer_size())
: -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
_M_set_node(_M_node + __node_offset);
_M_cur = _M_first +
(__offset - __node_offset * difference_type(_S_buffer_size()));
}
return *this;
}
由上面的定義我們可以看出,多步跳躍跟單步的是差不多的,值得注意的是,如果多步跳躍的步數比較大時,可能會進行map的跨越,而不單單是在同一個緩沖區中。
我們基本上已經全部看了疊代器的實作,但如果隻有上面所說的這些鞋可能還是會比較迷糊,還是不能實際的了解,那麼,下面我們通過一張圖來看下疊代器長啥樣。以便更好的了解。
由上圖可以看出,我們畫了兩個疊代器,begin() 和 end() 函數傳回的疊代器,如果最後一個緩沖區沒有存滿資料,則end()傳回的疊代器能夠指向他。
5、定義
在看deque容器的定義之前,我們先看看他的父類。
template <class _Tp, class _Alloc>
class _Deque_base {
public:
typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator;
typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
typedef _Alloc allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
_Deque_base(const allocator_type&, size_t __num_elements)
: _M_map(0), _M_map_size(0), _M_start(), _M_finish() {
_M_initialize_map(__num_elements);
}
_Deque_base(const allocator_type&)
: _M_map(0), _M_map_size(0), _M_start(), _M_finish() {}
~_Deque_base();
protected:
void _M_initialize_map(size_t);
void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
enum { _S_initial_map_size = 8 }; //使用枚舉的方式可以在頭檔案中定義int類型的常量,初始化map的大小
protected:
_Tp** _M_map; //指向map,map是塊連續空間,其中的每個元素都是一個指針(node),指向一塊連續的記憶體空間(緩沖區)
size_t _M_map_size; //map的大小,初始值為0
iterator _M_start; //表現為第一個節點
iterator _M_finish; //表現為最後一個節點
typedef simple_alloc<_Tp, _Alloc> _Node_alloc_type;
typedef simple_alloc<_Tp*, _Alloc> _Map_alloc_type;
_Tp* _M_allocate_node()
{ return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); }
void _M_deallocate_node(_Tp* __p)
{ _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); }
_Tp** _M_allocate_map(size_t __n)
{ return _Map_alloc_type::allocate(__n); }
void _M_deallocate_map(_Tp** __p, size_t __n)
{ _Map_alloc_type::deallocate(__p, __n); }
};
沒什麼特别需要說明的,注意一下其中的注釋就行了。
template <class _Tp, class _Alloc>
void _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
{
for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
_M_deallocate_node(*__n);
}
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class deque : protected _Deque_base<_Tp, _Alloc> {
// requirements:
__STL_CLASS_REQUIRES(_Tp, _Assignable);
typedef _Deque_base<_Tp, _Alloc> _Base;
public: // Basic types
typedef _Tp value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
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(); }
public: // Iterators
typedef typename _Base::iterator iterator;
typedef typename _Base::const_iterator const_iterator;
#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: // Internal typedefs
typedef pointer* _Map_pointer;
static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
protected:
#ifdef __STL_USE_NAMESPACES
using _Base::_M_initialize_map;
using _Base::_M_create_nodes;
using _Base::_M_destroy_nodes;
using _Base::_M_allocate_node;
using _Base::_M_deallocate_node;
using _Base::_M_allocate_map;
using _Base::_M_deallocate_map;
using _Base::_M_map;
using _Base::_M_map_size;
using _Base::_M_start;
using _Base::_M_finish;
#endif /* __STL_USE_NAMESPACES */
};
6、特點
當需要向容器的兩邊不停的添加或者删除元素的時候,應該使用deque。比如生産者和消費者中間的倉庫。
7、建立方法
#include<deque>
using namespace std;
1、建立一個空的deque
定義一個元素為int類型的空deque。
這種方法跟vector、array等一樣,在建立了空的deque之後,添加或者删除元素,這種方式比較常見。
2、建立一個含有 n 個元素的deque
deque(size_type __n) : _Base(allocator_type(), __n)
{ _M_fill_initialize(value_type()); }
建立了有8個元素的deque,其中每個元素的預設值均為0。
3、建立一個含有 n 個元素的deque,并為每個元素指定初始值
deque(size_type __n, const value_type& __value, const allocator_type& __a = allocator_type()) : _Base(__a, __n)
{ _M_fill_initialize(__value); }
建立了有8個元素的deque,其中每個元素的初始值均為5。
4、通過拷貝一個deque來建立一個新的deque
deque(const deque& __x) : _Base(__x.get_allocator(), __x.size())
{ uninitialized_copy(__x.begin(), __x.end(), _M_start); }
std::deque<int> data(8);
std::deque<int> data1(data);
拷貝data建立新的deque data1。這種方式下,新舊deque容器的元素類型必須保持一緻。
5、通過拷貝其他類型的容器來建立deque
deque(const value_type* __first, const value_type* __last,
const allocator_type& __a = allocator_type())
: _Base(__a, __last - __first)
{ uninitialized_copy(__first, __last, _M_start); }
deque(const_iterator __first, const_iterator __last,
const allocator_type& __a = allocator_type())
: _Base(__a, __last - __first)
{ uninitialized_copy(__first, __last, _M_start); }
int array[] = {1, 2, 3, 4};
std::deque<int> data4(array, array + 4);
vector<int> primes {2, 3, 5, 7, 11, 13, 17, 19};
std::deque<int> data5(++primes.begin(), --primes.end());
6、指派
deque& operator= (const deque& __x) {
const size_type __len = size();
if (&__x != this) {
if (__len >= __x.size())
erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
else {
const_iterator __mid = __x.begin() + difference_type(__len);
copy(__x.begin(), __mid, _M_start);
insert(_M_finish, __mid, __x.end());
}
}
std::deque<int> data(8);
std::deque<int> data1 = data;
下面我們通過一個例子來看看上面的這些情況。
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int main(int argc, char* argv[])
{
deque<double> data; //建立一個double 類型的空deque容器
cout << data.size() << " " << data.max_size() << endl; //0 2305843009213693951
deque<int> data1(10); //建立一個int類型的有10個元素deque容器,每個元素預設為0
cout << data1.size() << " " << data1.max_size() << endl; //10 4611686018427387903
for(deque<int>::iterator itor = data1.begin(); itor != data1.end(); ++itor)
{
cout << *itor << " "; //0 0 0 0 0 0 0 0 0 0
}
cout << endl << data1.begin()._S_buffer_size() << endl; //128 現在的版本已經對緩沖區這塊做了修改,定量大小為 512byte
for(int nIndex = 1; nIndex <= 130; ++nIndex)
{
data.push_back(nIndex);
}
for(deque<double>::iterator itor = data.begin(); itor != data.end(); ++itor)
{
cout << *itor << " "; // 1 2 3 ... 128 129 130
}
cout << endl << (++data.begin())._S_buffer_size() << " data size : " << data.size() << endl; //64 data size : 130
cout << *(data.begin()._M_first) << " " << *(data.begin()._M_last - 1) << endl; // 1 64 first cache
cout << *(data.end()._M_first) << " " << *(data.end()._M_cur - 1) << " " << *(data.end()._M_last - 1) << endl; //129 130 0
cout << data.begin()._M_node << " " << data.end()._M_node << endl; //0x1a1f48 0x1a1f58 //實際上被用掉的map的長度 相減為十六進制10 即16,兩個double長度然後加end,map實際使用 3
deque<int> data2(10, 4); //建立一個int類型的有10個元素deque容器,每個元素預設為4
for(deque<int>::iterator itor = data2.begin(); itor != data2.end(); ++itor)
{
cout << *itor << " "; //4 4 4 4 4 4 4 4 4 4
}
cout << endl;
deque<int> data3(data2);
for(deque<int>::iterator itor = data3.begin(); itor != data3.end(); ++itor)
{
cout << *itor << " "; //4 4 4 4 4 4 4 4 4 4
}
cout << endl;
int array[] = {1, 2, 3, 4};
deque<int> data4(array, array + 4);
for(deque<int>::iterator itor = data4.begin(); itor != data4.end(); ++itor)
{
cout << *itor << " "; //1 2 3 4
}
cout << endl;
vector<int> primes {2, 3, 5, 7, 11, 13, 17, 19};
deque<int> data5(++primes.begin(), --primes.end());
for(deque<int>::iterator itor = data5.begin(); itor != data5.end(); ++itor)
{
cout << *itor << " "; //3 5 7 11 13 17
}
cout << endl;
deque<int> data6 = data4;
for(deque<int>::iterator itor = data6.begin(); itor != data6.end(); ++itor)
{
cout << *itor << " "; //1 2 3 4
}
cout << endl;
return 0;
}
運作結果如下:
我們針對上面的例子,對其中的一些資料說明一下。
首先,我們看下deque中每個緩沖區的大小。先看下源碼中的函數:
inline size_t __deque_buf_size(size_t __size) {
return __size < 512 ? size_t(512 / __size) : size_t(1);
}
由上面的函數我們能夠看出,當__size < 512 時,緩沖區的大小為512byte。再檢視源碼中調用該函數的地方,發現,該函數的入參時固定的,為 sizeof(_Tp);也就是說,現在的stl版本中,已經固定了deque的緩沖區大小為512byte。通過上面的例子我們也得到了驗證。
然後我們再看下一個疊代器中的,也就是一個緩存區的大小和deque的大小。這一點在上面的疊代器這一節中我們已經有所了解了。
接下來我們看下
data.begin()
和
data.end()
這兩個疊代器中的資料存儲規律,我們通過列印發現:
計算一下,data的size是130,一個緩沖區中能存放64個double類型資料,那也就是說,data.end()這個疊代器中的資料隻有兩個,看下上面的列印就能知道。這樣的結果也是我們驗證上面疊代器中疊代器的相關屬性。
最後我們看下data這個deque中的map使用情況,我們在上面知道了,deque data中map的大小為8,我們通過列印data.begin()和data.end()中node的位址來計算map的實際使用量。如下,相減為十六進制10 即16,兩個double長度(準确的來說,是兩個指針的大小,因為我的系統是64位的,并且deque裡面的map存放的是_Tp **的指針,指向每一個緩沖區),然後再加上end()的使用,map實際使用大小為3。
8、map的空間擴充
我們來通過一個例子看一下map是怎麼進行空間擴充的。實踐是學東西的一個很好的方法,以後有不懂的時候,動手實踐下可能就會了。
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int main(int argc, char* argv[])
{
deque<double> data; //建立一個double 類型的空deque容器
for(int nIndex = 1; nIndex <= 511; ++nIndex)
{
data.push_back(nIndex);
}
cout << *(data.begin()._M_first) << " " << *(data.begin()._M_last - 1) << " " << data.size() << endl; //1 64 511
cout << *((--data.end())._M_first) << " " << *((--data.end())._M_cur) << " " << *((--data.end())._M_last - 1) << endl; //449 511 0
cout << data.begin()._M_node << " " << data.end()._M_node << endl; //0x811fd0 0x812008
data.push_back(512);
data.push_back(513);
cout << data.begin()._M_node << " " << data.end()._M_node << endl; //0x811fd0 0x812010
data.push_front(514);
data.push_front(515);
cout << *(data.begin()._M_cur) << " " << *(data.begin()._M_last - 1) << endl; //515 514
cout << *(data.end()._M_first) << " " << *(data.end()._M_cur - 1) << " " << *(data.end()._M_last - 1) << endl; //513 513 0
cout << data.begin()._M_node << " " << data.end()._M_node << endl; //0x811fc8 0x812010
return 0;
}
運作結果:
通過上面的例子可以看到,我們首先給data裡面
push_back
511 個元素,剛好在最後一個map未被使用,此時記錄
data.begin()
和
data.end()
包含的node的位址。值為:
0x811fd0 0x812008
兩者相差56,為7個double類型的空間,然後給data裡面再push_back兩個元素。記錄data.begin()和data.end()包含的node的位址,值為:
0x811fd0 0x812010
,發現begin()的值未變,但是end()的值增加了8。其實隻push_back一個元素也是同樣的結果。因為在push元素之後,發現改緩沖區已經沒有空間了,于是申請了下一段連續的空間(緩沖區)。
是以,我們可以得出:deque中map的空間進行擴充使用的是移動構造,并非是拷貝構造,跟vector的空間擴充是有差別的。
移動構造:移動構造函數是c++11的新特性,移動構造函數傳入的參數是一個右值 用&&标出。一般來說左值可以通過使用
std:move
方法強制轉換為右值。移動構造函數首先将傳遞參數的記憶體位址空間接管,然後将内部所有指針設定為nullptr,并且在原位址上進行新對象的構造,最後調用原對象的的析構函數,這樣做既不會産生額外的拷貝開銷,也不會給新對象配置設定記憶體空間。
拷貝構造:申請->複制->釋放原空間。拷貝構造函數是先将傳入的參數對象進行一次深拷貝,再傳給新對象。這就會有一次拷貝對象的開銷,并且進行了深拷貝,就需要給對象配置設定位址空間。
移動構造函數就是為了解決這個拷貝開銷而産生的。
9、操作資料的方法
1、重載運算符[]
deque<int> data(5, 2);
int a = data[3]; //2
int b = data[5]; //0
int c = data[128]; //錯誤
可以看到,容器名[n]的這種方式,不僅可以通路容器中的元素,還可以對其進行修改。但需要注意的是,使用此方法需確定下标 n 的值不會超過容器中存儲元素的個數,否則會發生越界通路的錯誤。
同時,如果某個緩沖區有未使用的空間,通路這些空間不會造成程式錯誤,隻會傳回一個不确定的值。
2、at(int pos)
有效地避免越界通路,由于該函數會傳回容器中指定位置處元素的引用形式,是以利用該函數的傳回值,既可以通路指定位置處的元素,如果需要還可以對其進行修改。
at() 成員函數會自行判定通路位置是否越界,如果越界則抛出
std::out_of_range
異常。
deque<int> data(5, 2);
std::cout << data.at(2) << endl;
//std::cout << data.at(5) << endl; std::out_of_range
3、front()和back()
它們分别傳回 deque容器中第一個和最後一個元素的引用,通過利用它們的傳回值,可以通路(甚至修改)容器中的首尾元素。
deque<int> data(5, 2);
std::cout << data.front() << endl;
std::cout << data.back() << endl;
3、push、pop、insert
成員函數 | 功能 |
---|---|
push_back() | 在容器現有元素的尾部添加一個元素 |
pop_back() | 移除容器尾部的一個元素 |
push_front() | 在容器現有元素的頭部添加一個元素 |
pop_front() | 移除容器尾部的一個元素 |
emplace_back() | C++11 新添加的成員函數,其功能是在容器尾部生成一個元素 |
emplace_front() | C++ 11 新添加的成員函數,其功能是在容器頭部生成一個元素 |
insert() | 在指定的位置直接生成一個元素。 |
emplace() | C++ 11 新添加的成員函數,其功能是 insert() 相同,即在指定的位置直接生成一個元素。 |
push_back() 和push_front() 都是給容器中插入資料,不同的事一個是插在容器的尾部,一個則是插在容器的頭部。
void push_back(const value_type& __t) {
if (_M_finish._M_cur != _M_finish._M_last - 1) {
construct(_M_finish._M_cur, __t);
++_M_finish._M_cur;
}
else
_M_push_back_aux(__t);
}
void push_back() {
if (_M_finish._M_cur != _M_finish._M_last - 1) {
construct(_M_finish._M_cur);
++_M_finish._M_cur;
}
else
_M_push_back_aux();
}
上面是push_back函數的原型。push_front則差不多的。
insert方法的實作跟其他容器的都差不多。主要有4種方法。
文法格式 | 功能 |
---|---|
iterator insert(pos, elem) | 在疊代器 pos 指定的位置之前插入一個新元素elem,并傳回表示新插入元素位置的疊代器。 |
iterator insert(pos, n, elem) | 在疊代器 pos 指定的位置之前插入 n 個元素 elem,并傳回表示第一個新插入元素位置的疊代器。 |
iterator insert(pos, first, last) | 在疊代器 pos 指定的位置之前,插入其他容器(不僅限于vector)中位于 [first,last) 區域的所有元素,并傳回表示第一個新插入元素位置的疊代器。 |
iterator insert(pos, initlist) | 在疊代器 pos 指定的位置之前,插入初始化清單中所有的元素,并傳回表示第一個新插入元素位置的疊代器。 |
std::deque<int> data {1, 2};
//第一種格式用法
data.insert(data.begin() + 1, 3); //{1, 3, 2}
//第二種格式用法
data.insert(data.end(), 2, 5); //{1, 3, 2, 5, 5}
//第三種格式用法
std::array<int, 3> array{ 7, 8, 9 };
data.insert(data.end(), array.begin(), array.end()); //{1, 3, 2, 5, 5, 7, 8, 9 }
//第四種格式用法
data.insert(data.end(), { 10,11 }); //{1, 3, 2, 5, 5, 7, 8, 9, 10, 11 }
4、為什麼要有emplace系列的函數
emplace系列的函數是在C++11之後才添加的,主要是因為引入了移動構造可以減少開銷。具體的内容與
std::map
的emplace系列函數是一樣的操作。測試用例也差不多。如果有興趣,請看上一篇《兩小時帶你從0學習stl庫–map》第九節并自行測試。