c++ - 按相似性(相同 ID)对数据进行分组的最佳算法

Question

引用代码如下:

struct MyData
{
int ID;

// other members
};

std::vector<MyData> inputData;

std::vector<std::vector<MyData> > outputData = GroupByIDs(inputData);

基本上我想要做的是迭代输入数据并按 ID 将对象分组到一个新的迷你 vector 中，我将把它插入输出 vector 。所以最后我会有一个子 vector vector ，其中每个子 vector 包含具有相同 ID 的对象。

是否有一种千篇一律的最有效算法来做到这一点？因为我只能想到高复杂度的算法。

Answer 1

您可以根据 ID 对元素进行排序，然后使用 std::upper_bound 来完成此操作找到每个组的结束位置:

例如:

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

struct MyData
{
    int id;
    std::string info;

    MyData(int id, const std::string& info): id(id), info(info) {}

    // for sorting by id
    bool operator<(const MyData& d) const { return id < d.id; }
};

// function requires sorted data as input
std::vector<std::vector<MyData> > GroupByIDs(const std::vector<MyData>& data)
{
    std::vector<std::vector<MyData> > groups;

    decltype(data.end()) upper;

    for(auto lower = data.begin(); lower != data.end(); lower = upper)
    {
        // get the upper position of all elements with the same ID
        upper = std::upper_bound(data.begin(), data.end(), *lower);

        // add those elements as a group to the output vector
        groups.emplace_back(lower, upper);
    }

    return groups;
}

int main()
{
    std::vector<MyData> data {{2, "A"}, {4, "B"}, {3, "C"}, {4, "D"}, {9, "E"}, {3, "F"}};

    // function requires sorted data
    std::sort(data.begin(), data.end());
    std::vector<std::vector<MyData> > groups = GroupByIDs(data);

    for(auto const& group: groups)
    {
        if(!group.empty())
            std::cout << "group: " << group.front().id << '\n';

        for(auto const& d: group)
            std::cout << "     : " << d.info << '\n';

        std::cout << '\n';
    }
}

输出:

group: 2
     : A

group: 3
     : C
     : F

group: 4
     : B
     : D

group: 9
     : E