C++中list详解-创新互联
list的介绍
构造函数
总结
网站栏目:C++中list详解-创新互联
转载来于:http://ybzwz.com/article/jhhhi.html
- list是序列容器,允许在序列中的任何位置执行固定O(1)时间复杂度的插入和删除操作,并在两个方向进行迭代。
- list容器使用双链表实现;双链表将每个元素存储在不同的位置,每个节点通过next,prev指针链接成顺序表。
- list与其他标准序列容器(array,vector和deque)相比,list通常可以在容器内的任何位置插入、提取和移动元素。
- list与其他标准序列容器(array,vector和deque)相比,list和forward_list(单链表实现)的主要缺点是他们不能通过位置直接访问元素;例如,要访问列表中的第五个元素,必须从已知位置(开始或结束)迭代到该位置,需要哦线性时间开销。
- 存储密度低,list要使用一些额外的内容空间(next,prev)来保持与每个元素相关联(前后续的线性)的链接信息,从而导致存储小元素类型(如char,short,int等)的列表的存储密度低。
成员类型 | 定义 |
---|---|
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 |
函数 | 功能 |
---|---|
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#includeusing namespace std;
templatevoid Print(const list& my)
{typename list::const_iterator it = my.begin();
for (; it != my.end(); it++)
{cout<< *it<< "\t";
}
cout<< endl;
}
int main()
{listlist1 = {12,23,34 };
listlist2(3, 11);
listlist3(list2);
listlist4 = {"This","is","windows" };
listlist5;
listlist6;
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#includeusing namespace std;
int main()
{listlist1 = {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#includeusing namespace std;
int main()
{listlist1 = {12,23,34 };
list::const_iterator it1 = list1.begin();
for (; it1 != list1.end(); it1++)
{cout<< *it1<< "\t";
}
cout<< endl;
list::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#includeusing namespace std;
int main()
{listlist1 = {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#includeusing namespace std;
templatevoid Print(const list& my)
{typename list::const_iterator it = my.begin();
for (; it != my.end(); it++)
{cout<< *it<< "\t";
}
cout<< endl;
}
int main()
{listlist1 = {12,23,34 };
listlist2 = {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#includeusing namespace std;
templatevoid Print(const list& my)
{typename list::const_iterator it = my.begin();
for (; it != my.end(); it++)
{cout<< *it<< "\t";
}
cout<< endl;
}
int main()
{listlist1 = {2,1,9,5,3,7 };
listlist2 = {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); |
迭代器 | 随机迭代器,迭代器检查越界。支持++,–,+,+=,<,>,!=,== | 双向迭代器,迭代器检查越界。支持++,–,==,!= |
迭代器失效 | 插入和删除元素都会导致迭代器失效 | 插入元素 |
- vector底层实现是驻足;list是双向链表。
- vector支持随机访问,list不支持。
- vector是顺序内存,list不是。
- vector在中间节点进行插入删除会导致内存拷贝,list不会。
- vector一次性分配好内存,不够时才进行扩容;list每次插入新节点都会进行内存申请。
- vector随机访问性能好,插入删除性能差;list随机访问性能差,插入删除性能好。
- 如果需要高效的随机存取,而不在乎插入和删除的效率(很少使用插入和删除操作),选用vector
- 如果需要大量的插入和删除的操作,随机存取很少使用,选用list。
见下篇
END!在这里插入代码片
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网站栏目:C++中list详解-创新互联
转载来于:http://ybzwz.com/article/jhhhi.html