【STL】list介绍（附与vector的比较）

发布于：2025-04-09 ⋅ 阅读:(28) ⋅ 点赞:(0)

文章目录

1.关于list

​ list也是STL提供的一个容器，其底层是一个带头双向循环链表，因此，其优缺点如下：

优点：

  1. 插入和删除效率高：在链表的任意位置插入或删除元素的时间复杂度为 O (1)，这使得list在需要频繁插入和删除元素的场景下非常高效。
  2. 内存管理灵活：list的元素在内存中不是连续存储的，因此可以灵活地分配和释放内存，避免了内存碎片的问题。

缺点：

  1. 随机访问效率低：由于list是双向链表，不支持随机访问，要访问第 n 个元素，需要从头或尾开始遍历链表。
  2. 空间开销大：每个元素除了存储自身的数据外，还需要额外的指针来指向前一个和后一个元素，因此空间开销较大。

在这里插入图片描述

2.使用

​ 这里也只介绍常用的一些接口。

2.1 list的构造

1.声明及说明

构造函数声明 说明
list(size_type n,const value_type& val = value_type()) 构造包含n个val元素的list
list() 构造空的list
list(const list& x) 拷贝构造
list (InputIterator first, InputIterator last) [first,last)区间元素构造

2.示例

#include <iostream>
#include <list> //注意包含头文件<list>
using namespace std;

template <class T>
void print_list(list<T>& lt)
{
    for (auto& e : lt)
    {
        cout << e << " ";
    }
    cout << endl;
}

void list_test1()
{
    list<int> lt1;                         // 构造空的lt1
    list<int> lt2(5, 10);                 // 4个值为10的元素构造lt2
    list<int> lt3(lt2.begin(), lt2.end()); // 用lt2的[begin(), end()）区间构造lt3
    list<int> lt4(lt3);                    // 用lt3拷贝构造lt4
	
    list<int> lt5{ 1,2,3,4,5 };           //列表格式构造 C++11支持
   
    print_list(lt1);//  
    print_list(lt2);//10 10 10 10 10
    print_list(lt3);//10 10 10 10 10
    print_list(lt4);//10 10 10 10 10
    
    print_list(lt5);//1 2 3 4 5
}


int main()
{
    list_test1();
	return 0;
}

2.2 list 迭代器的使用

1.声明及说明

声明 说明
begin() + end() 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin() + rend() 返回反向第一个元素的reverse_iterator，返回反向最后一个元素下一个位置的reverse_iterator

在这里插入图片描述

2.示例

void list_test2()
{
    list<int> lt{ 1,2,3,4,5 };           //列表格式构造 C++11支持

    list<int>::iterator it = lt.begin();
    while (it != lt.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
	//输出：1 2 3 4 5
    
    list<int>::reverse_iterator rit = lt.rbegin();
    while (rit != lt.rend())
    {
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;
    //输出：5 4 3 2 1
}

int main()
{
    list_test2();
	return 0;
}

2.3 list 容量操作

2.3.1 size()

1.声明及功能

声明 功能
size_type size() const 返回list内有效元素个数

2.示例

void list_test3()
{
    list<int> lt{ 1,2,3,4,5 };
    cout << lt.size() << endl;  //5
}

int main()
{
    list_test3();
	return 0;
}

2.3.2 empty()

1.声明及功能

声明 功能
bool empty() const 检测list是否为空

2.示例

void list_test4()
{
    list<int> lt1;
    list<int> lt2{ 1,2,3,4,5 };
    if (lt1.empty())
    {
        cout << "lt1 is empty" << endl;
    }
    else
    {
        cout << "lt1 is not empty" << endl;
    }
	//输出：lt1 is empty
    if (lt2.empty())
    {
        cout << "lt2 is empty" << endl;
    }
    else
    {
        cout << "lt2 is not empty" << endl;
    }
    //输出：lt2 is not empty
}

int main()
{
    list_test4();
	return 0;
}

2.3.3 resize()

1.声明及功能

声明 功能
void resize (size_type n); 将list的size调整为n。如果n大于当前list的size()，则在列表末尾插入默认构造的元素。如果n小于当前list的size()，则删除超出n的元素。
void resize (size_type n, const value_type& val); 将list的size调整为n。如果n大于当前列表的size()，则在列表末尾插入足够数量的值为val的元素。如果n小于当前列表的大小，则删除超出n的元素。

2.示例

void list_test5()
{
    list<int> lt1(5, 1);
    list<int> lt2(5, 2);
    print_list(lt1);//1 1 1 1 1
    print_list(lt2);//2 2 2 2 2

    lt1.resize(10, 2);
    print_list(lt1);//1 1 1 1 1 2 2 2 2 2
    lt1.resize(2, 0);
    print_list(lt1);//1 1

    lt2.resize(1);
    print_list(lt2);//2
    lt2.resize(10);
    print_list(lt2);//2 0 0 0 0 0 0 0 0 0 
    
}

int main()
{
    list_test5();
	return 0;
}

2.4 list 元素访问

2.4.1 front()

1.声明及功能

声明 功能
reference front(); 返回list第一个节点的值的引用

2.示例

void list_test6()
{
    list<int> lt{ 1,2,3,4,5 };
    print_list(lt);//1 2 3 4 5

    ++lt.front();//2 2 3 4 5
    print_list(lt);

}
int main()
{
    list_test6();
	return 0;
}

2.4.2 back()

1.声明及功能

声明 功能
reference back(); 返回list的最后一个节点中值的引用

2.示例

void list_test7()
{
    list<int> lt{ 1,2,3,4,5 };
    print_list(lt);//1 2 3 4 5

    --lt.back();
    print_list(lt);//1 2 3 4 4

}
int main()
{
    list_test7();
    return 0;
}

2.5 list 修改操作

2.5.1 push_front()

1.声明及功能

声明 功能
void push_front (const value_type& val); 在list首元素前插入值为val的元素

2.示例

void list_test8()
{
    list<int> lt{ 1,2,3,4,5 };
    print_list(lt);//1 2 3 4 5

    lt.push_front(0);
    print_list(lt);//0 1 2 3 4 5

}
int main()
{
    list_test8();
    return 0;
}

2.5.2 pop_front()

1.声明及功能

声明 功能
void pop_front(); 删除list中第一个元素

2.示例

void list_test9()
{
    list<int> lt{ 1,2,3,4,5 };
    print_list(lt);//1 2 3 4 5 

    lt.pop_front();
    print_list(lt);//2 3 4 5

}
int main()
{
    list_test9();
    return 0;
}

2.5.3 push_back()

1.声明及功能

声明 功能
void push_back (const value_type& val); 在list尾部插入值为val的元素

2.示例

void list_test10()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);
    print_list(lt);//1 2 3 4 5
}
int main()
{
    list_test10();
    return 0;
}

