【C++】list的使用（上）

🔥个人主页： Forcible Bug Maker
🔥专栏： STL || C++

前言

本篇博客主要内容：STL库中list的介绍以及list用法的讲解。

我们已经知道，string和vector的底层都是简单的顺序表，而list的底层就和之前的两个大不相同了，list的底层是一个带头双向循环链表。学习list之前，如果你还不知道什么是链表，完全由必要学习一下，可以看看我初阶数据结构所讲到的内容：初阶数据结构-顺序表和链表（C语言）

在C++中，我们可以直接使用list创建链表。

🌈关于list

list是可以在常数范围内任意位置进行插入和删除的序列式容器，并且可以前后双向迭代。

list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针向其前一个元素和后一个元素。

list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已经让其更简单更高效。

与其他序列式容器相比（array，vector，deque），list通常在任意位置进行插入，移除元素的执行效率更好。

于其他序列式容器相比，list和forward_list最大的缺陷是不支持元素的随机访问，比如：需要访问list的第六个元素，必须从已有的位置（比如头部或尾部）迭代到该位置，这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个结点的相关联信息（对于存储类型较小元素的大list来说这可能是一个重要的因素）。

🔥默认成员函数

构造函数（constructor）

注：对于最后一个参数（alloc），可以不用深究，在后期学了内存池相关的内容后会细讲。

构造一个list容器对象，可以根据以下四种方式初始化：
default (1)

explicit list (const allocator_type& alloc = allocator_type());

这是std::list的无参构造。它创建了一个不含任何元素的空list对象。其中explicit关键字阻止了隐式类型转换。

fill (2)

explicit list (size_type n, const value_type& val = value_type(),
               const allocator_type& alloc = allocator_type());

构造一个含有n个val值得list对象。

range (3)

template <class InputIterator>
  list (InputIterator first, InputIterator last,
         const allocator_type& alloc = allocator_type());

按迭代器区间[first, last) 的内容顺序构造list对象。

copy (4)

list (const list& x);

构造一个x对象得拷贝。
允许隐式类型转换。

代码案例：

// constructing lists
#include 
#include 

int main()
{
    // constructors used in the same order as described above:
    std::list<int> first;                                // 构建数据类型为整型的一个空链表
    std::list<int> second(4, 100);                       // 构建一个包含四个值为100的链表
    std::list<int> third(second.begin(), second.end());  // 通过second链表的迭代器构建third
    std::list<int> fourth(third);                       // 用third拷贝一个相同的链表fourth

    // the iterator constructor can also be used to construct from arrays:
    int myints[] = { 16,2,77,29 };
    std::list<int> fifth(myints, myints + sizeof(myints) / sizeof(int));

    std::cout << "The contents of fifth are: ";
    for (std::list<int>::iterator it = fifth.begin(); it != fifth.end(); it++)
        std::cout << *it << ' ';

    std::cout << '\n';

    return 0;
}

析构函数（destructor）

析构函数是当编译器出了对象的生命周期时自动调用的默认成员函数，释放开辟的内存空间。

赋值运算符重载

通过已有对象给被操作对象分配新的值，覆盖它原来的内容，并根据内容调整size的大小。

 list& operator= (const list& x);

从x中拷贝所有的内容到被操作list对象中。
在调用之前容器中持有的任何元素都将被分配给新值或被销毁。

代码案例：

// assignment operator with lists
#include 
#include 

int main()
{
	std::list<int> first(3);      // list of 3 zero-initialized ints
	std::list<int> second(5);     // list of 5 zero-initialized ints

	second = first;
	first = std::list<int>();

	std::cout << "Size of first: " << int(first.size()) << '\n';
	std::cout << "Size of second: " << int(second.size()) << '\n';
	return 0;
}

两个包含整型元素的列表容器都被初始化为不同大小的序列。然后，second容器被first容器赋值，所以现在两个容器相等并且大小都是3。接着，first容器被赋值给一个新构造的空容器对象（匿名对象），因此它的大小最终变为0。

🔥迭代器接口（Iterators）

对于STL的各种容器，迭代器的规则都是极其相似的。

和vector和string相同，begin获取指向list对象首元素的迭代器，end指向链表尾元素下一位的迭代器。

我认为迭代器在vector和string的基础上可以直接上代码了，大家能直接了解其用法。

代码案例：

#include
#include
using namespace std;

