按无序集排序 [英] Sorting on unordered_sets
问题描述
我有每帧创建的项目列表,需要对其进行排序.
每个项目的第一个要排序的成员变量是unordered_set
.
I have a list of items that are created each frame and need to be sorted.
Each Item's first member variable to sort by is an unordered_set
.
我已将其移至系统中所有位置的有序集合,因此可以在项目列表中对其进行排序.但是我遭受了另一个代码的性能打击.
I've moved this to an ordered set everywhere in the system so I can sort it in the list of items. But I'm suffering a performance hit in another are of the code foe this.
请记住,每件物品都将被销毁并在逐帧的基础上重新创建,我能做些什么来将它们保存在unordered_set
中并对它们进行排序吗?
Bearing in mind that each item will be destroyed and be recreated on a per-frame basis, is there anything I can do to hold these in unordered_set
s and sort them?
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
}
}
};
推荐答案
鉴于std::unordered_set<Key, Hash>
对于任意可哈希的Key
,您可以定义
Given std::unordered_set<Key, Hash>
for arbitrary hashable Key
, you could define
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
which will use the ordering on hash indices of Key
. You can then define an ordering on item
bool operator< (item const& L, item const& R)
{
return std::tie(L.sortI, L.sortUS) < std::tie(R.sortI, R.sortUS);
}
和std::tie
会根据对item
成员的引用而制成std::tuple
,以便您可以使用std::tuple
中的operator<
.
and std::tie
will make a std::tuple
out of references to the members of your item
so that you can use the operator<
from std::tuple
.
注意:由于std::tuple
比较和lexicographical_compare
都具有此属性,因此可以轻松证明上述比较是StrictWeakOrder(对std::sort
的要求).
NOTE: you can easily prove that the above comparison is a StrictWeakOrder (a requirement for std::sort
) since both the std::tuple
comparison and the lexicographical_compare
have this property.
但是,unordered_set
的顺序在其他方面非常不寻常.
However, the ordering of unordered_set
is very unusual in other respects.
- 散列键索引与您对元素进行迭代的顺序不符(有一些模运算将散列键映射到容器中的索引)
- 将元素添加到
unordered_set
可能会导致重新哈希并导致先前的排序无效
- the hashed key index doesn't correspond to the order in which you iterate over elements (there is some modulo operation that maps hashed keys to indices in the container)
- adding elements to an
unordered_set
can result in rehashing and invalidation of previous orderering
这篇关于按无序集排序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!