STL（二）vector 动态数组

蔚落 2022-06-03 22:48 202阅读 0赞

vector的底层数据结构是动态数组，因此，vector的数据安排以及操作方式与std::array十很相似，它们间的唯一差别在于对空间的运用灵活性上。array为静态数组，有着静态数组最大的缺点：每次只能分配一定大小的存储空间，当有新元素插入时，要经历**“找到更大的内存空间”->“把数据复制到新空间” ->“销毁旧空间” 三部曲**， 对于std::array而言，这种空间管理的任务压在使用它的用户身上，用户必须把握好数据的数量，尽量在第一次分配时就给数据分配合理的空间（这有时很难做到)，以防止“三部曲”带来的代价，而数据溢出也是静态数组使用者需要注意的问题。而vector用户不需要亲自处理空间运用问题。vector是动态空间，随着新元素的插入，旧存储空间不够用时，vector内部机制会自行扩充空间以容纳新元素，当然，这种空间扩充大部分情况下（几乎是)也逃脱不了“三部曲”，只是不需要用户自己处理，而且vector处理得更加安全高效。vector的实现技术关键就在于对其大小的控制以及重新配置时数据移动效率。

标准库的实现者使用了这样的内存分配策略：以最小的代价连续存储元素。为了使vector容器实现快速的内存分配，其实际分配的容量要比当前所需的空间多一些(预留空间)，vector容器预留了这些额外的存储区用于存放添加的新元素，于是不必为每个新元素进行一次内存分配。当继续向容器中加入元素导致备用空间被用光（超过了容量 capacity)，此时再加入元素时vector的内存管理机制便会扩充容量至两倍，如果两倍容量仍不足，就扩张至足够大的容量。容量扩张必须经历“重新配置、元素移动、释放原空间”这个浩大的工程。

当然，vector的每种实现都可以自由地选择自己的内存分配策略，分配多少内存取决于其实现方式，不同的库采用不同的分配策略。

迭代器失效问题

(1)vector管理的是连续的内存空间，在容器中插入（或删除)元素时，插入（或删除)点后面的所有元素都需要向后（或向前)移动一个位置，指向发生移动的元素的迭代器都失效。这里以插入操作示例：

![20171128190248794][]

(2)随着元素的插入，原来分配的连续内存空间已经不够且无法在原地拓展新的内存空间，整个容器会被copy到另外一块内存上，此时指向原来容器元素的所有迭代器通通失效。

![20171128190320487][]

(3)删除元素后，指向被删除元素的迭代器失效，这是显而易见的。

vector使用优劣

优点：

(1) 不指定一块内存大小的数组的连续存储，即可以像数组一样操作，但可以对此数组进行动态操作。通常体现在push\_back() pop\_back()

(2) 随机访问方便，即支持\[ \]操作符和vector.at()

(3) 节省空间。

缺点：

(1) 在内部进行插入删除操作效率低。

(2) 只能在vector的最后进行push和pop，不能在vector的头进行push和pop。

(3) 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放

定义：

# std::vector #

template < class T, class Alloc = allocator<T> > class vector; // generic template

1、构造函数

# std::[vector][]::vector #

<table style="font-family:verdana,arial,helvetica,sans-serif; font-size:12px; border-collapse:collapse; border-bottom:0px; width:722px; background-color:rgb(250,255,250)"> 
 <tbody> 
  <tr style="border-bottom:1px dashed rgb(240,240,240)"> 
   <th style="text-align:right; font-style:italic">default (1)</th> 
   <td style="padding-left:12px"> <pre style="margin-top:0px; margin-bottom:0px"><strong>explicit vector (const allocator_type&amp; alloc = allocator_type());
</strong></pre> <pre style="margin-top:0px; margin-bottom:0px"><strong>
</strong></pre> </td> 
  </tr> 
  <tr style="border-bottom:1px dashed rgb(240,240,240); background:rgb(242,255,242)"> 
   <th style="text-align:right; font-style:italic">fill (2)</th> 
   <td style="padding-left:12px"> <pre style="margin-top:0px; margin-bottom:0px"><strong>explicit vector (size_type n, const value_type&amp; val = value_type(),</strong></pre> <pre style="margin-top:0px; margin-bottom:0px"><strong>const allocator_type&amp; alloc = allocator_type());
</strong></pre> <pre style="margin-top:0px; margin-bottom:0px"><strong>
</strong></pre> </td> 
  </tr> 
  <tr style="border-bottom:1px dashed rgb(240,240,240)"> 
   <th style="text-align:right; font-style:italic">range (3)</th> 
   <td style="padding-left:12px"> <pre style="margin-top:0px; margin-bottom:0px"><strong>template &lt;class InputIterator&gt;
