C++ STL中的forward_list emplace_after()和emplace_front()

前言

C++ STL是C++语言中一个非常重要的标准库，它提供了大量方便实用的容器和算法，可以大大提高代码开发效率和程序性能。其中，由于其链表的实现方式，forward_list成为了新的一员。与list相比，forward_list仅支持单向遍历，但其占用的空间更小，能更好地处理大量数据。本文将介绍forward_list中的emplace_after()和emplace_front()两个成员函数。

forward_list的基本操作

forward_list是一个单向链表，因此对它的基本操作就是增删查。

插入操作

forward_list提供的插入操作有push_front()、insert_after()和emplace_after()三个。其中push_front()是在表头插入元素，insert_after()是在指定元素之后插入元素，而emplace_after()可以在指定节点之后直接进行元素构造：

    forward_list<int> flist = {1, 3, 5};
    auto it = flist.begin();
    ++it;
    flist.emplace_after(it, 2);
    // flist: 1 2 3 5

删除操作

forward_list提供的删除操作有pop_front()和erase_after()两个。pop_front()删除表头元素，erase_after()可以删除指定节点之后的元素：

    forward_list<int> flist = {1, 2, 3, 4};
    flist.pop_front();
    // flist: 2 3 4
    auto it = flist.begin();
    ++it;
    flist.erase_after(it);
    // flist: 2 4

查找操作

forward_list提供的查找操作有begin()、end()、cbegin()、cend()、find()和search()等。其中begin()和end()用于返回头指针和尾指针，cbegin()和cend()用于返回头指针和尾指针的const版本，find()用于查找是否有当前元素，返回下标指针，search()用于查找是否有指定节点的子链表，返回bool类型：

    forward_list<int> flist = {1, 2, 3, 4};
    auto it = flist.begin();
    ++it;
    auto pos = flist.find(3);
    // pos: 2
    bool is_exist = flist.search_after(it, {3, 4});
    // is_exist: true

emplace_after()函数

emplace_after()函数是用于在指定节点之后直接进行元素构造的函数。它可以和insert_after()函数一样插入元素，但它实现方式不同，它直接在指定元素之后进行构造，比insert_after()多调用了一次构造函数，更加高效。原型如下：

    template <class... Args>
    iterator emplace_after(const_iterator pos, Args&&... args);

pos：插入位置前面的节点的迭代器

args…：需要插入节点的参数

返回值：指向所插入的节点的迭代器。

举个例子，构造一个如下的forward_list：

    struct Node {
        int age;
        double weight;
        char name[20];
    };
    forward_list<Node> flist;

我们可以在第二个节点后插入一个新的节点，代码如下：

    auto it = flist.begin();
    ++it;
    flist.emplace_after(it, 20, 60.5, "Bob");

这个新节点的age为20，weight为60.5，name为”Bob”。

emplace_front()函数

emplace_front()函数类似于emplace_after()函数，它用于在表头插入元素。与push_front()函数相比，emplace_front()直接构造一个新元素，更加高效，且可以传递多个参数。原型如下：

    template <class... Args>
    void emplace_front(Args&&... args);

args…：需要插入节点的参数

返回值：无

举个例子，构造一个如下的forward_list：

    struct Person {
        int age;
        double height;
        std::string name;
    };
    forward_list<Person> flist;

我们可以在表头插入一个新的Person节点，代码如下：

    flist.emplace_front(25, 175.2, "Jack");

这个新节点的age为25，height为175.2，name为”Jack”。

示例代码

下面是一个综合运用forward_list的示例代码，其功能为实现一个简单的图搜索：

#include <iostream>
#include <forward_list>

typedef struct Edge {
    int src;
    int dest;
} Edge;

typedef struct Graph {
    int V;
    std::forward_list<int> *adj;
} Graph;

Graph* createGraph(int V) {
    Graph* graph = new Graph;
    graph->V = V;
    graph->adj = new std::forward_list<int>[V];
    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    Edge e = {src, dest};
    graph->adj[src].emplace_front(dest);
    graph->adj[dest].emplace_front(src);
}

void printGraph(Graph* graph) {
    std::cout << "Graph Structure:" << std::endl;
    for(int i=0; i<graph->V; i++) {
        std::cout << i << ": ";
        for(int j : graph->adj[i]) {
            std::cout << j << " ";
        }
        std::cout << std::endl;
    }
}

void BFS(Graph* graph, int start) {
    bool* visited = new bool[graph->V];
    for(int i=0; i<graph->V; i++) {
        visited[i] = false;
    }

    std::forward_list<int> queue;
    visited[start] = true;
    queue.emplace_front(start);

    while(!queue.empty()) {
        int s = queue.front();
        std::cout << s << " ";
        queue.pop_front();

        for(int i : graph->adj[s]) {
            if(!visited[i]) {
                visited[i] = true;
                queue.emplace_front(i);
            }
        }
    }
}

int main() {
    Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 0);
    printGraph(graph);
    BFS(graph, 0);
    return 0;
}