jjzjj

c++ - 仅在相等可用时排序

coder 2023-11-17 原文

假设我们有一个 vector 对:

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>，这是阻止我发明排序的结构，并且很难构建哈希函数)

最佳答案

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

@MadScienceDreams 手写的双循环可以写成 cluster() O(N * K)的算法N 的复杂性元素和 K集群。它反复调用 std::partition (使用带有通用 lambda 的 C++14 风格，很容易适应 C++1，甚至通过编写您自己的函数对象来适应 C++98 风格):

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; }
);

Live Example使用 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如果您不想在单独的存储中缓存所有唯一的哈希值。

其次，如果A不可哈希，但有数据成员 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))直接。

关于c++ - 仅在相等可用时排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25326089/

用时ampcodestdconstc++algorithmsortingpartition

有关c++ - 仅在相等可用时排序的更多相关文章

  1. ruby - Ruby 的 Hash 在比较键时使用哪种相等性测试？ - 2

    我有一个围绕一些对象的包装类，我想将这些对象用作散列中的键。包装对象和解包装对象应映射到相同的键。一个简单的例子是这样的:classAattr_reader:xdefinitialize(inner)@inner=innerenddefx;@inner.x;enddef==(other)@inner.x==other.xendenda=A.new(o)#oisjustanyobjectthatallowso.xb=A.new(o)h={a=>5}ph[a]#5ph[b]#nil,shouldbe5ph[o]#nil,shouldbe5我试过==、===、eq?并散列所有无济于事。

  2. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  3. ruby-on-rails - ActiveRecord 对象相等 - 2

    根据ActiveRecord::Base的文档:==(comparison_object)Returnstrueifcomparison_objectisthesameexactobject,orcomparison_objectisofthesametypeandselfhasanIDanditisequaltocomparison_object.id.Notethatnewrecordsaredifferentfromanyotherrecordbydefinition,unlesstheotherrecordisthereceiveritself.Besides,ifyoufet

  4. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  5. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  6. ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2

    我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night

  7. ruby-on-rails - 在具有 ActiveRecord 条件的相关模型中按字段排序 - 2

    我正在尝试按Rails相关模型中的字段进行排序。我研究的所有解决方案都没有解决如果相关模型被另一个参数过滤？元素模型classItem相关模型:classPriority我正在使用where子句检索项目:@items=Item.where('company_id=?andapproved=?',@company.id,true).all我需要按相关表格中的“位置”列进行排序。问题在于，在优先级模型中，一个项目可能会被多家公司列出。因此，这些职位取决于他们拥有的company_id。当我显示项目时，它是针对一个公司的，按公司内的职位排序。完成此任务的正确方法是什么？感谢您的帮助。PS-我

  8. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  9. ruby - 按数字(从大到大)然后按字母(字母顺序)对对象集合进行排序 - 2

    我正在构建一个小部件来显示奥运会的奖牌数。我有一个“国家”对象的集合，其中每个对象都有一个“名称”属性，以及奖牌计数的“金”、“银”、“铜”。列表应该排序:1.首先是奖牌总数2.如果奖牌相同，按类型分割(金>银>铜，即2金>1金+1银)3.如果奖牌和类型相同，则按字母顺序子排序我正在用ruby​​做这件事，但我想语言并不重要。我确实找到了一个解决方案，但如果感觉必须有更优雅的方法来实现它。这是我做的:使用加权奖牌总数创建一个虚拟属性。因此，如果他们有2个金牌和1个银牌，加权总数将为“3.020100”。1金1银1铜为“3.010101”由于我们希望将奖牌数排序为最高的，因此列表按降序排

  10. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

随机推荐