vector (InputIterator first, InputIterator last, </strong></pre> <pre style="margin-top:0px; margin-bottom:0px"><strong>const allocator_type&amp; alloc = allocator_type());
</strong></pre> </td> 
  </tr> 
  <tr style="border-bottom:1px dashed rgb(240,240,240); background:rgb(242,255,242)"> 
   <th style="text-align:right; font-style:italic">copy (4)</th> 
   <td style="padding-left:12px"> <pre style="margin-top:0px; margin-bottom:0px"><strong>vector (const vector&amp; x);</strong></pre> </td> 
  </tr> 
 </tbody> 
</table>

示例：

2、成员函数

[**vector::operator=**][vector_operator]

Assign content  (public member function )

vector& operator= (const vector& x);

[**vector::assign**][vector_assign]

Assign vector content  (public member function )

<table style="font-family:verdana,arial,helvetica,sans-serif; font-size:12px; color:black; border-collapse:collapse; border-bottom:0px; width:722px; background-color:rgb(250,255,250)"> 
 <tbody> 
  <tr style="border-bottom:1px dashed rgb(240,240,240)"> 
   <th style="text-align:right; font-weight:normal; font-style:italic"><span style="color:#333333">range (1)</span></th> 
   <td style="padding-left:12px"> <pre style="margin-top:0px; margin-bottom:0px"><span style="color:#333333">template &lt;class InputIterator&gt;
 void assign (InputIterator first, InputIterator last);
</span></pre> </td> 
  </tr> 
  <tr style="border-bottom:1px dashed rgb(240,240,240); background:rgb(242,255,242)"> 
   <th style="text-align:right; font-weight:normal; font-style:italic"><span style="color:#333333">fill (2)</span></th> 
   <td style="padding-left:12px"> <pre style="margin-top:0px; margin-bottom:0px"><span style="color:#333333">void assign (size_type n, const value_type&amp; val);</span></pre> </td> 
  </tr> 
 </tbody> 
</table>

[**vector::reserve**][vector_reserve]

Request a change in capacity  (public member function )

void reserve (size_type n);

**[vector::resize][vector_resize]**

Change size  (public member function )

void resize (size_type n, value_type val = value_type());

[**vector::clear**][vector_clear]

Clear content  (public member function )

void clear();

示例：

#include<iostream>
    #include<vector>
    
    using namespace std;
    
    template<typename T>
    void Print(T vec)
    {
    	T::iterator iter = vec.begin();
    	for (; iter != vec.end();)
    	{
    		cout << *iter++ << " ";
    	}
    	cout << endl;
    }
    
    
    int main()
    {
    	vector<int>a1;
    	vector<int>a2(6, 10);
    	vector<int>a3(a2.begin(), a2.end());
    	vector<int>a4(a3);
    	Print(a3);
    	Print(a4);
    
    
    	vector<int>a5;
    	vector<char>a6;
    	a1 = a3;
    	Print(a1);
    
    	a5.assign(a4.begin(), a4.end());
    	Print(a5);
    
    	a6.assign(6, 'A');
    	Print(a6);
    
    
    	//capacity空间大小，size占用空间中多少位
    	//重置空间大小reserve
    	cout << "a6 capacity:" << a6.capacity() << "  a6 size:" << a6.size() << endl;
    	a6.reserve(20);
    	cout << "a6 capacity:" << a6.capacity() << "  a6 size:" << a6.size() << endl;
    	cout<<endl;
    
    
    	//resize调整占用空间位数，不足补零
    	a5.resize(10);
    	Print(a5);
    	cout << "a5 capacity:" << a5.capacity() << "  a5 resize:" << a5.size() << endl;
    	//不足补6
    	a5.resize(12, 6);
    	Print(a5);
    	cout << "a5 capacity:" << a5.capacity() << "  a5 resize:" << a5.size() << endl;
    	cout << endl;
    
    	//分配的空间大小不变，但是清除占用空间位数
    	a5.clear();
    	Print(a5);
    	cout << "a5 capacity:" << a5.capacity() << "  a5 size:" << a5.size() << endl;
    
    
    
    
    	system("pause");
    	return 0;
    }

3、元素访问

# std::[vector][]::data #

value_type* data() noexcept;
    const value_type* data() const noexcept;

返回指向作为元素存储工作的底层数组的指针。指针满足范围 `[data(); data() + size())` 始终是合法范围，即使容器为空

