c++堆的emplace

C++的堆是动态内存分配的一种方式，可以在运行时动态分配和释放内存。`emplace`是C++标准库中的一个函数模板，用于在堆中创建对象。

`emplace`函数通过传递构造函数的参数来创建对象，并将对象直接放入堆中。它避免了创建临时对象和拷贝构造函数的开销，提高了代码的性能。

使用`emplace`函数的方法如下：

#include <vector>

struct MyStruct {
    int a;
    float b;
    // 自定义构造函数
    MyStruct(int x, float y) : a(x), b(y) {}
};

int main() {
    std::vector<MyStruct> myVector;

    // 使用emplace函数创建对象并添加到容器中
    myVector.emplace(myVector.begin(), 10, 3.14);

    return 0;
}

在上面的示例中，我们创建了一个存储`MyStruct`对象的向量容器`myVector`。使用`emplace`函数，我们可以直接在容器的起始位置插入一个新的`MyStruct`对象，并传递构造函数的参数。

这样，在堆中创建对象会更加高效，因为不需要额外的内存拷贝操作。

相关问题

priority_queue的emplace

`std::priority_queue` 是C++标准库中的一个容器适配器，它提供了以优先级顺序访问元素的功能。`std::priority_queue` 是通过堆数据结构实现的，默认情况下，它采用 std::less 进行元素的比较，保证堆顶元素是最大的。

`emplace` 是 `std::priority_queue` 的一个成员函数，用于直接在容器中就地构造元素。和 `push` 函数不同，`emplace` 函数可以避免元素的多次复制或移动操作，提高了效率。

下面是使用 `emplace` 函数向 `std::priority_queue` 中添加元素的示例代码：

#include <queue>
#include <iostream>

int main() {
    std::priority_queue<int> pq;

    // 使用 emplace 函数添加元素
    pq.emplace(3);
    pq.emplace(1);
    pq.emplace(4);
    pq.emplace(1);
    pq.emplace(5);

    // 输出堆中的元素
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }

    return 0;
}

输出结果：

5 4 3 1 1

可以看到，通过 `emplace` 函数添加元素时，我们可以直接提供构造该元素所需的参数，而不需要手动创建一个临时对象再传递给 `push` 函数。这样可以更方便地在堆中添加元素，并且可以避免不必要的拷贝或移动操作。

dijkstra算法c++类模板实现

以下是Dijkstra算法的C++类模板实现，可以适用于任何具有权重边的图（有向或无向）：

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

template <typename T>
class Dijkstra {
private:
    std::vector<std::vector<std::pair<int, T>>> graph; // 存储图的邻接表
    std::vector<T> dist; // 存储每个顶点的最短距离
    std::vector<int> prev; // 存储每个顶点在最短路径中的前驱结点
    const T INF = std::numeric_limits<T>::max(); // 无穷大

public:
    Dijkstra(const std::vector<std::vector<std::pair<int, T>>>& g) : graph(g) {}

    void run(int start) {
        int n = graph.size();
        dist.assign(n, INF);
        prev.assign(n, -1);

        // 使用小根堆存储每个顶点的最短距离及其编号
        std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<>> pq;

        pq.emplace(0, start);
        dist[start] = 0;
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();

            // 如果当前节点已经被处理过，就直接跳过
            if (dist[u] < d) {
                continue;
            }

            // 遍历当前节点所有的邻居节点
            for (auto [v, w] : graph[u]) {
                T newDist = dist[u] + w;
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    prev[v] = u;
                    pq.emplace(newDist, v);
                }
            }
        }
    }

    // 获取从起点到终点的最短距离
    T getDistance(int end) const {
        return dist[end];
    }

    // 获取从起点到终点的最短路径
    std::vector<int> getPath(int end) const {
        std::vector<int> path;
        for (int u = end; u != -1; u = prev[u]) {
            path.push_back(u);
        }
        std::reverse(path.begin(), path.end());
        return path;
    }
};

使用示例：

int main() {
    // 构建有向图
    int n = 5;
    std::vector<std::vector<std::pair<int, int>>> graph(n);
    graph[0].emplace_back(1, 10);
    graph[0].emplace_back(3, 5);
    graph[1].emplace_back(2, 1);
    graph[1].emplace_back(3, 2);
    graph[2].emplace_back(4, 4);
    graph[3].emplace_back(1, 3);
    graph[3].emplace_back(2, 9);
    graph[3].emplace_back(4, 2);

    // 运行Dijkstra算法
    Dijkstra<int> dijkstra(graph);
    dijkstra.run(0);

    // 输出结果
    for (int i = 0; i < n; i++) {
        std::cout << "Distance from 0 to " << i << ": " << dijkstra.getDistance(i) << std::endl;
        auto path = dijkstra.getPath(i);
        std::cout << "Path from 0 to " << i << ": ";
        for (int u : path) {
            std::cout << u << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

输出结果：

Distance from 0 to 0: 0
Path from 0 to 0: 0 
Distance from 0 to 1: 8
Path from 0 to 1: 0 3 1 
Distance from 0 to 2: 9
Path from 0 to 2: 0 3 1 2 
Distance from 0 to 3: 5
Path from 0 to 3: 0 3 
Distance from 0 to 4: 7
Path from 0 to 4: 0 3 4