C++ STL 容器技术 之 list双向链表容器_断了路梦在天上_百度空间

C++ STL 容器技术 之 list双向链表容器_断了路梦在天上_百度空间

C++ STL 容器技术 之 list双向链表容器
2010-09-03 18:39

简介:

list是双向链表的一个泛化容器,它的数据元素可通过链表指针串接成逻辑意义上的线性表。不同于采用线性表顺序存储结构的vector和deque容器,list双向链表中任一位置的元素查找、插入和删除,都具有高效的常数阶算法时间复杂度O(1)。

list应用基础:

创建list对象:

1、list(const A& a=A()) 创建一个空的list对象。

如:list<int> l;

2、list(size_type n) 创建一个具有n个元素的list对象,每个list元素具有它的类型下的默认值。

如:list<int> l(10);

3、list(size_type n, const T& value) 创建一个具有n个元素的list对象,每个元素具有初始值value。

如:list<int> l(10, 5);

4、list(const list&) 通过拷贝一个list对象的各个元素值,创建一个新的list对象。

如:list<int> l1(10, 5);        list<int> l2(l1);

5、list(const InputIterator first, const InputIterator last, const A& a=A()) 通过拷贝迭代器区间[first, last)的元素值,创建一个新的list对象中,内存分配器可省略。

如:int iArray[] = {1,2,3};      list<int> l(iArray, iArray+3);

初始化赋值:

list提供的push_back函数常用来进行list容器的初始化,push_back函数在容器的尾端插入新元素value。

void push_back(const T& value)

元素的遍历访问:

由于链表中的数据需要一个个元素进行遍历,因此list元素的遍历只使用迭代器的方式进行。

元素的插入:

由于list链表元素的插入不需要对其他元素进行移位拷贝,因此,list的元素插入函数具有常数阶的O(1)算法复杂度。除了push_back函数在尾部添加元素外,list还有在链首插入元素的push_front函数和在任意迭代器位置插入的insert函数。

iterator insert(iterator pos, const T& x)

void push_front(const T&)

元素的删除:

iterator erase(iterator pos) 删除迭代器pos所指的链表元素

iterator erase(iterator first, iterator last) 删除迭代器区间[first, last)的所有链表元素

void clear() 删除所有链表元素

void pop_front() 删除list的第一个链表元素

void pop_back() 删除list的最后一个链表元素

void remove(const T& value) 删除list链表中所有元素值为value的元素

元素的反向遍历:

reverse_iterator rbegin()

reverse_iterator rend()

list的交换:

list容器的swap函数,通过简单地交换两个list的头指针,来实现list元素的交换。

void swap(list&)

list的归并:

void splice(iterator position, list& x) 将x的链表归并到当前list链表的position位置之前,list对象x将被清空。

void splice(iterator position, list&, iterator i) 将一个list的迭代器i值所指的元素,归并到当前list链表中,并将归并的元素从原链表中删除。

void merge(list& x) 将list对象x的链表归并到当前list链表中,并清空x链表。只有当前链表和被归并的x链表的元素均预先按元素值的"<"关系排好序,merge函数才具有意义,归并后的链表元素也是按"<"关系排序的。

list的元素排序:

list提供的void sort函数,按"<"关系进行list链表的元素排序,较小的元素排在前面。

list的连续重复元素的删除:

利用list的void unique函数,可将连续重复的元素删除,仅保留一个。

举例分析:

1、

//插入list链表元素

#include <list>

#include <iostream>

using namespace std;

int main(void)

{

list<int> l;

l.push_back(6);

l.push_back(8);

l.push_back(9);

//插入链表元素

list<int>::iterator i, iend;

i = l.begin();

i++;

l.insert(i, 7);

l.push_front(5);

//打印链表元素

iend = l.end();

for (i=l.begin(); i!=iend; i++)

   cout << *i << " ";

return 0;

}

2、

//list链表元素的删除

#include <list>

#include <iostream>

using namespace std;

int main(void)

{

list<int> l;

l.push_back(5);

l.push_back(6);

l.push_back(7);

l.push_back(8);

l.push_back(9);

l.push_back(9);

l.push_back(9);

l.push_back(10);

//删除元素,剩下7、8和9

list<int>::iterator i, iend;

i = l.begin();

i++;

l.erase(i);

l.pop_back();

l.pop_front();

l.remove(9);

//打印

iend = l.end();

for (i=l.begin(); i!=iend; i++)

{

   cout << *i << " ";

}

return 0;

}

3、

//list链表的归并

#include <list>

#include <iostream>

using namespace std;

void print(list<int>& l)

{

list<int>::iterator i, iend;

iend = l.end();

for (i=l.begin(); i!=iend; i++)

{

   cout << *i << " ";

}

}

int main(void)

{

list<int> l;

for (int j=1; j<=10; j++)

{

   l.push_back(j);

}

//splice()函数

list<int> carry;

carry.splice(carry.begin(), l, l.begin());

//打印carry

cout << "carry的链表元素为: ";

print(carry);

cout << endl;

//打印l

cout << "l的链表元素为: ";

print(l);

cout << endl;

//merge()函数用法

list<int> x;

x.push_back(30);

x.push_back(31);

x.push_back(32);

l.merge(x);

//打印x

cout << "x的链表元素为: 空";

print(x);

cout << endl;

//打印l

cout << "l的链表元素为: ";

print(l);

cout << endl;

return 0;

}

4、

//list链表元素的排序

#include <list>

#include <iostream>

using namespace std;

void print(list<int>& l)

{

list<int>::iterator i, iend;

iend=l.end();

for (i=l.begin(); i!=iend; i++)

   cout << *i << " ";

cout << endl;

}

int main(void)

{

list<int> l;

for(int j=18; j>=0; j--)

   l.push_back(j);

cout << "排序前: ";

print(l);

//调用list<int>::sort()函数排序

l.sort();

cout << "排序后: ";

print(l);

return 0;

}

5、

//list连续重复元素的删除

#include <list>

#include <iostream>

using namespace std;

int main(void)

{

list<int> l;

l.push_back(6);

l.push_back(8);

l.push_back(6);

l.push_back(6);

l.push_back(6);

l.push_back(9);

l.push_back(13);

l.push_back(6);

l.unique();

list<int>::iterator i, iend;

iend = l.end();

for (i=l.begin(); i!=iend; i++)

   cout << *i << " ";

cout << endl;

return 0;

}

原文链接: https://www.cnblogs.com/lexus/archive/2012/07/30/2615788.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍

    C++ STL 容器技术 之 list双向链表容器_断了路梦在天上_百度空间

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/57346

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年2月9日 上午8:13
下一篇 2023年2月9日 上午8:13

相关推荐