详解C++中 list 与 vector
【啊哈!算法】系列文章目录
前言
首先介绍一下 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被认为是相等的,如果:
- 它们具有相同的容量
- 所有相同位置的元素相等.
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