vector::at  
Access element (public member function )  
reference at (size\_type n);  
const\_reference at (size\_type n) const;  
  
  
vector::operator\[\]  
Access element (public member function )  
reference operator\[\] (size\_type n);  
const\_reference operator\[\] (size\_type n) const;  
  
  
vector::front  
Access first element (public member function )  
 reference front();  
const\_reference front() const;  
  
  
vector::back  
Access last element (public member function )  
reference back()  
const\_reference back() const;

示例：

#include<iostream>
    #include<vector>
    
    
    using namespace std;
    
    
    template<typename T>
    void Print(T vec)
    {
    	T::iterator iter = vec.begin();
    	for (; iter != vec.end();)
    	{
    		cout << *iter++ << " ";
    	}
    	cout << endl;
    }
    
    
    
    
    int main()
    {
    
    
    
    
    	vector<char> a;
    	for (int i = 0; i < 10; i++)
    	{
    		a.push_back((char)i);
    	}
    
    
    	Print(a);
    	cout <<"data: "<< *(a.data()+6) << endl;
    	cout << "[]: " << a[6] << endl;
    	cout << "front: " << a.front() << endl;
    	cout << "back: " << a.back() << endl;
    	cout << "at: " << a.at(6) << endl;
    
    
    	system("pause");
    	return 0;
    }

4、迭代器  
vector::begin  
Return iterator to beginning (public member function )  
     iterator begin();  
const\_iterator begin() const;  
  
  
vector::end  
Return iterator to end (public member function )  
iterator end();  
const\_iterator end() const;  
  
反转：  
vector::rbegin  
Return reverse iterator to reverse beginning (public member function )  
 reverse\_iterator rbegin();  
const\_reverse\_iterator rbegin() const;  
  
  
vector::rend  
Return reverse iterator to reverse end (public member function )  
  reverse\_iterator rend();  
const\_reverse\_iterator rend() const;  
  
  
示例：

#include<iostream>
    #include<vector>
    
    
    using namespace std;
    
    
    template<typename T>
    void Print(T vec)
    {
    	T::iterator iter = vec.begin();
    	for (; iter != vec.end();)
    	{
    		cout << *iter++ << " ";
    	}
    	cout << endl;
    }
    //反转
    template<typename T>
    void Print1(T vec)
    {
    	T::reverse_iterator iter = vec.rbegin();
    	for (; iter != vec.rend();)
    	{
    		cout << *iter++ << " ";
    	}
    	cout << endl;
    }
    
    
    
    
    int main()
    {
    	vector<char> a;
    	for (int i = 0; i < 10; i++)
    	{
    		a.push_back((char)i);
    	}
    
    
    	Print(a);
    	Print1(a);
    
    
    
    
    	system("pause");
    	return 0;
    }

常量迭代器：  
vector::cbegin

Return const\_iterator to beginning (public member function )  
 const\_iterator cbegin() const noexcept;  
  
  
vector::cend  
Return const\_iterator to end (public member function )  
const\_iterator cend() const noexcept;  
  
常量反转迭代器：  
vector::crbegin  
Return const\_reverse\_iterator to reverse beginning (public member function )  
const\_reverse\_iterator crbegin() const noexcept;  
  
  
vector::crend  
Return const\_reverse\_iterator to reverse end (public member function )  
const\_reverse\_iterator crend() const noexcept;

#include<iostream>
    #include<vector>
    #include<ctime>
    using namespace std;
    
    
    template<typename T>
    void Print(T vec)
    {
    	T::const_iterator iter = vec.cbegin();
    	for (; iter != vec.cend();)
    	{
    		cout << *iter++ << " ";
    	}
    	cout << endl;
    }
    
    
    template<typename T>
    void Print1(T vec)
    {
    	T::const_reverse_iterator iter = vec.crbegin();
    	for (; iter != vec.crend();)
    	{
    		cout << *iter++ << " ";
    	}
    	cout << endl;
    }
    
    
    
    
    int main()
    {
    	srand(time(0));
    	vector<char> a;
    	for (int i = 0; i < 10; i++)
    	{
    		a.push_back((char)rand()%10);
    	}
    
    
    	Print(a);
    	Print1(a);
    
    
    
    
    	system("pause");
    	return 0;
    }

5、容量  
vector::reserve  
  Request a change in capacity (public member function )

vector::size  
  Return size (public member function )

vector::max\_size  
Return maximum size (public member function )

vector::resize  
  Change size (public member function )

