1. 从“插入”说起

前面，我们学习 vector 说到：使用 vector 时，最少用到的，就是往 vector 非尾部插入或删除元素。

list 正好相反，我们使用它的期待操作，就是：插入和删除。典型如：在新增或删除操作后，需要保持元素逻辑顺序的场景：

• 操作上，一群学生希望从高排低，站成一行；
• 整理扑克牌，目标是按花色和大小排序；
• 智能手机上，用户的多个闹钟安排（需按闹钟时间排列，而不是添加时间排列）；
• 高三年段模拟考成绩排列过程；
• ……

2. 课堂视频

3. 常用方法

3.1 迭代器相关

// 正向迭代器
iterator begin();
iterator end();
const_iterator end() const;

// 正向，常量迭代器
const_iterator cbegin();
const_iterator cend();

// 逆向迭代器
reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rend() const;

// 逆向，常量迭代器
const_reverse_iterator crbegin();
const_reverse_iterator crend();

结束位置上的迭代器，本质都不允许读写数据（因其并未指向实质数据），只用于比较，因此为方便比较，end() 和 rend() 都提供了语法上可写与不可写（const）两个重载版本。

3.2 添加数据

// 定义时准备数据
std::list<T> lst { v1, v2, v3 };

// 前后添加数据
void push_front( T const& v); // 复制版
void push_fornt( T && v);  // 移入版

void push_back( T const& v); // 复制版
void push_back( T && v ) ;  // 移入版

// 指定位置插入一个数据
iterator insert(const_iterator pos, T const& v); // 复制版
iterator insert(const_iterator pos, T&& v); // 移入版

无论是 push_xxx() 还是 insert ()，视频以及日常使用较多的，是 “复制版”，它复制一份源数据之后，再将“复制品”放入容器（ list），比如：

struct A
{
    std::string name;
    int age;
};

A a {"Alice", 13};

std::list<A> lst;

lst.push_back(a); // 函数内将复制一份 a，然后将复制器存入 lst 

std::cout << a.name << "\n"; // "Alice"，a不受 push_back() 任何影响

lst.push_back(std::move(a)); // a 被移入 lst ……

std::cout << a.name << "\n"; // "", a.name 的内容被移走了……

注意，如果 A 的成员数据只有 int、bool、double 等基础类型，而没有例中的 "std::string name"成员，则对它执行 lst.push_back(std::move(a)) 操作，仅有语义上的区别，因此基础数据只能复制，无法移动（通常也没有移动的价值，即移动与复制的性能一致）。

有一个有趣的问题，为什么都是容器， vector 却只有 push_back() 而无 push_front() 呢？

是 vector 无法实现 push_front() 吗？当然不是，所有 push_xxx() 都只是 insert( pos, v) 操作的特化而已， push_front() 就是 insert(this->cbegin(), v); vector 为要刻意不提供 push_front() 呢？

答：vector 的 push_back() 操作，可能慢速，也可能性能还不错（预留空间充足的情景），但 vector 入最前面添加入数据 （即 push_front() 方法要做的事）却一定是低效的。同一容器类型，同样叫 push_xxxx() 的方法，一个可能高效，一个固定低效，违反直觉，因此 vector 只提供了 性能可好可差的push_back() 而不提供性能一定低效的 push_front()。

vector 也只提供了性能良好的 pop_back()，而不提供性能一定低下的 pop_front()。

如果某 vector 对象就要在最前面添加或删除数据怎么办？ insert(cbegin(), v) 和 erase(cbegin())。

3.3 删除数据

// 删除首个元素
void pop_front();
// 删除末个元素
void pop_back();

// 删除指定位置的元素
iterator erase(const_iterator pos);

// 清空所有元素
void clear();

3.4 便捷访问

// 取首个元素
T& front(); 
T const& front() const;

// 取末个元素
T& back();
T const& back() const;

// 是否为空链表
bool empty() const; 
// 取元素个数
size_t size() const;

其中 front() 和 back() 返回的都是引用(或常量引用)，调用者可依据需要，复制或直接引用得到的元素：

/* front() 返回引用示例 */

std::list<Student> lst  
{  
    {1, "Alice"}, {2, "Bob"}, 
    {3, "Charlie"}, {4, "David"}
};

Student v1 = lst.front(); // v1 是复制品，对它修改不影响 lst 首元素的值
Student& v2 = lst.front(); // v2 是引用，对它修改就是对 lst 首元素的修改

