使用STL按成员变量对容器进行排序

Question

假设我有一些数据存储在unique_ptr容器中：

struct MyData {
    int id;  // a unique id for this particular instance
    data some_data; // arbitrary additional data
};

// ...

std::vector<std::unique_ptr<MyData>> my_data_vec;

my_data_vec的排序很重要。现在假设我有另一个MyDatas ID的向量：

std::vector<int> my_data_ids;

我现在想重新排列my_data_vec，使元素按照my_data_ids指定的顺序排列。 （不要忘记移动unique_ptr需要使用std::move（）进行移动语义。）

最有效的算法是什么？STL算法中有哪些适合实现此目的？我认为std::sort并没有什么帮助。

编辑：我可以使用O（n）内存空间（内存不太重要），但ID是任意的（在我的特定情况下，它们实际上是随机生成的）。

- AshleysBrain

---

id是任意的还是恰好是0...n-1？ - Thomas

编辑了问题以回答这些点。 - AshleysBrain

Answer 1

1. 创建一个将ID映射到my_data_ids索引的映射表。
2. 创建一个函数对象，根据该映射表中的ID索引比较std::unique_ptr<MyData>。
3. 使用该函数对象使用std::sort对my_data_vec进行排序。

这是一个示意图：

// Beware, brain-compiled code ahead!
typedef std::vector<int> my_data_ids_type;
typedef std::map<int,my_data_ids_type::size_type> my_data_ids_map_type;

class my_id_comparator : public std::binary_function< bool
                                                    , std::unique_ptr<MyData>
                                                    , std::unique_ptr<MyData> > {
public:
  my_id_comparator(const my_data_ids_map_type& my_data_ids_map)
    : my_data_ids_map_(my_data_ids_map) {}

  bool operator()( const std::unique_ptr<MyData>& lhs
                 , const std::unique_ptr<MyData>& rhs ) const
  {
     my_data_ids_map_type::const_iterator it_lhs = my_data_ids_map_.find(lhs.id);
     my_data_ids_map_type::const_iterator it_rhs = my_data_ids_map_.find(rhs.id);
     if( it_lhs == my_data_ids_map_.end() || it_rhs == my_data_ids_map_.end() )
       throw "dammit!"; // whatever
     return it_lhs->second < it_rhs->second;
  }
private
  my_data_ids_map_type& my_data_ids_map_;
};

//...

my_data_ids_map_type my_data_ids_map;
// ...
// populate my_data_ids_map with the IDs and their indexes from my_data_ids
// ...
std::sort( my_data_vec.begin(), my_data_vec.end(), my_id_comparator(my_data_ids_map) );

如果内存稀缺，但时间不重要，您可以放弃使用地图，并在每个比较中搜索 my_data_ids 向量中的ID。然而，你必须非常需要内存才能这样做，因为每个比较需要两个线性复杂度的操作，代价很高。

- sbi

---

这是一个非常好的解决方案，谢谢！我没想到sort会适用，但你证明了我错了 :) （顺便说一下，我正在使用C++0x，所以我在排序中使用了lambda - 让事情变得更整洁） - AshleysBrain

我认为这个解决方案的时间复杂度可能比你期望的要高。每个比较都是O(log n)而不是O(1)，因此总时间是O(n*(log n)^2)，而不是通常的O(n*log(n)). 这可能无关紧要，但如果有关紧要，那么使用std::unordered_map而不是std::map会更好。 - Richard Wolf

@Richard：这是一个很好的观点。如果有人找到更好的解决方案，我会非常感兴趣。 - sbi

如何尝试以下操作：1）创建一个从id到指针的映射；2）清空原始列表；3）对于id列表中的每个id，在映射中查找其id并将指针添加到列表末尾。这不是O(n*log(n))吗？ - AshleysBrain

我的建议是使用std :: unordered_map，它在最佳情况下可以以常数时间访问元素。只需确保使用的哈希函数是适当的即可。 - Richard Wolf

Answer 2

为什么不尝试将数据移动到STL Set中？你只需要实现比较函数，就可以得到一个非常快速的完美有序数据集合。

- Ioan Paul Pirau

---

好主意 - 但是 my_data_vec 的排序是有意义且任意的。使用 set 会丢失排序信息。 - AshleysBrain

为什么不尝试将数据移动到STL Set中呢？这样它们就不会按照“my_data_ids”指定的顺序排列了。 - sbi

Answer 3

为什么不直接使用 map<int, unique_ptr<MyData>>（或者 multimap）呢？

- rlbond