【C++ STL】-- list介绍与使用

目录

前言

list的介绍

list结构图

list的定义方式

list成员函数

迭代器的使用

begin、end、rbegin、rend

const修饰的迭代器

范围for

容量操作

empty、size

列表元素访问

front、back

列表修饰符

push_back、pop_back、push_front、pop_front

insert、erase 

swap、clear

resize

操作函数

splice

remove、remove_if

sort、unique

merge

reverse

---

前言

        相较于vector的连续线性空间，list就显得复杂的许多，它的好处就是每次插入与删除一个元素的时候，只需要配置或释放一个空间即可。因此，list对于空间的运用有绝对的精准，一点也不会浪费。而且对于任何位置的元素插入或元素删除，list永远是常数。

list的介绍

list的文档介绍

list结构图

        STL list 容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。list 容器中的元素可以分散存储在内存空间里，而不是存储在一整块连续的内存空间中。

list的定义方式

方式一：规定的存储类型的空容器

//int类型
list<int> lt1;
//double类型
list<double lt2;

方式二：利用其他容器的迭代器构造

vector<int> v{1, 2, 3, 4, 5};
list<int> lt(v.begin(), v.end());

方式三：构造为含有n个val

//5个1
list<int> lt2(5, 1);

方式四：以另一个list容器构造

list<int> lt1(5, 1);
list<int> lt2(lt1);

方式五：列表格式初始化C++11 

list<int> lt{ 1,2,3,4,5 };

方式六：以数组为迭代器区间构造

int array[] = { 16,2,77,29 };
list<int> lt(array, array + sizeof(array) / sizeof(int));

list成员函数

迭代器的使用

        将迭代器理解成一个指针，该指针指向list中的某个节点。

注意： . （遍历链表只能用迭代器和范围for）

• begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
• rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

begin、end、rbegin、rend

