欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

详解C++中 list 与 vector

程序员文章站 2022-03-22 21:45:17
...

【啊哈!算法】系列文章目录



前言

  首先介绍一下 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

Function Explanation
begin 返回第一个元素的迭代器
end 返回最末元素的迭代器(译注:实指向最末元素的下一个位置)
rbegin 返回Vector尾部的逆迭代器
rend 返回Vector起始的逆迭代器

▌02. Capacity

Function Explanation
size 返回Vector元素数量的大小
max_size 返回Vector所能容纳元素的最大数量(上限)
resize 改变Vector元素数量的大小
capacity 返回vector所能容纳的元素数量(在不重新分配内存的情况下)
reserve 设置Vector最小的元素容纳数量
empty 判断Vector是否为空(返回true时为空)
void resize( size_type size, TYPE val );	//resize() 函数改变当前vector的大小为size,且对新创建的元素赋值val

▌03. Element access

Function Explanation
operator[] 返回指定位置的元素
at 返回指定位置的元素
front 返回第一个元素
back 返回最末一个元素

▌04. Modifiers

Function Explanation
assign 对Vector中的元素赋值
push_back 在Vector最后添加一个元素
pop_back 移除最后一个元素
insert 插入操作
erase 删除操作
swap 交换操作
clear 清空所有元素

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

Function Explanation
begin 返回第一个元素的迭代器
end 返回最末元素的迭代器(译注:实指向最末元素的下一个位置)
rbegin 返回指向第一个元素的逆向迭代器
rend 指向list末尾的逆向迭代器

▌02. Capacity

Function Explanation
size 返回list中的元素个数
max_size 返回list能容纳的最大元素数量
empty 如果list是空的则返回true

▌03. Element access

Function Explanation
front 返回第一个元素
back 返回最末一个元素

▌04. Modifiers

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

▌05. Operations

Function Explanation
splice 合并两个list (可以无序)
merge 合并两个list (必须有序)
remove 从list删除元素
remove_if() 按指定条件删除元素
unique 删除list中重复的元素
sort 给list排序
reverse 把list的元素倒转

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)