2.5.4 pop_back()

1.声明及功能

声明 功能
void pop_back(); 删除list中最后一个元素

2.示例

void list_test11()
{
    list<int> lt{ 1,2,3,4,5 };
    print_list(lt);//1 2 3 4 5

    lt.pop_back();
    lt.pop_back();
    lt.pop_back();
    lt.pop_back();
    print_list(lt);//1

}
int main()
{
    list_test11();
    return 0;
}

2.5.5 insert()

1.声明及功能

声明 功能
iterator insert (iterator position, const value_type& val); 在position位置前插入值为val的元素
void insert (iterator position, size_type n, const value_type& val); 在position位置前插入n个值为val的元素
template < class InputIterator > void insert (iterator position, InputIterator first, InputIterator last); 在position位置前插入指定区域[first,last)对应值的元素

2.示例

void list_test12()
{
    list<int> lt{ 1,2,3,4,5 };
    list<int> lt1{ 1,1,1,1,1 };
    print_list(lt);//1 2 3 4 5

    list<int>::iterator it = ++lt.begin();
    lt.insert(it, 0);
    print_list(lt);//1 0 2 3 4 5

    lt.insert(lt.begin(), 3, 0);
    print_list(lt);//0 0 0 1 0 2 3 4 5

    lt.insert(lt.begin(), lt1.begin(), lt1.end());
    print_list(lt);//1 1 1 1 1 0 0 0 1 0 2 3 4 5
}
int main()
{
    list_test12();
    return 0;
}

2.5.6 erase()

1.声明及功能

声明 功能
iterator erase (iterator position); 删除position位置的值,并返回position下一个位置的iterator
iterator erase (iterator first, iterator last); 删除指定区间[first,last)的元素并返回last位置的iterator

在这里插入图片描述

2.示例

void list_test13()
{
    list<int> lt{ 1,2,3,4,5,6,7,8,9,10 };
    print_list(lt);//1 2 3 4 5 6 7 8 9 10

    list<int>::iterator it1 = lt.begin();
    while (it1 != lt.end())
    {
        if (*it1 == 5)
        {
            it1 = lt.erase(it1); //it指向值为6的位置
            cout << *it1 << endl;//6
            continue;
        }
        it1++;
    }
    print_list(lt);//1 2 3 4 5 7 8 9 10

    list<int>::iterator first = ++lt.begin();//指向2的位置
    list<int>::iterator last = --lt.end(); //指向10的位置
    
    list<int>::iterator it2 = lt.erase(first, last);//删除[first,last) it2指向last的位置即9的位置
    cout << *it2 << endl;//10
    print_list(lt);//1 10
}
int main()
{
    list_test13();
    return 0;
}

2.5.7 swap()

1.声明及功能

声明 功能
void swap (list& x); 交换两个list

2.示例

