详解C++中 list 与 vector

落日映苍穹つ 2022-11-17 14:42 54阅读 0赞

## [【啊哈！算法】系列文章目录][Link 1] ##

--------------------

### 目录 ###

*   *  【啊哈！算法】系列文章目录
 *  前言
 *  C++ STL 库中的Vectors
 *   *  ▌01. Iterators
     *  ▌02. Capacity
     *  ▌03. Element access
     *  ▌04. Modifiers
     *   *  4.1 assign
         *  4.2 push\_back & pop\_back
         *  4.3 insert
         *  4.4 erase
     *  ▌05. Allocator
     *  ▌06. relational operators
 *  C++ STL 库中的链表Lists
 *   *  ▌01. Iterators
     *  ▌02. Capacity
     *  ▌03. Element access
     *  ▌04. Modifiers
     *  ▌05. Operations
     *   *  5.1 splice & merge
         *  5.2 remove
         *  5.3 remove\_if
         *  5.4 unique
         *  5.5 sort
     *  ▌06. Allocator
     *  ▌07. relational operators

--------------------

# 前言 #

首先介绍一下 vector 与 list 的区别：  
**vector**  
  vector与**数组**类似，拥有一段连续的内存空间，并且起始地址不变。便于随机访问，时间复杂度为 O ( 1 ) O(1) O(1)，但因为内存空间是连续的，所以在进入插入和删除操作时，会造成内存块的拷贝，时间复杂度为  O ( n ) O(n) O(n)。

此外，当数组内存空间不足，会采取扩容，通过重新申请一块更大的内存空间进行内存拷贝。

**list**  
  list底层是由**双向链表**实现的，因此内存空间不是连续的。根据链表的实现原理，List查询效率较低，时间复杂度为 O ( n ) O(n) O(n)，但插入和删除效率较高。只需要在插入的地方更改指针的指向即可，不用移动数据。

# C++ STL 库中的Vectors #

Vectors 包含着一系列连续存储的元素,其行为和数组类似。访问Vector中的任意元素或从末尾添加元素都可以在**常量级**时间复杂度内完成，而查找特定值的元素所处的位置或是在Vector中插入元素则是**线性**时间复杂度。

## ▌01. Iterators ##

<table> 
 <thead> 
  <tr> 
   <th>Function</th> 
   <th>Explanation</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>begin</code></td> 
   <td>返回第一个元素的迭代器</td> 
  </tr> 
  <tr> 
   <td><code>end</code></td> 
   <td>返回最末元素的迭代器(译注:实指向最末元素的下一个位置)</td> 
  </tr> 
  <tr> 
   <td><code>rbegin</code></td> 
   <td>返回Vector尾部的逆迭代器</td> 
  </tr> 
  <tr> 
   <td><code>rend</code></td> 
   <td>返回Vector起始的逆迭代器</td> 
  </tr> 
 </tbody> 
</table>

## ▌02. Capacity ##

