首页 > 代码库 > 【C++ STL】List

【C++ STL】List

2024-10-04 12:34:02   216人阅读

1、结构

　　list使用一个double linked list（双向链表）来管理元素。

技术分享

2、 list 能力

　　list内部结构和vector或deque截然不同，所以与他们的区别：

　　list不支持随机存取，需要存取某个元素，需要遍历之前所有的元素，是很缓慢的行为。

　　任何位置上（不止是两端）安插和删除元素都非常快，始终都是在常数时间内完成，因为无需移动其他任何操作，实际上只进行了一些指针操作。

　　安插和删除并不会造成指向其他元素的各个pointers、reference、iterators失效

　　list是原子操作，要么成功，要么失败，不会说只执行一半。

　　list不支持随机存取，不提供下标操作符和at()函数。

　　list不提供容量，内存分配的操作函数，因为完全没必要，每个元素都有自己的内存空间，在删除之前一直有效。

　　list提供专门的函数用于移动函数，这些函数执行效率高，无需元素的拷贝和移动，只需要调整若干指针。

3、操作函数

3.1 构造和析构

操作

效果

list<Elem> c

产生一个空的list

list<Elem> c1(c2)

产生一个c2同型的list，每个元素都被复制

list<Elem> c(n)

产生一个n个元素的list，每个元素都由default构造产生

list<Elem> c(n,elem)

产生一个n个元素的list，每个元素都是elem的副本

list<Elem> c (beg,end)

产生一个list以区间[beg,end)内所有元素作为初值

c.~list<Elem>()

销毁所有元素，释放内存

3.2 非变动性操作

操作

效果

c.size()

返回当前的元素数量

c.empty()

判断大小是否为零，等同于0 == size()，效率更高

c.max_size()

返回能容纳的元素最大数量

c1 == c2

判断c1是否等于c2

c1 != c2

判断c1是否不等于c2(等同于!(c1==c2))

c1 < c2

判断c1是否小于c2

c1 > c2

判断c1是否大于c2

c1 <= c2

判断c1是否小于等于c2(等同于!(c2<c1))

c1 >= c2

判断c1是否大于等于c2 (等同于!(c1<c2))

3.3 赋值

操作

效果

c1 = c2

将c2的元素全部赋值给c1

c.assign(n,elem)

将elem的n个副本拷贝给c

c.assign(beg,end)

创建一个list，区间[beg,end)内的所有元素作为初值

c1.swap(c2)

c1和c2元素互换

swap(c1,c2)

c1和c2元素互换，全局函数

3.3 元素存取

　　list不支持随机存取，只有front()和back()能直接存取元素。

操作

效果

c.front()

返回第一个元素，不检查元素是否存在

c.back()

返回最后一个元素，不检查元素是否存在

3.4 迭代器相关函数

　　list只有使用迭代器才能对元素进行存取，list不支持随机存取，所以这些迭代器是双向迭代器，凡是用到随机存取迭代器的算法都不能使用。

操作

效果

c.begin()

返回一个随机存取迭代器，指向第一个元素

c.end()

返回一个随机存取迭代器，指向最后一个元素的下一个位置

c.rbegin()

返回一个逆向迭代器，指向逆向迭代的第一个元素

c.rend()

返回一个逆向迭代器，指向逆向迭代的最后一个元素的下一个位置

3.5 元素的安插和移除

　　list提供了deque的所有功能，还增加了remove()和remove_if()应用于list。

操作

效果

c.insert(pos, elem)

在迭代器pos位置插入一个elem副本，返回新元素位置

c.insert(pos,n, elem)

在迭代器pos位置插入n个elem副本，无返回值

c.insert(pos, beg,end)

在迭代器pos位置插入区间[beg,end)内所有元素的副本，无返回值

c.push_back(elem)

在尾部追加一个elem副本

c.pop_back()

移除最后一个元素，不返回

c.push_front(elem)

在头部安插一个elem副本

c.pop_front()

移除第一个元素，不返回

c.remove(val)

移除所有值为val的元素

c.remove_if(op)

移除所有“造成op(elem)为true”的元素

c.erase(pos)

移除迭代器pos所指元素，返回下一元素位置

c.erase(beg,end)

移除区间[beg,end)内的所有元素，返回下一元素位置

c.resize(num)

将元素容量重置为num个，如果size变大，则以default构造函数构造所有元素

c.resize (num, elem)

将元素容量重置为num个，如果size变大，则所有元素为elem的副本

c. clear ()

移除所有元素，将整个容器清空

3.6 特殊变动性操作

操作

效果

c.unique()

如果存在若干相邻而数值相等的元素，移除重复元素，只留下一个

c.unique(op)

若存在若干相邻元素，都使op()为true，移除重复元素，只留下一个

c1.splice(pos,c2)

将所有c2元素移到c1容器pos迭代器之前

c1.splice(pos,c2,c2pos)

将c2 pos位置元素移到c1元素pos位置，c1和c2可以相同

c1.splice(pos,c2,c2beg,c2end)

将c2区间[c2beg,c2end)所有元素移到c1 pos位置之前，c1和c2可以相同

c.sort()

以operator < 为准，对所有元素排序

c.sort(op)

以op()为准，对c排序

c1.merge(c2)

假设c1和c2已序，将c2元素移动到c1，并保证合并后的list仍为已序

c1.merge(c2,op)

假设c1和c2都以op()为序，将c2移动到c1仍然以op()已序

c.reverse()

将所有元素反序

4、示例代码

 // cont/list1.cpp

    #include <iostream>
    #include <list>
    #include <algorithm>
    using namespace std;

    void printLists (const list<int>& 11, const list<int>& 12)
    {

        cout << "list1: ";
        copy (l1.begin(), l1.end(), ostream_iterator<int>(cout," "));
        cout << endl << "list2: ";
        copy (12.begin(), 12.end(), ostream_iterator<int>(cout," "));
        cout << endl << endl;

    }

    int main()
    {

        //create two empty lists
        list<int> list1, list2;

        //fill both lists with elements
        for (int i=0; i<6; ++i) {
            list1.push_back(i);
            list2.push_front(i);
        }
        printLists(list1, list2);

        //insert all elements of list1 before the first element with value 3 of list2 
        //-find() returns an iterator to the first element with value 3
        list2.splice(find(list2.begin(),list2.end(), // destination position
                          3),
                     list1);                         // source list
        printLists(list1, list2);

        //move first element to the end
        list2.splice(list2.end(),          // destination position
                     list2,                // source list
                     list2.begin());       // source position
        printLists(list1, list2);

        //sort second list, assign to list1 and remove duplicates
        list2.sort();
        list1 = list2;
        list2.unique();
        printLists(list1, list2);

        //merge both sorted lists into the first list
        list1.merge(list2);
        printLists(list1, list2);
     }

输出：

   list1: 0 1 2 3 4 5
   list2: 5 4 3 2 1 0

   list1:
   list2: 5 4 0 1 2 3 4 5 3 2 1 0

   list1:
   list2: 4 0 1 2 3 4 5 3 2 1 0 5

   list1: 0 0 1 1 2 2 3 3 4 4 5 5
   list2: 0 1 2 3 4 5

   list1: 0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5
   list2:

 

【C++ STL】List


联系
我们