void list_test14()
{
    list<int> lt1{ 1,2,3,4,5 };
    list<int> lt2{ 5,4,3,2,1 };
    print_list(lt1);//1 2 3 4 5
    print_list(lt2);//5 4 3 2 1

    lt1.swap(lt2);
    print_list(lt1);//5 4 3 2 1
    print_list(lt2);//1 2 3 4 5
}
int main()
{
    list_test14();
    return 0;
}

2.5.8 clear()

1.声明及功能

声明 功能
void clear(); 清空list中的有效元素（不包括头节点）

2.示例

void list_test15()
{
    list<int> lt{ 1,2,3,4,5 };
    print_list(lt);//1 2 3 4 5

    lt.clear();
    print_list(lt);// 
}
int main()
{
    list_test15();
    return 0;
}

2.6其它

2.6.1 remove()

1.声明及功能

声明 功能
void remove (const value_type& val); 删除值为val的元素

2.示例

void list_test16()
{
    list<int> lt{ 10,20,30,40,50 };
    print_list(lt);//10 20 30 40 50

    lt.remove(30);//有30则删除
    print_list(lt);//10 20 40 50

    lt.remove(1);//无1则不删除
    print_list(lt);//10 20 40 50
    
}
int main()
{
    list_test16();
    return 0;
}

2.6.2 remove_if()

1.声明及功能

声明 功能
template < class Predicate> void remove_if (Predicate pred); 删除满足（）中条件的值，其中可以是函数指针或者函数对象

2.示例

bool if_even(int n)
{
    return n % 2 != 0;
}

void list_test17()
{
    list<int> lt{ 1,2,3,4,5 };
    print_list(lt);//1 2 3 4 5

    lt.remove_if(if_even);//删除奇数
    print_list(lt);//2 4
}
int main()
{
    list_test17();
    return 0;
}

2.6.3 unique()

1.声明及功能

声明 功能
void unique(); 删除list中连续重复的值，一段连续值只保留一个（注意区分，不是完全去重）

2.示例

void list_test18()
{
    list<int> lt{ 1,1,1,2,2,2,3,3,4,5,5 };
    print_list(lt);//1 1 1 2 2 2 3 3 4 5 5 

    lt.unique();//连续重复的数，仅保留一个
    print_list(lt);//1 2 3 4 5 

    list<int> lt1{ 1,1,1,2,2,2,1,1,2,2,3,3,4,5,5 };
    print_list(lt1);1 1 1 2 2 2 1 1 2 2 3 3 4 5 5 

    lt1.unique();
    print_list(lt1);//1 2 1 2 3 4 5
}

int main()
{
    list_test18();
    return 0;
}

2.6.4 sort()

1.声明及功能

声明 功能
void sort(); 默认按升序排序
template < class Compare> void sort (Compare comp); 按comp方法进行排序

2.示例

struct cmp
{
    bool operator()(int a,int b) {
        return a > b;
    }
};
void list_test19()
{
    list<int> lt{ 3,1,2,5,4,0,2 };
    print_list(lt);//3 1 2 5 4 0 2

    lt.sort();//默认升序排列
    print_list(lt);//0 1 2 2 3 4 5

    lt.sort(cmp());//自定义降序排列
    print_list(lt);//5 4 3 2 2 1 0
}
int main()
{
    list_test19();
    return 0;
}

2.6.5 merge()

1.声明及功能

声明 功能
void merge (list& x); 合并两个list为一个有序的list（仅适用于两个已排序的list(升序)）

2.示例

void list_test20()
{
    list<int> lt1{ 1,2,6,4,5 };
    list<int> lt2{ 0,4,21,3,4 };

    lt1.sort();
    lt2.sort();
    lt1.merge(lt2);//将lt2合并到lt1中，合并成一个升序list

    print_list(lt1);//0 1 2 3 4 4 4 5 6 21
    print_list(lt2);//
}
int main()
{
    list_test20();
    return 0;
}

2.6.6 reverse()

1.声明及功能

声明 功能
void reverse(); 翻转list

2.示例

void list_test21()
{
    list<int> lt{ 1,2,3,4,5 };
    print_list(lt);//1 2 3 4 5

    lt.reverse();
    print_list(lt);//5 4 3 2 1
}
int main()
{
    list_test21();
    return 0;
}

3. vector和list对比

对比 vector list
底层结构 动态顺序表 带头双向循环链表
访问 支持随机访问，可使用首地址+下标，[]形式 不能随机访问
插入删除 任意位置插入删除效率较低，需挪动元素 任意位置插入删除效率较高
空间利用率 底层为连续空间，空间利用率高，缓存利用率高 节点动态开辟，容易造成内存碎片，空间利用率低，缓存利用率低
迭代器 原生态指针 指针进行了封装
迭代器失效 容器相关操作都可能导致迭代器失效，如插入引起扩容、删除元素等时 插入元素不会导致迭代器失效，删除节点会导致且只影响当前迭代器
使用场景 想进行随机访问，不关心插入删除效率时 有大量插入删除场景，不在意随机访问效率时

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布