int main()
{
	list<int> lt({ 1,2,3,4 });
	
	// 获取正向迭代器遍历
	list<int>::iterator it = lt.begin();
	while (it != lt.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;

	// 获取反向迭代器遍历
	list<int>::reverse_iterator rit = lt.rbegin();
	while (rit != lt.rend()) {
		cout << *rit << " ";
		++rit;
	}
	cout << endl;

	return 0;
}

不过在使用list迭代器需要特别注意的一点：list链表的迭代器不支持加减运算，只支持++和- -运算符，如it += 1或it = it + 3的写法会使编译器报错。

🔥容量获取接口（Capacity）

empty和size

bool empty() const;

判断list对象是否为空。

size_type size() const;

获取list对象元素个数。

代码案例：

#include
#include
using namespace std;

int main()
{
	list<int> lt1;
	list<int> lt2({ 1,2,3,4 });

	cout << "lt1.empty():" << lt1.empty() << endl;
	cout << "lt2.empty():" << lt2.empty() << endl;
	cout << endl;

	cout << "lt1.size():" << lt1.size() << endl;
	cout << "lt2.size():" << lt2.size() << endl;

	return 0;
}

🔥元素获取（Element access）

  reference front();
const_reference front() const;

获取list对象首元素。

reference back();
const_reference back() const;

获取list对象尾元素。

代码案例：

#include
#include
using namespace std;

int main()
{
	list<int> lt({ 1,2,3,4 });

	cout << lt.front() << endl;
	cout << lt.back() << endl;

	return 0;
}

🔥修改器（Modifiers）

assign

range (1)

template <class InputIterator>
  void assign (InputIterator first, InputIterator last);

fill (2)

void assign (size_type n, const value_type& val);

两个重载都可以给list对象分配新内容，将对象原有的内容覆盖。

代码案例：

#include
#include
using namespace std;

int main()
{
	list<int> lt1({ 1,2,3,4 });
	list<int> lt2({ 0,0,0,0 });

	lt1.assign(lt2.begin(), lt2.end());
	for (auto e : lt1) {
		cout << e << " ";
	}
	cout << endl;

	lt1.assign(8, -1);
	for (auto e : lt1) {
		cout << e << " ";
	}
	return 0;
}

push_back，pop_back，push_front和pop_front

分别对应着链表的尾插尾删和头插头删。

代码案例：

#include
#include
using namespace std;

int main()
{
	list<int> lt({ 0,0,0 });

	for (auto e : lt) {cout << e << " ";}
	cout << endl;

	lt.push_back(-1);
	for (auto e : lt) { cout << e << " "; }
	cout << endl;

	lt.pop_back();
	for (auto e : lt) { cout << e << " "; }
	cout << endl;

	lt.push_front(-1);
	for (auto e : lt) { cout << e << " "; }
	cout << endl;

	lt.pop_front();
	for (auto e : lt) { cout << e << " "; }
	cout << endl;

	return 0;
}

insert

single element (1)

iterator insert (iterator position, const value_type& val);

在迭代器指向元素之前插入val。
fill (2)

void insert (iterator position, size_type n, const value_type& val);

在迭代器指向元素之前插入n个val。
range (3)

template <class InputIterator>
    void insert (iterator position, InputIterator first, InputIterator last);

在迭代器指向元素之前按顺序插入迭代器区间[first, last)内的值。

带吗案例：

#include 
#include 
#include 

int main()
{
    std::list<int> mylist;
    std::list<int>::iterator it;

    // set some initial values:
    for (int i = 1; i <= 5; ++i) mylist.push_back(i); // 1 2 3 4 5

    it = mylist.begin();
    ++it;       // it points now to number 2           ^

    mylist.insert(it, 10);                        // 1 10 2 3 4 5

    // "it" still points to number 2                      ^
    mylist.insert(it, 2, 20);                      // 1 10 20 20 2 3 4 5

    --it;       // it points now to the second 20            ^

    std::vector<int> myvector(2, 30);
    mylist.insert(it, myvector.begin(), myvector.end());
    // 1 10 20 30 30 20 2 3 4 5
    //               ^
    std::cout << "mylist contains:";
    for (it = mylist.begin(); it != mylist.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

erase

iterator erase (iterator position);
iterator erase (iterator first, iterator last);

删除list容器中一个迭代器（position）指向的元素或者一段迭代器区间(first, last]内的元素。
返回值为指向被删除元素下一元素的迭代器。

代码案例：

#include
#include
using namespace std;

int main()
{
	list<int> lt({ 1,2,3,4,5 });
	for (auto e : lt) { cout << e << " "; }
	cout << endl;

	list<int>::iterator it = lt.begin();
	++it;
	it = lt.erase(it);
	for (auto e : lt) { cout << e << " "; }
	cout << endl;

	it = lt.erase(it, lt.end());
	for (auto e : lt) { cout << e << " "; }
	cout << endl;

	return 0;
}

resize

void resize (size_type n, value_type val = value_type());

此接口函数用于调整容器的大小，使其包含n个元素。
如果n小于当前容器的大小，内容将被缩减为其前n个元素，移除超出n的部分（并销毁它们）。
如果n大于当前容器的大小，内容将通过在末尾插入所需数量的新元素来扩展，以达到大小为n。如果指定了val，新元素将被初始化为val的副本；否则，它们将进行默认值初始化。

// resizing list
#include 
#include 

int main()
{
    std::list<int> mylist;

    // set some initial content:
    for (int i = 1; i < 10; ++i) mylist.push_back(i);

    mylist.resize(5);
    mylist.resize(8, 100);
    mylist.resize(12);

    std::cout << "mylist contains:";
    for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
        std::cout << ' ' << *it;

    std::cout << '\n';

    return 0;
}

clear

void clear();

从列表容器（其中的元素将被销毁）中移除所有元素，使size的大小变为0。

结语

本篇博客给大家初步介绍了list，其底层是一个双向循环链表，讲解了list的一些函数接口，如修改器，元素访问，以及迭代器接口的使用方式。这些功能和规则和vector，string的接口大同小异，名称也大都一致，降低了我们的学习成本。
博主后续还会产出更多有关于STL的内容，感谢大家的支持。♥