> 到矢量>,c++,vector,graph"/>
时间戳

首页 > 解决方案 > 如何转换矢量> 到矢量>

c++ - 如何转换矢量> 到矢量>

问题描述

我有一个方法需要我返回一个向量<pair<string, string>>。但是，我的输入是 vector <pair<string, T>>。这是返回图中边数的更大问题的一部分。相关代码在下面，其中T是整数类型。

map<string, string> all_vertices;
map<string, map<string, T>> adj_list;

template<typename T>
size_t Graph<T>::num_edges() {
    int edge_num = 0;

    for(auto& node : adj_list) {
        for(auto& edge : node.second) {
            edge_num++;
        }
    }

    return edge_num / 2;
}

template<typename T>
void Graph<T>::add_edge(const string& u, const string& v, const T& weight) {
    if(!adjacent(u, v)) {
        if(adj_list[u].find(v) == adj_list[u].end()) {
            adj_list[u].insert({v, weight});
            adj_list[v].insert({u, weight});
        }
    }
}

template <typename T>
void Graph<T>::add_vertex(const string& u) {
    
        if(!contains(u)){
            all_vertices.insert({u,u}); 
            adj_list[u]= map<string, T>();
     }
    
}

template <typename T>
bool Graph<T>::adjacent(const string& u, const string& v) {

     if(contains(u) && contains(v)){
        if (adj_list[u].find(v)!=adj_list[u].end()){
            return true;
        }
    }
    return false;
    
}

template<typename T>
vector<pair<string, string>> Graph<T>::get_edges() {
    vector<pair<string, T>> e;
    vector<pair<string, string>> e_string;
    for(auto x1 : adj_list) {
        for(auto x2 : x1.second) {
            e.push_back(x2);
        }
    }

    return e;
}
/* the test cases for the nodes in the graphs:

Number of vertices: 5

Number of edges: 8

Is vertex A in the graph? 1

Is vertex F in the graph? 0

Is there an edge between A and B? 1

Is there an edge between B and C? 0

*/

不同功能的说明：

标签： c++vectorgraph

解决方案

我建议你跳过创建的中间步骤，e直接进入e_string. 另外， makeget_edges() const因为你没有改变*this.

用于std::to_string将整数转换T为std::string.

然而，真正的问题是您的代码尝试仅添加一个顶点+ 每条边的权重。

在您对问题的描述中，它说它应该是一对顶点。它并没有说应该包括重量。

所以，这是如何做到的：

template <typename T>
std::vector<std::pair<std::string, std::string>> Graph<T>::get_edges() const {
    std::vector<std::pair<std::string, std::string>> e_string;
 
    for (auto&[u, Map] : adj_list) {
         // only add one direction, get all v's where u < v:
        for(auto vw_it = Map.upper_bound(u); vw_it != Map.end(); ++vw_it) {
            e_string.emplace_back(u, vw_it->first);
        }
    }
    
    return e_string;
}

演示

不相关的建议：

您可以简化num_edges()方法（也应该是const）。你现在循环遍历内部的所有元素map来计算它们，但是它map有一个size()成员函数，所以这不是必需的：

#include <numeric>  // std::accumulate

template<typename T>
size_t Graph<T>::num_edges() const {
    return
        std::accumulate(adj_list.begin(), adj_list.end(), size_t{0},
            [](size_t sum, const auto& node) {
                return sum + node.second.size();
            }) / 2;
}

在add_edge您可以跳过检查连接是否已经存在并尝试添加它。如果它是重复的，它将被拒绝：

template<typename T>
void Graph<T>::add_edge(const std::string& u, const std::string& v,
                        const T& weight)
{
    if(u == v) return; // don't allow linking a vertex with itself
    adj_list[u].emplace(v, weight);
    adj_list[v].emplace(u, weight);
}

您可能仍希望拥有该adjacent功能。在这种情况下，我会将其简化为如下所示：

template <typename T>
bool Graph<T>::adjacent(const string& u, const string& v) const {
    auto it = adj_list.find(u);
    return it != adj_list.end() && it->second.find(v) != it->second.end();

    // return it != adj_list.end() && it->second.contains(v); // C++20
}

推荐阅读