// 或：
lst.front().name = "Anna"; // "Alice" →  "Anna"
lst.back().age++; // 4 → 5

不管有没有元素，list 以实现上，通常会拥有一个“header”节点，如果该节点的 next 指向 nullptr，即说明该链表为空。因此 empty() 方法性能极高。

98 及更早标准下，不少 STL 将 std::list 的 size() 实现为必须从头到尾“数”一遍才能得到元素个数，复杂度为 O（N）, C++11 及更高标准下，std::list 通常会维护一个 size_t 类型的成员以同步记录元素个数，复杂度为 O（1).

4. 项目实践 —— 成绩录入程序

4.1 需求

设有如下小测结果类型：

// 测试结果
struct TestResult 
{
    int index;    //交卷次序
    int no; 	     //学号    
    float score;  //成绩
};

请借助std::list<TestResult> 实现成绩录入。

具体要求：

1. 录入时模拟学生交卷次序，因此学号是混乱的，但加入链表后，需维护学号从小到大排列;
2. index 记录的就是交卷次序，与录入次序一致；
3. 如输入的 no 和 score 均为 0，表示结束输入；
4. 结束输入后，首先对所有数据进行合法检查，合法指：学号大于 0，成绩在0和100 之间，非法数据直接从链表中剔除，最终显示剔除个数；
5. 最后显示余留的合法数据。

4.2 代码

#include <iostream>
#include <iomanip>
#include <list>

struct TestResult
{
    int index;  //交卷次序
    int no;     // 学号
    float score;// 成绩
};

// 录入单个成绩
TestResult InputResult(int index)
{
    TestResult result;
    
    result.index = index;

    std::cout << "请输入第 " << index << " 份成绩\n";
    std::cout << "学号 成绩 ：(都为0，表示退出): ";
    std::cin >> result.no >> result.score;
    std::cout << "----------------------\n";

    return result;
}

// 录入成绩链表
std::list<TestResult> InputResults()
{
    std::list<TestResult> resultList;

    while(true) // 持续录入
    {
        int index = resultList.size() + 1;

        auto result = InputResult(index);

        if (result.no <= 0 && result.score == 0.0)
        {
            break;
        }

        // 找插入位置
        bool repeated = false;    // 是否号码重复
        bool inserted = false;  // 是否在循环中完成插入

        for (auto pos = resultList.begin(); pos != resultList.end(); ++pos)
        {
            if (result.no == pos->no)
            {
                std::cout << "学号重复，成绩更新：" << pos->score << " → " << result.score << "\n";
                
                pos->score = result.score;

                repeated = true;
                break;
            }
            
            if (result.no < pos->no)
            {
                resultList.insert(pos, result);

                inserted = true;
                break;
            }
        }

        if (!repeated && !inserted)
        {
            resultList.push_back(result);
        }
    }

    return resultList;
}

void OutputResult(TestResult const& result)
{
    std::cout << "学号：" << result.no;
    std::cout << "\t成绩：" << result.score;
    std::cout << "\t交卷次序：" << result.index;

    std::cout << "\n----------------------\n";
}

// 检查并剔除非法数据
void RemoveInvalidElem(std::list<TestResult>& resultList)
{
    int count = 0;

    for (auto it = resultList.cbegin(); it != resultList.cend(); )
    {
        if (it->no <= 0 || it->score < 0.0 || it->score > 100.0)
        {
            std::cout << "发现非法数据，删除：\n";
            OutputResult(*it);

            it = resultList.erase(it);
            ++count;
        }
        else
        {
            ++it;
        }
    }

    std::cout << "共发现并剔除 " << count << " 份非法成绩数据\n";
}

int main()
{
    std::cout << "~~学生成绩录入~~" << std::endl;

    auto resultList = InputResults();
    auto pos = resultList.begin(); 
    

    std::cout << "~~学生成绩合法检查~~" << std::endl;
    RemoveInvalidElem(resultList);

    if (resultList.empty()) // 一个都没录入？
    {
        std::cout << "未录入任何合法成绩，程序结束！" << std::endl;
        return -1;
    }

    std::cout << "\n按回车键查看成绩详情……";
    std::cin.ignore().get();

    for (auto const& result : resultList)
    {
        OutputResult(result);
    }
}