在unordered_sets上排序

我有一个项目列表，每个框架都创建并需要排序。每个商品的第一个成员变量排序是unordered_set。在unordered_sets上排序

我已经把它移到了系统中的一个有序集合，所以我可以在项目列表中对它进行排序。但是我在另一个代码中遇到了性能问题。

请记住，每个项目将被销毁，并在每帧的基础上重新创建，有什么我可以做，以保持这些在unordered_set s和排序呢？

class item 
{ 
    public: 
    unordered_set<int> _sortUS; 
    int _sortI; 
    //Other members to sort 
    bool operator<(const item& that) const 
    { 
     if(_sortI != that._sortI) 
     { 
      return _sortI < that._sortI; 
     } 
     else if(_sortUS != that._sortUS) 
     { 
      return ??? // this is what I need. I don't know how to compare these without converting them to sets 
     } 
    } 
};

来源

2014-02-10 Jonathan Mee

这个问题不是100％清楚 - 你想排序（unsorted_set）的（概念）序列？ – Angew

我有一个项目列表，我需要根据它们的成员变量进行排序。在这个排序中要比较的成员变量之一是'unordered_set'。我只是想明确说明我拥有该项目的比较运算符，因此我可以更改运算符比较'unordered_set'的方式。 –

因此，显然你已经足够了解这些项目的排序谓词（比如'operator <'）。我仍然不清楚问题是什么 - 对于在代码中表达时遇到问题的unorderd_set，您是否有一个“低于”标准（如果是这样，请将其添加到问题中）还是其他内容？ – Angew

鉴于std::unordered_set<Key, Hash>任意哈希的Key，你可以定义

template<class Key, class Hash = std::hash<Key>> 
bool operator< (std::unordered_set<Key, Hash> const& L, std::unordered_set<Key, Hash> const& R) 
{ 
    return std::lexicographical_compare(
     begin(L), end(L), begin(R), end(R), 
     [](Key const& kL, Key const& kR) { 
     return Hash()(kL) < Hash()(kR);  
    }); 
}

将使用上的Key哈希索引的顺序。然后，您可以在item

bool operator< (item const& L, item const& R) 
{ 
    return std::tie(L.sortI, L.sortUS) < std::tie(R.sortI, R.sortUS); 
}

和std::tie定义排序将使std::tuple了引用您item这样的成员，你可以从std::tuple使用operator<。

注意：你可以很容易地证明上述比较是StrictWeakOrder（用于std::sort的要求），因为这两个std::tuple比较和lexicographical_compare具有这种性质。

但是，在其他方面，unordered_set的排序是非常不寻常的。

散列密钥索引不对应于在其中遍历元素的顺序（有一些模操作该散列键映射到索引中的容器）
将元素添加到一个unordered_set可导致重新排序和无效的先前的排序

来源

2014-02-10 22:00:21 TemplateRex

你能帮助我理解你的lambda中的Hash命令在做什么，我不明白这将如何帮助我们维持一个严格的排序_（或者甚至是一般的做法）。 –

@JonathanMee通常，元素在'unordered_set'中没有定义'operator'（你的'int'有，但这是个例外）。你可以做的唯一假设是它们可以被散列成一个整数。所以你可以根据这个定义一个排序。 'Hash（）（kL）'命令创建一个类型为“Hash”的函数对象，并用参数'kL'调用它。 – TemplateRex

在unordered_sets上排序

回答

相关问题