c++ - 对数组或 vector 进行排序和聚类

Question

我有以下数据结构:

std::vector<std::vector<std::pair <std::vector<unsigned>,std::vector<unsigned> >, unsigned > > A;

包含以下数据:

((7),(108,109)),5
((7),(108,109)),4
((7),(101,102,110)),3
((7),(101,102)),1
((7),(51)),2
((7),(51,54)),6
((7),(40,54,59)),7
((3),(108,109)),15
((3),(101,102,110)),13
((3),(101,102)),11
((3),(51)),12
((3),(51,54)),16
((3),(40,54,59)),17
((9),(108,109)),25
((9),(108,109)),24
((9),(108,109,110)),20
((9),(101,102,110)),23
((9),(111,112,120)),21
((9),(101,102)),29
((9),(51)),22
((9),(51,54)),26
((9),(40,54,59)),7
((8,2,10),(108,109)),25
((8,2,10),(108,109)),24
((8,2,10),(108,109,110)),20
((8,2,10),(101,102,110)),23
((8,2,10),(111,112,120)),21
((8,2,10),(101,102)),29
((8,2,10),(51)),22
((8,2,10),(51,54)),26
((8,2,10),(40,54,59)),7
((5,7),(108,109)),35
((5,7),(108,109)),34
((5,7),(108,109,110)),30
((5,7),(101,102,110)),33
((5,7),(111,112,120)),31
((5,7),(101,102)),39
((5,7),(51)),32
((5,7),(51,54)),36
((5,7),(40,54,59)),37

现在我想按以下方式安排我的数据:

((3),(101,102)),11
((3),(108,109)),15
((3),(101,102,110)),13
((7),(101,102)),1
((7),(108,109)),5
((7),(108,109)),4
((7),(101,102,110)),3
((9),(101,102)),29
((9),(108,109)),25
((9),(108,109)),24
((9),(101,102,110)),23
((9),(108,109,110)),20
((9),(111,112,120)),21
((5,7),(101,102)),39
((5,7),(108,109)),35
((5,7),(108,109)),34
((5,7),(101,102,110)),33
((5,7),(108,109,110)),30
((5,7),(111,112,120)),31
((8,2,10),(101,102)),29
((8,2,10),(108,109)),25
((8,2,10),(108,109)),24
((8,2,10),(101,102,110)),23
((8,2,10),(108,109,110)),20
((8,2,10),(111,112,120)),21

((3),(51)),12
((3),(51,54)),16
((3),(40,54,59)),17
((7),(51)),2
((7),(51,54)),6
((7),(40,54,59)),7
((9),(51)),22
((9),(51,54)),26
((9),(40,54,59)),7
((5,7),(51)),32
((5,7),(51,54)),36
((5,7),(40,54,59)),37
((8,2,10),(51)),22
((8,2,10),(51,54)),26
((8,2,10),(40,54,59)),7

排序是通过首先按大小对 pair<> 中第一个 pair<> 的第一个 vector 进行排序来实现的。然后按字典顺序对 vector 进行排序。 pair<> 中第二对的第二个 vector 也是先按 size 的大小排序，然后再按字典顺序排序。数据作为一个整体根据 vector A 的 pair<> 中第一对 <> 的第二个 vector 进行聚类。即用户指定根据以下条件将 A 的所有元素聚类在一起:((101,102),(108,109) ,(101,102,110),(108,109,110),(111,112,120)) 和 ((51),(51,54),(40,54,59)).

我知道可以按 (i) 排序。第一尺寸和(ii)。然后按字典顺序对 vector 进行排序。通过使用以下代码:

bool mySort(const pair<vector<unsigned>,vector<unsigned> > &a , const pair<vector<unsigned>,vector<unsigned> > &b)
{
    if (a.first.size() == b.first.size()) {
        //If sizes of the vectors are equal
        //Sort the graph lexicographically. 
        return std::lexicographical_compare(a.first.begin(),a.first.end(),b.first.begin(),b.first.end());pair<vector<unsigned>,vector<unsigned> > a
    } else {
        //Sort by size.
        return a.first.size() < b.first.size();
    }
}
int main()
{
    std::vector<std::pair<std::vector<unsigned>,std::vector<unsigned> > > a;
    std::sort(a.begin(),a.end(),mySort);
}

但我不明白如何在排序时将 A 的第一对 vector 中的第二个 vector 聚集在一起((i)。按大小(ii)。然后按字典序排序)。有人可以帮助我吗。

此外，我拥有的 vector A 的大小非常大。因此，任何高效的解决方案都将是锦上添花。

我使用的gcc版本是:gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

如果可以使用任何数据结构在 c 或 c++ 中实现相同的功能，我觉得很好(因为我只对我指定的特定顺序感兴趣)。

编辑:生成输入的代码:

std::vector<std::pair<std::vector<unsigned>, std::vector<unsigned> > > a; 
vector<unsigned> b; vector<unsigned> p;
b.push_back(7); p.push_back(108); p.push_back(109);
a.push_back(make_pair(b,p));
p.clear();
p.push_back(101); p.push_back(102); p.push_back(110);
a.push_back(make_pair(b,p));
p.clear();
p.push_back(101); p.push_back(102);
a.push_back(make_pair(b,p));
p.clear();
p.push_back(51);
a.push_back(make_pair(b,p));
p.clear();
p.push_back(51); p.push_back(54);
a.push_back(make_pair(b,p));
p.clear();
p.push_back(40); p.push_back(54); p.push_back(59);
a.push_back(make_pair(b,p));
b.clear(); p.clear();
b.push_back(3);
p.push_back(108); p.push_back(109); 
a.push_back(make_pair(b,p));
p.clear();
p.push_back(101); p.push_back(102); p.push_back(110);
a.push_back(make_pair(b,p));
p.clear();
p.push_back(101); p.push_back(102); 
a.push_back(make_pair(b,p));
p.clear();
p.push_back(51); 
a.push_back(make_pair(b,p));
p.clear();
p.push_back(51); p.push_back(54);
a.push_back(make_pair(b,p));
p.clear();
p.push_back(40); p.push_back(54); p.push_back(59);
a.push_back(make_pair(b,p));

Answer 1

您可以先进行分区 (std::partition)，然后对每个“簇”进行排序 (std::sort)。

以下内容可能会有所帮助:

using vec_pair = std::pair<std::vector<unsigned>, std::vector<unsigned>>;

std::set<std::vector<unsigned>> wanted = {
    {101,102}, {108,109}, {101,102,110}, {108,109,110}, {111,112,120}};

auto mid = std::partition(a.begin(), a.end(), [&](const vec_pair& p){
    return wanted.count(p.second) != 0;
});

std::sort(a.begin(), mid, mySort); // First cluster
std::sort(mid, a.end(), mySort);   // Second cluster

Live example

在 C++03 中，lambda 可以被这个仿函数代替:

struct allowed
{
public:
    explicit allowed(const std::set<std::vector<unsigned>>& wanted) :  wanted(wanted) {}

    bool operator () (const vec_pair& p) const {
        return wanted.count(p.second) != 0;
    }
private:
    const std::set<std::vector<unsigned>>& wanted;
};

代码变为:

std::vector<vec_pair>::iterator mid = std::partition(a.begin(), a.end(), allowed(wanted));