如何生成与图中所有顶点不同的通用标识符？支持整数及字符串类型

针对你需要支持的整数类型（int32_t、int64_t）和字符串类型（std::string、std::string_view），可以通过类型专属逻辑快速生成不与现有顶点冲突的标识符，以下是具体实现思路和代码示例：

整数类型处理逻辑 #

对于整数类型，直接基于现有顶点的极值生成即可保证唯一性：

• 若顶点集合为空，返回类型默认值（如0）
• 若集合非空，取所有顶点的最大值，返回max_val + 1；如果最大值已是类型上限（如int32_t::max()），则返回min_val - 1（避免溢出）

这种方式无需额外遍历检查，生成的标识符必然不在现有集合中。

字符串类型处理逻辑 #

字符串类类型推荐两种实用策略：

1. 固定特殊标识：使用带有特殊前缀的字符串（如"__super_vertex__"），这类标识在业务场景中几乎不会与用户自定义顶点重复；若担心极端冲突，可先检查该字符串是否存在，不存在则直接使用，存在则追加递增数字（如"__super_vertex_1__"）。
2. 极简兜底方案：如果能接受少量性能损耗，也可以直接遍历现有顶点，拼接出一个全新字符串（如将所有顶点字符串拼接后加后缀），但仅适合顶点数量极少的场景。

代码实现示例 #

#include <concepts>
#include <vector>
#include <string>
#include <algorithm>
#include <limits>

// 整数类型的超级顶点生成函数
template<std::integral T>
T generate_super_vertex_id(const std::vector<T>& existing_vertices) {
    if (existing_vertices.empty()) {
        return T{};
    }
    auto [min_it, max_it] = std::minmax_element(existing_vertices.begin(), existing_vertices.end());
    const T max_val = *max_it;
    if (max_val == std::numeric_limits<T>::max()) {
        return *min_it - 1;
    } else {
        return max_val + 1;
    }
}

// 字符串类型的超级顶点生成函数
template<std::convertible_to<std::string> T>
std::string generate_super_vertex_id(const std::vector<T>& existing_vertices) {
    const std::string base_id = "__super_vertex__";
    // 先检查基础标识是否存在
    if (std::find(existing_vertices.begin(), existing_vertices.end(), base_id) == existing_vertices.end()) {
        return base_id;
    }
    // 若存在则递增后缀
    size_t suffix = 1;
    std::string candidate;
    do {
        candidate = base_id + "_" + std::to_string(suffix);
        suffix++;
    } while (std::find(existing_vertices.begin(), existing_vertices.end(), candidate) != existing_vertices.end());
    return candidate;
}

// 使用示例
int main() {
    // 整数类型示例
    std::vector<int32_t> int_vertices = {1,3,2,5,6};
    auto int_super_id = generate_super_vertex_id(int_vertices); // 返回7

    // 字符串类型示例
    std::vector<std::string> str_vertices = {"US", "China", "Japan", "Korea"};
    auto str_super_id = generate_super_vertex_id(str_vertices); // 返回"__super_vertex__"
    return 0;
}

注意事项 #

• 对于std::string_view类型，上述模板会自动转换为std::string处理，生成的标识符可直接转为string_view使用。
• 整数类型的溢出处理仅针对极值场景，常规业务中很少遇到；若你的场景存在大量接近类型极值的顶点，可调整逻辑为遍历寻找第一个未使用的整数。

内容的提问来源于stack exchange，提问作者frozenca