vector::shrink\_to\_fit  
Shrink to fit (public member function )  
它是减少 capacity() 到 size()非强制性请求。请求是否达成依赖于实现。  
若发生重分配，则所有迭代器，包含尾后迭代器，和所有到元素的引用都被非法化。若不发生重分配，则没有迭代器或引用被非法化。  
  
  
vector::capacity  
Return size of allocated storage capacity (public member function )

std::vector::empty

bool empty() const

//vector 使用数组做出来的
    //数组的缺点：定义长度不能改                   优点：下标访问比较快
    //capacity和reserve成员  容量每次增加原有的 50%(取整)，capacity顺序:0,1,2,4,6,9,13,19.....
    
    
    #include<iostream>
    #include<vector>
    
    
    using namespace std;
    
    
    int main()
    {
    	vector<int> a;
    	cout << "大小：" << a.size()  << " 容量：" << a.capacity() << endl;
    
    
    	a.push_back(1);
    	cout << "大小：" << a.size() << " 容量：" << a.capacity() << endl;
    	a.push_back(1);
    	cout << "大小：" << a.size()  << " 容量：" << a.capacity() << endl;
    	a.push_back(1);
    	a.push_back(1);
    	cout << "大小：" << a.size()  << " 容量：" << a.capacity() << endl;
    	a.push_back(1);
    	a.push_back(1);
    	cout << "大小：" << a.size()  << " 容量：" << a.capacity() << endl;
    	a.push_back(1);
    	a.push_back(17);
    	cout << "大小：" << a.size()  << " 容量：" << a.capacity() << endl;
    	a.push_back(100);
    	a.push_back(1);
    	a.push_back(1);
    	cout << "大小：" << a.size()  << " 容量：" << a.capacity() << endl;
    	a.push_back(17);
    	a.push_back(100);
    	a.push_back(10);
    
    
    	cout << "大小：" << a.size()  << " 容量：" << a.capacity() << endl;
    
    
    	cout << endl;
    	a.shrink_to_fit();//将capacity大小调整与size一样
    	cout << "大小：" << a.size() << "  容量：" << a.capacity() << endl;
    
    
    	system("pause");
    	return 0;
    
    
    }

6、修改器  
clear 清除内容 (公开成员函数)

insert 插入元素 (公开成员函数)  
iterator insert( iterator pos, const T& value );(1)

iterator insert( const\_iterator pos, const T& value );  
iterator insert( const\_iterator pos, T&& value );(2)

void insert( iterator pos, size\_type count, const T& value );(3)

iterator insert( const\_iterator pos, size\_type count, const T& value );(4)  
  
template< class InputIt >  
void insert( iterator pos, InputIt first, InputIt last);

template< class InputIt >  
iterator insert( const\_iterator pos, InputIt first, InputIt last );  
iterator insert( const\_iterator pos, std::initializer\_list<T> ilist );(5)  
  
  
插入元素到容器中的指定位置。  
1-2) 在 pos 前插入 value 。  
3) 在 pos 前插入 value 的 count 个副本。  
4) 在 pos 前插入来自范围 \[first, last) 的元素。  
       返回值：  
1-2) 指向被插入 value 的迭代器。  
3) 指向首个被插入元素的迭代器，或若 count==0 则为 pos 。  
4) 指向首个被插入元素的迭代器，或若 first==last 则为 pos 。  
5) 指向首个被插入元素的迭代器，或若 ilist 为空则为 pos 。  
  
  
  
emplace 原位构造元素 (公开成员函数)  
template< class... Args >   
iterator emplace( const\_iterator pos, Args&&... args );  
  
直接于 pos 前插入元素到容器中。通过 std::allocator\_traits::construct 构造元素，它典型地用布置 new 在容器所提供的位置原位构造元素。将参数 args... 作为 std::forward<Args>(args)... 转发给构造函数。  
若新的 size() 大于 capacity() ，则所有迭代器和引用都被非法化。否则，仅在插入点前的迭代器和引用保持合法。尾后迭代器亦被非法化。  
  
  
erase 擦除元素 (公开成员函数)

push\_back 将元素添加到容器末尾 (公开成员函数)

emplace\_back  在容器末尾就地构造元素 (公开成员函数)

pop\_back 移除末元素 (公开成员函数)

resize 改变容器中可存储元素的个数 (公开成员函数)

swap 交换内容 (公开成员函数)