<table> 
 <thead> 
  <tr> 
   <th>Function</th> 
   <th>Explanation</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>size</code></td> 
   <td>返回Vector元素数量的大小</td> 
  </tr> 
  <tr> 
   <td><code>max_size</code></td> 
   <td>返回Vector所能容纳元素的最大数量（上限）</td> 
  </tr> 
  <tr> 
   <td><code>resize</code></td> 
   <td>改变Vector元素数量的大小</td> 
  </tr> 
  <tr> 
   <td><code>capacity</code></td> 
   <td>返回vector所能容纳的元素数量(在不重新分配内存的情况下）</td> 
  </tr> 
  <tr> 
   <td><code>reserve</code></td> 
   <td>设置Vector最小的元素容纳数量</td> 
  </tr> 
  <tr> 
   <td><code>empty</code></td> 
   <td>判断Vector是否为空（返回true时为空）</td> 
  </tr> 
 </tbody> 
</table>

void resize( size_type size, TYPE val );	//resize() 函数改变当前vector的大小为size,且对新创建的元素赋值val

## ▌03. Element access ##

<table> 
 <thead> 
  <tr> 
   <th>Function</th> 
   <th>Explanation</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>operator[]</code></td> 
   <td>返回指定位置的元素</td> 
  </tr> 
  <tr> 
   <td><code>at</code></td> 
   <td>返回指定位置的元素</td> 
  </tr> 
  <tr> 
   <td><code>front</code></td> 
   <td>返回第一个元素</td> 
  </tr> 
  <tr> 
   <td><code>back</code></td> 
   <td>返回最末一个元素</td> 
  </tr> 
 </tbody> 
</table>

## ▌04. Modifiers ##

<table> 
 <thead> 
  <tr> 
   <th>Function</th> 
   <th>Explanation</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>assign</code></td> 
   <td>对Vector中的元素赋值</td> 
  </tr> 
  <tr> 
   <td><code>push_back</code></td> 
   <td>在Vector最后添加一个元素</td> 
  </tr> 
  <tr> 
   <td><code>pop_back</code></td> 
   <td>移除最后一个元素</td> 
  </tr> 
  <tr> 
   <td><code>insert</code></td> 
   <td>插入操作</td> 
  </tr> 
  <tr> 
   <td><code>erase</code></td> 
   <td>删除操作</td> 
  </tr> 
  <tr> 
   <td><code>swap</code></td> 
   <td>交换操作</td> 
  </tr> 
  <tr> 
   <td><code>clear</code></td> 
   <td>清空所有元素</td> 
  </tr> 
 </tbody> 
</table>

### 4.1 assign ###

void assign( input_iterator start, input_iterator end );
    void assign( size_type num, const TYPE &val );

assign() 函数要么将区间\[start, end)的元素赋到当前vector,或者赋num个值为val的元素到vector中.这个函数将会清除掉为vector赋值以前的内容.

### 4.2 push\_back & pop\_back ###

void push_back( const TYPE &val );
    void pop_back();

push\_back()添加值为val的元素到当前vector末尾  
pop\_back()函数删除当前vector最末的一个元素

### 4.3 insert ###

iterator insert( iterator loc, const TYPE &val );
    void insert( iterator loc, size_type num, const TYPE &val );
    void insert( iterator loc, input_iterator start, input_iterator end );

insert() 函数有以下三种用法:

*  在指定位置loc前插入值为val的元素,返回指向这个元素的迭代器,
 *  在指定位置loc前插入num个值为val的元素
 *  在指定位置loc前插入区间\[start, end)的所有元素 .

// inserting into a vector
    #include <iostream>
    #include <vector>
    using namespace std;
    
    int main ()
    { 
    	vector<int> myvector (3,100);
    	vector<int>::iterator it;
    
    	it = myvector.begin();
    	it = myvector.insert ( it , 200 );
    
    	myvector.insert (it,2,300);
    
    	// "it" no longer valid, get a new one:
    	it = myvector.begin();
    
    	vector<int> anothervector (2,400);
    	myvector.insert (it+2,anothervector.begin(),anothervector.end());
    
    	int myarray [] = {  501,502,503 };
    	myvector.insert (myvector.begin(), myarray, myarray+3);
    
    	cout << "myvector contains:";
    	for (it=myvector.begin(); it<myvector.end(); it++)
    		cout << ' ' << *it;
    	cout << '\n';
    
    	return 0;
    }
    //myvector contains: 501 502 503 300 300 400 400 200 100 100 100

### 4.4 erase ###

iterator erase( iterator loc );
    iterator erase( iterator start, iterator end );

erase函数要么删作指定位置loc的元素,要么删除区间\[start, end)的所有元素.返回值是指向删除的最后一个元素的下一位置的迭代器.

// erasing from vector
    #include <iostream>
    #include <vector>
    using namespace std;
    
    int main ()
    { 
    	vector<int> myvector;
    
      	// set some values (from 1 to 10)
      	for (int i=1; i<=10; i++) myvector.push_back(i);
    
      	// erase the 6th element
      	myvector.erase (myvector.begin()+5);
    
      	// erase the first 3 elements:
      	myvector.erase (myvector.begin(),myvector.begin()+3);
    
    	cout << "myvector contains:";
      	for (unsigned i=0; i<myvector.size(); ++i)
    		cout << ' ' << myvector[i];
    	cout << '\n';
    
      return 0;
    }
    //myvector contains: 4 5 7 8 9 10

## ▌05. Allocator ##

`get_allocator()` : 返回vector的内存分配器

// vector::get_allocator
    #include <iostream>
    #include <vector>
    using namespace std;
    
    int main ()
    { 
    	vector<int> myvector;
      	int * p;
      	unsigned int i;
    
      	// allocate an array with space for 5 elements using vector's allocator:
      	p = myvector.get_allocator().allocate(5);
    
      	// construct values in-place on the array:
      	for (i=0; i<5; i++) myvector.get_allocator().construct(&p[i],i);
    
    	cout << "The allocated array contains:";
      	for (i=0; i<5; i++) cout << ' ' << p[i];
    	cout << '\n';
    
      	// destroy and deallocate:
      	for (i=0; i<5; i++) myvector.get_allocator().destroy(&p[i]);
      	myvector.get_allocator().deallocate(p,5);
    
      	return 0;
    }
    //The allocated array contains: 0 1 2 3 4

## ▌06. relational operators ##

C++ Vectors能够使用标准运算符: ==, !=, <=, >=, <, 和 >. 要访问vector中的某特定位置的元素可以使用 \[\] 操作符.

两个vectors被认为是相等的,如果:

1.  它们具有相同的容量
2.  所有相同位置的元素相等.  
    vectors之间大小的比较是按照词典规则.

# C++ STL 库中的链表Lists #

Lists将元素按顺序储存在链表中. 与 向量(vectors)相比, 它允许快速的插入和删除，但是随机访问却比较慢.

## ▌01. Iterators ##

<table> 
 <thead> 
  <tr> 
   <th>Function</th> 
   <th>Explanation</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>begin</code></td> 
   <td>返回第一个元素的迭代器</td> 
  </tr> 
  <tr> 
   <td><code>end</code></td> 
   <td>返回最末元素的迭代器(译注:实指向最末元素的下一个位置)</td> 
  </tr> 
  <tr> 
   <td><code>rbegin</code></td> 
   <td>返回指向第一个元素的逆向迭代器</td> 
  </tr> 
  <tr> 
   <td><code>rend</code></td> 
   <td>指向list末尾的逆向迭代器</td> 
  </tr> 
 </tbody> 
</table>

## ▌02. Capacity ##

<table> 
 <thead> 
  <tr> 
   <th>Function</th> 
   <th>Explanation</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>size</code></td> 
   <td>返回list中的元素个数</td> 
  </tr> 
  <tr> 
   <td><code>max_size</code></td> 
   <td>返回list能容纳的最大元素数量</td> 
  </tr> 
  <tr> 
   <td><code>empty</code></td> 
   <td>如果list是空的则返回true</td> 
  </tr> 
 </tbody> 
</table>

## ▌03. Element access ##

<table> 
 <thead> 
  <tr> 
   <th>Function</th> 
   <th>Explanation</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>front</code></td> 
   <td>返回第一个元素</td> 
  </tr> 
  <tr> 
   <td><code>back</code></td> 
   <td>返回最末一个元素</td> 
  </tr> 
 </tbody> 
</table>

## ▌04. Modifiers ##

<table> 
 <thead> 
  <tr> 
   <th>Function</th> 
   <th>Explanation</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>assign</code></td> 
   <td>给list赋值</td> 
  </tr> 
  <tr> 
   <td><code>push_back</code></td> 
   <td>在list的末尾添加一个元素</td> 
  </tr> 
  <tr> 
   <td><code>pop_back</code></td> 
   <td>移除最后一个元素</td> 
  </tr> 
  <tr> 
   <td><code>push_front</code></td> 
   <td>在list的头部添加一个元素</td> 
  </tr> 
  <tr> 
   <td><code>pop_front</code></td> 
   <td>删除第一个元素</td> 
  </tr> 
  <tr> 
   <td><code>insert</code></td> 
   <td>插入操作</td> 
  </tr> 
  <tr> 
   <td><code>erase</code></td> 
   <td>删除操作</td> 
  </tr> 
  <tr> 
   <td><code>swap</code></td> 
   <td>交换操作</td> 
  </tr> 
  <tr> 
   <td><code>resize</code></td> 
   <td>改变list的大小</td> 
  </tr> 
  <tr> 
   <td><code>clear</code></td> 
   <td>清空所有元素</td> 
  </tr> 
 </tbody> 
</table>

## ▌05. Operations ##

<table> 
 <thead> 
  <tr> 
   <th>Function</th> 
   <th>Explanation</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>splice</code></td> 
   <td>合并两个list （可以无序）</td> 
  </tr> 
  <tr> 
   <td><code>merge</code></td> 
   <td>合并两个list （必须有序）</td> 
  </tr> 
  <tr> 
   <td><code>remove</code></td> 
   <td>从list删除元素</td> 
  </tr> 
  <tr> 
   <td><code>remove_if()</code></td> 
   <td>按指定条件删除元素</td> 
  </tr> 
  <tr> 
   <td><code>unique</code></td> 
   <td>删除list中重复的元素</td> 
  </tr> 
  <tr> 
   <td><code>sort</code></td> 
   <td>给list排序</td> 
  </tr> 
  <tr> 
   <td><code>reverse</code></td> 
   <td>把list的元素倒转</td> 
  </tr> 
 </tbody> 
</table>

### 5.1 splice & merge ###

void splice( iterator pos, list &lst );
    void splice( iterator pos, list &lst, iterator del );
    void splice( iterator pos, list &lst, iterator start, iterator end );

splice()函数把lst连接到pos的位置。如果指定其他参数，则插入lst中del所指元素到现链表的pos上，或者用start和end指定范围。

void merge(list &lst );
    void merge( list &lst, Comp compfunction );

merge()函数把自己和lst链表连接在一起，产生一个整齐排列的组合链表。如果指定compfunction，则将指定函数作为比较的依据。

// splicing lists
    #include <iostream>
    #include <list>
    using namespace std;
    
    int main ()
    { 
    	list<int> mylist1, mylist2;
      	list<int>::iterator it;
    
      	// set some initial values:
      	for (int i=1; i<=4; ++i)
         	mylist1.push_back(i);      // mylist1: 1 2 3 4
    
      	for (int i=1; i<=3; ++i)
         	mylist2.push_back(i*10);   // mylist2: 10 20 30
    
      	it = mylist1.begin();
      		++it;                 		// points to 2
    
      	mylist1.splice (it, mylist2); 	// mylist1: 1 10 20 30 2 3 4
                                    	// mylist2 (empty)
                                    	// "it" still points to 2 (the 5th element)
                                              
      	mylist2.splice (mylist2.begin(),mylist1, it);
                                    	// mylist1: 1 10 20 30 3 4
                                    	// mylist2: 2
                                    	// "it" is now invalid.
      	it = mylist1.begin();
    	advance(it,3);           		// "it" points now to 30
    
      	mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end());
                                    	// mylist1: 30 3 4 1 10 20
    
     	cout << "mylist1 contains:";
      	for (it=mylist1.begin(); it!=mylist1.end(); ++it)
    		cout << ' ' << *it;
    	cout << '\n';
    
    	cout << "mylist2 contains:";
     	 for (it=mylist2.begin(); it!=mylist2.end(); ++it)
    		cout << ' ' << *it;
    	cout << '\n';
    
      return 0;
    }
    //mylist1 contains: 30 3 4 1 10 20
    //mylist2 contains: 2

