仅在相等可用时排序

Question

假设我们有一对对矢量:

std::vector<std::pair<A,B>> v;

其中A仅定义类型相等:

bool operator==(A const & lhs, A const & rhs) { ... }

您如何对具有相同first元素的所有对最终关闭进行排序？要清楚,我希望实现的输出应该与以下内容相同:

std::unordered_multimap<A,B> m(v.begin(),v.end());
std::copy(m.begin(),m.end(),v.begin());

但是,如果可能的话,我想:

• 进行分类.
• 避免为了相等而定义哈希函数.

编辑:其他具体信息.

在我的情况下,元素的数量不是特别大(我期望N = 10~1000),虽然我必须多次重复这种排序(~400)作为更大算法的一部分,并且已知的数据类型A相当大(它包含其中包含unordered_map~20 std::pair<uint32_t,uint32_t>的内容,这是阻止我发明排序,并且难以构建散列函数的结构)

Answer 1

第一个选项：cluster()和sort_within()

@MadScienceDreams 手写的双循环可以写成具有元素和簇cluster()的复杂算法。它重复调用（使用带有通用 lambda 的 C++14 风格，可以轻松适应 C++1，甚至可以通过编写自己的函数对象来适应 C++98 风格）：O(N * K)NKstd::partition

template<class FwdIt, class Equal = std::equal_to<>>
void cluster(FwdIt first, FwdIt last, Equal eq = Equal{}) 
{
    for (auto it = first; it != last; /* increment inside loop */)
        it = std::partition(it, last, [=](auto const& elem){
            return eq(elem, *it);    
        });    
}

您将您的输入vector<std::pair>称为

cluster(begin(v), end(v), [](auto const& L, auto const& R){
    return L.first == R.first;
});

下一个要编写的算法sort_within采用两个谓词：相等和比较函数对象，并重复调用std::find_if_not以查找当前范围的末尾，然后std::sort在该范围内进行排序：

template<class RndIt, class Equal = std::equal_to<>, class Compare = std::less<>>
void sort_within(RndIt first, RndIt last, Equal eq = Equal{}, Compare cmp = Compare{})
{
    for (auto it = first; it != last; /* increment inside loop */) {
        auto next = std::find_if_not(it, last, [=](auto const& elem){
            return eq(elem, *it);
        });
        std::sort(it, next, cmp);
        it = next;
    }
}

在已经集群的输入上，您可以将其称为：

sort_within(begin(v), end(v), 
    [](auto const& L, auto const& R){ return L.first == R.first; },
    [](auto const& L, auto const& R){ return L.second < R.second; }
);

实时示例显示了一些使用std::pair<int, int>.

第二个选项：用户定义的比较

即使没有operator<定义A，您也可以自己定义。在这里，有两个广泛的选择。首先，如果A是可散列的，则可以定义

bool operator<(A const& L, A const& R)
{
    return std::hash<A>()(L) < std::hash<A>()(R);
}

并std::sort(begin(v), end(v))直接写。如果您不想将所有唯一哈希值缓存在单独的存储中，您将需要O(N log N)调用。std::hash

其次， ifA不可散列，但有数据成员 getter和x()，唯一确定 上的相等性：您可以这样做y()z()A

bool operator<(A const& L, A const& R)
{
    return std::tie(L.x(), L.y(), L.z()) < std::tie(R.x(), R.y(), R.z());
}

同样你可以std::sort(begin(v), end(v))直接写。