#include<iostream>
    #include<vector>
    #include<ctime>
    using namespace std;
    
    
    template<typename T>
    void Print(T vec)
    {
    	T::const_iterator iter = vec.cbegin();
    	for (; iter != vec.cend();)
    	{
    		cout << *iter++ << " ";
    	}
    	cout << endl;
    }
    
    
    
    
    int main()
    {
    	srand(time(0));
    	vector<char> a;
    	vector<char> b;
    	for (int i = 0; i < 10; i++)
    	{
    		a.push_back((char)rand()%10);
    	}
    	for (int i = 0; i < 10; i++)
    	{
    		b.push_back((char)rand() % 10);
    	}
    
    
    	Print(a);
    	a.swap(b);//交换数量一样
    	Print(a);
    
    
    	//插入
    	a.insert(a.begin(), 'a');
    	Print(a);
    	a.insert(a.begin(),6, 'b');
    	Print(a);
    	a.insert(a.begin(), b.begin(),b.end());
    	Print(a);
    	char c[] = { '1', '2', '3' };
    	a.insert(a.begin(), c, c+2);
    	Print(a);
    
    
    
    
    	std::vector<int> myvector = { 10, 20, 30 };
    
    
    	auto it = myvector.emplace(myvector.begin() + 1, 100);//10后插入100
    	myvector.emplace(it, 200);//10后100前插入200
    	myvector.emplace(myvector.end(), 300);//30后插入300
    
    
    
    
    	myvector.emplace_back(600);
    	myvector.emplace_back(600);//直接在后面插入600
    	/*std::cout << "myvector contains:";
    	for (auto& x : myvector)
    		std::cout << ' ' << x;
    	std::cout << '\n';*/
    	//或
    	Print(myvector);
    
    
    	system("pause");
    	return 0;
    }

7、非成员函数  
  
  
operator==  
operator!=  
operator<  
operator<=  
operator>  
operator>=   
按照字典顺序比较 vector 中的值   
(函数模板)  
比较二个容器的内容。  
1-2) 检查 lhs 与 rhs 的内容是否相等，即是否 lhs.size() == rhs.size() 且每个 lhs 中的元素与 rhs 的同位置元素比较相等。  
3-6) 按字典序比较 lhs 与 rhs 的内容。按照等价于 std::lexicographical\_compare 的函数进行比较。  
返回值  
1) 若容器内容相等则为 true ，否则为 false  
2) 若容器内容不相等则为 true ，否则为 false  
3) 若 lhs 的内容按字典序小于 rhs 的内容则为 true ，否则为 false  
4) 若 lhs 的内容按字典序小于或等于 rhs 的内容则为 true ，否则为 false  
5) 若 lhs 的内容按字典序大于 rhs 的内容则为 true ，否则为 false  
6) 若 lhs 的内容按字典序大于或等于 rhs 的内容则为 true ，否则为 false  
  
  
  
  
(1) template <class T, class Alloc>  
  bool operator== (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);

(2)template <class T, class Alloc>  
  bool operator!= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);

(3)template <class T, class Alloc>  
  bool operator<  (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);

(4)template <class T, class Alloc>  
  bool operator<= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);

(5)template <class T, class Alloc>  
  bool operator>  (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);

(6)template <class T, class Alloc>  
  bool operator>= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);

// vector comparisons
    #include <iostream>
    #include <vector>
    
    
    int main ()
    {
      std::vector<int> foo (3,100);   // three ints with a value of 100
      std::vector<int> bar (2,200);   // two ints with a value of 200
    
    
      if (foo==bar) std::cout << "foo and bar are equal\n";
      if (foo!=bar) std::cout << "foo and bar are not equal\n";
      if (foo< bar) std::cout << "foo is less than bar\n";
      if (foo> bar) std::cout << "foo is greater than bar\n";
      if (foo<=bar) std::cout << "foo is less than or equal to bar\n";
      if (foo>=bar) std::cout << "foo is greater than or equal to bar\n";
    
    
      return 0;
    }

待续。。。。。。

[20171128190248794]: /images/20220604/77584d4abdf4438e876e08515afa8e89.png
[20171128190320487]: /images/20220604/f8b4c18cd3e041d38f56cdd40dbdb72b.png
[vector]: http://www.cplusplus.com/reference/vector/vector/
[vector_operator]: http://www.cplusplus.com/reference/vector/vector/operator=/
[vector_assign]: http://www.cplusplus.com/reference/vector/vector/assign/
[vector_reserve]: http://www.cplusplus.com/reference/vector/vector/reserve/
[vector_resize]: http://www.cplusplus.com/reference/vector/vector/resize/
[vector_clear]: http://www.cplusplus.com/reference/vector/vector/clear/