// list::merge
    #include <iostream>
    #include <list>
    using namespace std;
    
    // compare only integral part:
    bool mycomparison (double first, double second)
    {  return ( int(first)<int(second) ); }
    
    int main ()
    { 
    	list<double> first, second;
    
    	first.push_back (3.1);
    	first.push_back (2.2);
    	first.push_back (2.9);
    
    	second.push_back (3.7);
    	second.push_back (7.1);
    	second.push_back (1.4);
    
    	first.sort();
    	second.sort();
    
    	first.merge(second);
    
    	// (second is now empty)
    
    	second.push_back (2.1);
    
    	first.merge(second,mycomparison);
    
    	cout << "first contains:";
    	for (list<double>::iterator it=first.begin(); it!=first.end(); ++it)
    		cout << ' ' << *it;
    	cout << '\n';
    
    	return 0;
    }
    //first contains: 1.4 2.2 2.9 2.1 3.1 3.7 7.1

### 5.2 remove ###

void remove( const TYPE &val );

remove()函数删除链表中所有值为val的元素。

### 5.3 remove\_if ###

void remove_if( UnPred pr );

remove\_if()以一元谓词pr为判断元素的依据，遍历整个链表。如果pr返回true则删除该元素。

// list::remove_if
    #include <iostream>
    #include <list>
    using namespace std;
    
    // a predicate implemented as a function:
    bool single_digit (const int& value) {  return (value<10); }
    
    // a predicate implemented as a class:
    struct is_odd { 
    	bool operator() (const int& value) {  return (value%2)==1; }
    };
    
    int main ()
    { 
    	int myints[]= { 15,36,7,17,20,39,4,1};
    	list<int> mylist (myints,myints+8);   // 15 36 7 17 20 39 4 1
    	
    	mylist.remove_if (single_digit);           // 15 36 17 20 39
    	
    	mylist.remove_if (is_odd());               // 36 20
    	
    	cout << "mylist contains:";
    	for (list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
    		cout << ' ' << *it;
    	cout << '\n';
    	
    	return 0;
    }
    //mylist contains: 36 20

### 5.4 unique ###

void unique();
    void unique( BinPred pr );

unique()函数删除链表中所有重复的元素。如果指定pr，则使用pr来判定是否删除。

// list::unique
    #include <iostream>
    #include <cmath>
    #include <list>
    using namespace std;
    
    // a binary predicate implemented as a function: 具有相同的整数部分
    bool same_integral_part (double first, double second)
    {  return ( int(first)==int(second) ); }
    
    // a binary predicate implemented as a class:
    struct is_near { 
    	bool operator() (double first, double second)
    	{  return (fabs(first-second)<5.0); }
    };
    
    int main ()
    { 
    	double mydoubles[]={  12.15,  2.72, 73.0,  12.77,  3.14,
                           12.77, 73.35, 72.25, 15.3,  72.25 };
    	list<double> mylist (mydoubles,mydoubles+10);
      
    	mylist.sort();             // 2.72, 3.14, 12.15, 12.77, 12.77,
    	                           // 15.3, 72.25, 72.25, 73.0, 73.35
    
      	mylist.unique();           // 2.72, 3.14, 12.15, 12.77
                                   // 15.3, 72.25, 73.0, 73.35
    
      	mylist.unique (same_integral_part);  // 2.72, 3.14, 12.15
                                             // 15.3, 72.25, 73.0
    
     	 mylist.unique (is_near());           // 2.72, 12.15, 72.25
    
    	cout << "mylist contains:";
      	for (list<double>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
    		cout << ' ' << *it;
    	cout << '\n';
    
      	return 0;
    }
    //mylist contains: 2.72 12.15 72.25

### 5.5 sort ###

void sort();
    void sort( Comp compfunction );

sort()函数为链表排序，默认是升序。如果指定compfunction的话，就采用指定函数来判定两个元素的大小。

// list::sort
    #include <iostream>
    #include <list>
    #include <string>
    #include <cctype>
    using namespace std;
    
    // comparison, not case sensitive. 按字母顺序排序，不考虑大小写
    bool compare_nocase (const string& first, const string& second)
    { 
    	unsigned int i=0;
    	while ( (i<first.length()) && (i<second.length()) )
      	{ 
        	if (tolower(first[i])<tolower(second[i])) return true;
        	else if (tolower(first[i])>tolower(second[i])) return false;
        	++i;
      	}
      	return ( first.length() < second.length() );
    }
    
    int main ()
    { 
    	list<string> mylist;
    	list<string>::iterator it;
      	mylist.push_back ("one");
      	mylist.push_back ("two");
      	mylist.push_back ("Three");
    
      	mylist.sort();
    
     	cout << "mylist contains:";
      	for (it=mylist.begin(); it!=mylist.end(); ++it)
      		cout << ' ' << *it;
    	cout << '\n';
    
      	mylist.sort(compare_nocase);
    
     	cout << "mylist contains:";
      	for (it=mylist.begin(); it!=mylist.end(); ++it)
      		cout << ' ' << *it;
    	cout << '\n';
    
      	return 0;
    }
    //mylist contains: Three one two
    //mylist contains: one Three two

## ▌06. Allocator ##

`get_allocator`： 返回list的配置器

// list::get_allocator
    #include <iostream>
    #include <list>
    using namespace std;
    
    int main ()
    { 
    	list<int> mylist;
      	int * p;
    
      	// allocate an array of 5 elements using mylist's allocator:
      	p=mylist.get_allocator().allocate(5);
    
      	// assign some values to array
      	for (int i=0; i<5; ++i) p[i]=i;
    
      	cout << "The allocated array contains:";
      	for (int i=0; i<5; ++i)  cout << ' ' << p[i];
    		cout << '\n';
    
      	mylist.get_allocator().deallocate(p,5);
    
      	return 0;
    }
    The allocated array contains: 0 1 2 3 4

## ▌07. relational operators ##

[std::relational operators (list)][std_relational operators _list]

[Link 1]: https://blog.csdn.net/weixin_43964993/article/details/115446128
[std_relational operators _list]: https://www.cplusplus.com/reference/list/list/operators/