#include
#include
#include
using namespace std;
int main(){
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> lt(array, array + sizeof(array) / sizeof(array[0]));
    // 使用正向迭代器正向list中的元素
    // list::iterator it = l.begin();   // C++98中语法
    auto it = lt.begin();                  // C++11之后推荐写法
    while (it != lt.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
 
    // 使用反向迭代器逆向打印list中的元素
    // list::reverse_iterator rit = lt.rbegin(); // C++98中语法
    auto rit = lt.rbegin();            // C++11之后推荐写法
    while (rit != lt.rend())
    {
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;
}

const修饰的迭代器

#include
#include
#include
using namespace std;
int main(){
    // 注意这里调用的是list的 begin() const，返回list的const_iterator对象
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
    {
        cout << *it << " ";
        // *it = 10; 编译不通过
    }
 
    cout << endl;
}

范围for

#include
#include
#include
using namespace std;
int main() {
	vector<int> v{ 1,2,3,4,5 };
	list<int> lt(v.begin(), v.end());
	// C++11范围for的方式遍历
	for (auto& e : lt)
		cout << e << " ";
	cout << endl;
	//输出：1 2 3 4 5
	return 0;
}

容量操作

empty、size

#include
#include
#include
using namespace std;
int main() {
	int array[] = { 1, 2, 3 };
	list<int> lt(array, array + sizeof(array) / sizeof(array[0]));
	cout << lt.size() << endl;//输出：3
 
	while (!lt.empty()) {
		cout << lt.front() << " ";
		lt.pop_front();
	}
	cout << endl;//输出：1 2 3
 
	cout << lt.size() << endl;//输出：0
	return 0;
}

列表元素访问

front、back

#include
#include
#include
using namespace std;
int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
    //front与back返回的是引用，可以修改list内部数据
	lt.front() -= lt.back();
	cout << lt.front() << endl;//输出：-1
	lt.back() -= lt.front();
	cout << lt.back() << endl;//输出：3
 
	return 0;
}

列表修饰符

push_back、pop_back、push_front、pop_front

#include
#include
#include
using namespace std;
void Print_list(list<int>& lt) {
    for (auto val : lt)
        cout << val << " ";
    cout << endl;
}
 
int main()
{
    int array[] = { 1, 2, 3 };
    list<int> lt(array, array + sizeof(array) / sizeof(array[0]));
    Print_list(lt);//输出：1 2 3
 
    // 在list的尾部插入4，头部插入0
    lt.push_back(4);
    lt.push_front(0);
    Print_list(lt);//输出：0 1 2 3 4
 
    // 删除list尾部节点和头部节点
    lt.pop_back();
    lt.pop_front();
    Print_list(lt);//输出：1 2 3
 
    return 0;
}

insert、erase 

#include
#include
#include
using namespace std;
int main() {
    int array[] = { 1, 2, 3 };
    list<int> lt(array, array + sizeof(array) / sizeof(array[0]));
 
    // 获取链表中第二个节点
    auto pos = ++lt.begin();
    cout << *pos << endl;
 
    // 在pos前插入值为4的元素
    lt.insert(pos, 4);
 
    // 在pos前插入5个值为5的元素
    lt.insert(pos, 5, 5);
 
    // 在pos前插入[v.begin(), v.end)区间中的元素
    vector<int> v{ 7, 8, 9 };
    lt.insert(pos, v.begin(), v.end());
 
    // 删除pos位置上的元素
    lt.erase(pos);
 
    // 删除list中[begin, end)区间中的元素，即删除list中的所有元素
    lt.erase(lt.begin(), lt.end());
	return 0;
}

swap、clear

#include
#include
#include
using namespace std;
int main() {
    // 用数组来构造list
    int array[] = { 1, 2, 3 };
    list<int> lt1(array, array + sizeof(array) / sizeof(array[0]));
 
    // 交换l1和l2中的元素
    list<int> lt2;
    lt1.swap(lt2);
    cout << lt2.size() << endl;//输出：3
 
    // 将lt1中的元素清空
    lt2.clear();
    cout << lt2.size() << endl;//输出：0
    return 0;
}

resize

• 如果n小于当前容器大小，则内容将减少到其前n个元素，并删除（并销毁）超出的元素。
• 如果n大于当前容器大小，则通过在末尾插入尽可能多的元素来扩展内容，以达到n的大小。如果指定了val，则将新元素初始化为val，否则将对其进行值初始化（为0）。

#include
#include
#include
using namespace std;
int main()
{
    list<int> lt;
	for (int i = 1; i < 10; ++i)
		lt.push_back(i);
    //1 2 3 4 5 6 7 8 9
 
    lt.resize(5);       //1 2 3 4 5
    lt.resize(8, 100);  //1 2 3 4 5 100 100 100
    lt.resize(12);      //1 2 3 4 5 100 100 100 0 0 0 0
    return 0;
}

操作函数

splice

#include 
#include 
using namespace std;
int main()
{
	int array[] = { 1, 2, 3, 4 ,5 ,6 ,7 ,8 ,9 ,10 };
	list<int> lt1(array, array + 5);
	list<int> lt2(array + 5, array + 10);
	lt1.splice(lt1.begin(), lt2); //将容器lt2拼接到容器lt1的开头
	//lt1：6 7 8 9 10 1 2 3 4 5
 
	list<int> lt3(array, array + 5);
	list<int> lt4(array + 5, array + 10);
	lt3.splice(lt3.begin(), lt4, lt4.begin()); //将容器lt4的第一个数据拼接到容器lt3的开头
	//lt3：6 1 2 3 4 5
 
	list<int> lt5(array, array + 5);
	list<int> lt6(array + 5, array + 10);
	lt5.splice(lt5.begin(), lt6, lt6.begin(), lt6.end()); //将容器lt6的指定迭代器区间内的数据拼接到容器lt5的开头
	//lt5：6 7 8 9 10 1 2 3 4 5
 
	return 0;
}

remove、remove_if

#include
#include
#include
using namespace std;
bool single_digit(const int& val)
{
	return val < 5;
}
int main() {
	int array[] = { 1, 2, 3, 4, 5, 6 };
    list<int> lt(array, array + sizeof(array) / sizeof(array[0]));
	lt.remove(3); //删除容器当中值为3的元素
	//1 2 4 5 6
 
	lt.remove_if(single_digit); //删除容器当中值小于10的元素
	//5 6
	return 0;
}

sort、unique

#include 
#include 
using namespace std;
int main(){
	int array[] = { 3, 2, 1, 6, 5, 4, 4, 5, 6 };
	list<int> lt(array, array + sizeof(array) / sizeof(array[0]));
 
	lt.sort(); //将容器当中的元素排为升序
	//1 2 3 4 4 5 5 6 6
 
	lt.unique(); //删除容器当中连续的重复元素
	//1 2 3 4 5 6
	return 0;
}

merge

        用于将一个有序list容器合并到另一个有序list容器当中，若要实现无序排序合并建议使用splice。

#include 
#include 
using namespace std;
bool mycomparison(int first, int second) { return first > second; }
 
int main()
{
	int array1[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
	list<int> lt1(array1, array1 + 5);
	list<int> lt2(array1+5, array1 + 10);
	//用于将一个有序list容器合并到另一个有序list容器当中
	//要求列表容器的元素在调用之前已经按comp(mycomparison)排序。否则报错
	//若要实现无序排序合并建议使用splice
	lt1.merge(lt2,mycomparison); //将lt2合并到lt1当中
	//lt1：1 2 3 5 6 8 9 10
 
	int array2[] = { 100, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	list<int> lt3(array2, array2 + 5);
	list<int> lt4(array2 + 5, array2 + 10);
	//comp默认：如果第一个参数被认为小于第二个参数，则返回true，否则返回false。
	lt3.merge(lt4); //error
 
	return 0;
}

reverse

#include 
#include 
using namespace std;
int main()
{
	int array1[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
	list<int> lt(array1, array1 + 10);
	//10 9 8 7 6 5 4 3 2 1
	lt.reverse(); //将容器当中元素的位置进行逆置
	//1 2 3 4 5 6 7 8 9 10 
	return 0;
}