list详解
list的介绍 list函数说明 成员类型 构造函数 元素访问 迭代器 容量 修改器 操作
vector和list区别
仿写 END!
list的介绍
list是序列容器,允许在序列中的任何位置执行固定O(1)时间复杂度的插入和删除操作,并在两个方向进行迭代。 list容器使用双链表实现;双链表将每个元素存储在不同的位置,每个节点通过next,prev指针链接成顺序表。 list与其他标准序列容器(array,vector和deque)相比,list通常可以在容器内的任何位置插入、提取和移动元素。 list与其他标准序列容器(array,vector和deque)相比,list和forward_list(单链表实现)的主要缺点是他们不能通过位置直接访问元素;例如,要访问列表中的第五个元素,必须从已知位置(开始或结束)迭代到该位置,需要哦线性时间开销。 存储密度低,list要使用一些额外的内容空间(next,prev)来保持与每个元素相关联(前后续的线性)的链接信息,从而导致存储小元素类型(如char,short,int等)的列表的存储密度低。
list函数说明
成员类型
成员类型 定义 value_type T allocator_type Allocator size_type 无符号整数类型(通常是 std::size_t ) difference_type 有符号整数类型(通常是 std::ptrdiff_t ) reference value_type& const_reference const value_type& pointer value_type* const_pointer const value_type* iterator 指向 value_type 的双向迭代器 const_iterator 指向 const value_type 的双向迭代器 reverse_iterator std::reverse_iterator const_reverse_iterator std::reverse_iterator<const_iterator>
构造函数
函数 功能 list ();默认构造函数。构造拥有默认构造的分配器的空容器 list ( size_type count,const T& value);构造拥有 count 个有值 value 的元素的容器。 explicit list ( size_type count ); 构造拥有个 count 默认插入的 T 实例的容器。 list ( InputIt first, InputIt last, const Allocator& alloc = Allocator() );构造拥有范围 [first, last) 内容的容器。 list ( const list& other );复制构造函数。构造拥有 other 内容的容器。 list & operator=( const list& other );复制赋值运算符。以 other 的副本替换内容。 list & operator=( std::initializer_list ilist );以 initializer_list ilist 所标识者替换内容。 void assign ( size_type count, const T& value ); 以 count 份 value 的副本替换内容。 template< class InputIt > void assign ( InputIt first, InputIt last ); 以范围 [first, last) 中元素的副本替换内容。 void assign ( std::initializer_list ilist ); 以来自 initializer_list ilist 的元素替换内容
# include <iostream>
# include <list>
using namespace std;
template < class T >
void Print ( const list< T> & my)
{
typename list < T> :: const_iterator it = my. begin ( ) ;
for ( ; it != my. end ( ) ; it++ )
{
cout << * it << "\t" ;
}
cout << endl;
}
int main ( )
{
list< int > list1 = { 12 , 23 , 34 } ;
list< int > list2 ( 3 , 11 ) ;
list< int > list3 ( list2) ;
list< string> list4 = { "This" , "is" , "windows" } ;
list< string> list5;
list< string> list6;
list5 = list4;
list6. assign ( 3 , "This" ) ;
Print ( list1) ;
Print ( list2) ;
Print ( list3) ;
Print ( list4) ;
Print ( list5) ;
Print ( list6) ;
return 0 ;
}
元素访问
元素访问 功能 reference front (); 返回到容器首元素的引用。 const_reference front () const; 返回到容器首元素的引用。 reference back (); 返回到容器中最后一个元素的引用。 const_reference back () const; 返回到容器中最后一个元素的引用。
# include <iostream>
# include <list>
using namespace std;
int main ( )
{
list< int > list1 = { 12 , 23 , 34 } ;
cout << "list1.front():" << list1. front ( ) << endl;
cout << "list1.back():" << list1. back ( ) << endl;
return 0 ;
}
迭代器
迭代器 功能 iterator begin (); 返回指向 list 首元素的迭代器。 若 list 为空,则返回的迭代器将等于 end() 。 const_iterator begin () const; 返回指向 list 首元素的迭代器。 若 list 为空,则返回的迭代器将等于 end() 。 iterator end (); 返回指向 list 末元素后一元素的迭代器。 const_iterator end () const; 返回指向 list 末元素后一元素的迭代器。 reverse_iterator rbegin (); 返回指向逆向 list 首元素的逆向迭代器。 const_reverse_iterator rbegin () const; 返回指向逆向 list 首元素的逆向迭代器。 reverse_iterator rend (); 返回指向逆向 list 末元素后一元素的逆向迭代器。 const_reverse_iterator rend () const; 返回指向逆向 list 末元素后一元素的逆向迭代器。
# include <iostream>
# include <list>
using namespace std;
int main ( )
{
list< int > list1 = { 12 , 23 , 34 } ;
list< int > :: const_iterator it1 = list1. begin ( ) ;
for ( ; it1 != list1. end ( ) ; it1++ )
{
cout << * it1 << "\t" ;
}
cout << endl;
list< int > :: reverse_iterator it2 = list1. rbegin ( ) ;
for ( ; it2 != list1. rend ( ) ; it2++ )
{
cout << * it2 << "\t" ;
}
cout << endl;
return 0 ;
}
容量
容量 功能 bool empty () const; 检查容器是否无元素,即是否 begin() == end() 。 size_type size () const; 返回容器中的元素数,即 std::distance(begin(), end()) 。 size_type max_size () const; 返回根据系统或库实现限制的容器可保有的元素最大数量,即对于最大容器的 std::distance(begin(), end()) 。
# include <iostream>
# include <list>
using namespace std;
int main ( )
{
list< int > list1 = { 12 , 23 , 34 } ;
cout << "list1.empty():" << list1. empty ( ) << endl;
cout << "list1.size():" << list1. size ( ) << endl;
cout << "list1.max_size():" << list1. max_size ( ) << endl;
return 0 ;
}
修改器
修改器 功能 void clear (); 从容器擦除所有元素。此调用后 size() 返回零。 iterator insert ( iterator pos, const T& value ); 在 pos 前插入 value 。 void insert ( iterator pos, size_type count, const T& value ); 在 pos 前插入 value 的 count 个副本。 template< class InputIt > void insert ( iterator pos, InputIt first, InputIt last); 在 pos 前插入来自范围 [first, last) 的元素 iterator insert ( const_iterator pos, std::initializer_list ilist ); 在 pos 前插入来自 initializer_list ilist 的元素 iterator erase ( iterator pos ); 移除位于 pos 的元素。 iterator erase ( iterator first, iterator last ); 移除范围 [first; last) 中的元素。 void pop_back (); 移除容器的末元素。 void push_front ( const T& value ); 前附给定元素 value 到容器起始。 void push_back ( const T& value ); 后附给定元素 value 到容器尾。 void pop_front (); 移除容器首元素。 void resize ( size_type count ); 重设容器大小以容纳 count 个元素。 void resize ( size_type count, T value = T() ); count - 容器的大小,value - 用以初始化新元素的值 void swap ( list& other ); 将内容与 other 的交换。
# include <iostream>
# include <list>
using namespace std;
template < class T >
void Print ( const list< T> & my)
{
typename list < T> :: const_iterator it = my. begin ( ) ;
for ( ; it != my. end ( ) ; it++ )
{
cout << * it << "\t" ;
}
cout << endl;
}
int main ( )
{
list< int > list1 = { 12 , 23 , 34 } ;
list< int > list2 = { 1 , 2 , 3 , 4 , 5 } ;
Print ( list1) ;
Print ( list2) ;
auto it = list1. begin ( ) ;
list1. insert ( it, 55 ) ;
Print ( list1) ;
it++ ;
list1. insert ( it, 3 , 55 ) ;
Print ( list1) ;
list1. erase ( it) ;
Print ( list1) ;
list1. swap ( list2) ;
Print ( list1) ;
Print ( list2) ;
return 0 ;
}
操作
操作 功能 void merge ( list& other ); 归并二个已排序链表为一个。链表应以升序排序。 void splice ( const_iterator pos, list& other ); 从 other 转移所有元素到 *this 中。元素被插入到 pos 所指向的元素之前。操作后容器 other 变为空。 void splice ( const_iterator pos, list& other, const_iterator it ); 从 other 转移 it 所指向的元素到 *this 。元素被插入到 pos 所指向的元素之前。 void splice ( const_iterator pos, list& other, const_iterator first, const_iterator last); 从 other 转移范围 [first, last) 中的元素到 *this 。元素被插入到 pos 所指向的元素之前。 void remove ( const T& value ); 移除所有满足特定标准的元素。value - 要移除的元素的值 void reverse (); 逆转容器中的元素顺序。 void unique (); 从容器移除所有相继的重复元素。只留下相等元素组中的第一个元素。 void sort (); 以升序排序元素。保持相等元素的顺序。用 operator< 比较元素 template< class Compare > void sort ( Compare comp ); 以升序排序元素。保持相等元素的顺序。用给定的比较函数 comp 。
# include <iostream>
# include <list>
using namespace std;
template < class T >
void Print ( const list< T> & my)
{
typename list < T> :: const_iterator it = my. begin ( ) ;
for ( ; it != my. end ( ) ; it++ )
{
cout << * it << "\t" ;
}
cout << endl;
}
int main ( )
{
list< int > list1 = { 2 , 1 , 9 , 5 , 3 , 7 } ;
list< int > list2 = { 1 , 8 , 3 , 6 , 0 , 1 , 5 } ;
Print ( list1) ;
Print ( list2) ;
list1. sort ( ) ;
list2. sort ( ) ;
Print ( list1) ;
Print ( list2) ;
list2. unique ( ) ;
Print ( list2) ;
list1. merge ( list2) ;
Print ( list1) ;
Print ( list2) ;
return 0 ;
}
vector和list区别
区别 vector list 底层实现 连续存储的容器,动态数组,在堆上分配空间 动态双向链表,在堆上 空间利用率 连续空间,不易造成内存碎片,空间利用率高 节点不连续,易造成内存碎片,小元素使节点密度低,空间利用率低 查询元素 iterator operator[];find O(n);binary_search O(logn) iterator find O(n) 插入和删除 在最后插入(空间够):push_back(val);O(1)。在最后插入(空间不够):需要内存申请和释放,以及对之前数据进行拷贝。在之间插入(空间够):内存拷贝。在之间插入(空间不够):需要内存申请和释放,以及对之前数据进行拷贝。Insert(it,va) ,O(n)。在最后删除:pop_back(),O(1)。在之间删除:内存拷贝,不需要释放内存。erase(it),O(n)。resize(10):开辟空间,存储数据。reserve(10):只开辟空间,不存储数据。初始化vector空间,提高vector的使用效率。 插入:O(1),需要申请内存。push_back(),O(1);erase(it) ,O(n); 迭代器 连续的内存空间,支持随机迭代器,迭代器检查越界。支持++,–,+,+=,<,>,!=,== 内存空间可以是不连续,它不支持随机访问,双向迭代器,迭代器检查越界。支持++,–,==,!=;list::iterator则不支持“+”、“+=”、“<”等
|
|迭代器失效 |插入和删除元素都会导致迭代器失效 |插入元素 |
总结
vector底层实现是数组;list是双向链表。 vector支持随机访问,list不支持。 vector是顺序内存,list不是。 vector在中间节点进行插入删除会导致内存拷贝,list不会。 vector一次性分配好内存,不够时才进行扩容;list每次插入新节点都会进行内存申请。 vector随机访问性能好,插入删除性能差;list随机访问性能差,插入删除性能好。
vector和list的使用场景
vector拥有一段连续的内存空间,因此支持随机访问,如果需要高效的随机存取,而不在乎插入和删除的效率(很少使用插入和删除操作),选用vector list 拥有一段不连续的内存空间,如果需要大量的插入和删除的操作,随机存取很少使用,选用list。
仿写
见下篇
END!
CX-max: 不能直接定位it吧,得从begin或者end开始沿着链找
Ding Zhicong: list的erase(it)为什么不是O(1)?
星星落进眼睛: 请问有项目源码嘛
无妨无妨: 有bug 一直按2 work自己增长
无妨无妨: safecheck的两重循环为什么