具有不满足严格弱排序的值的 c++ 排序范围

Question

我需要对一个范围内的值进行排序，以便该范围代表一个链。

struct Link
{
   int id;
   int next;
};

Link::id 和 Link::next 的值是任意的，它们本身不提供任何语义意义(对排序算法没有任何意义) ).

两个链接(排序后)的关系是:lhs.next正好是rhs.id。

先决条件

• 无序的 range 保证保存的值可以恰好排序到一个 chain 中。
• 保证值集合中没有递归(没有循环)

示例:

std::vector< Link> range{ { 4, 1}, { 1, 5}, { 3, 4}, { 2, 3}};
auto chain = some_algorithm( range);
// expect the ordering to be: { { 2, 3}, { 3, 4}, { 4, 1}, { 1, 5}};

我至少可以想到两种方法，但我怀疑这已经以惯用的方式解决了。所以，我的问题是:如何以惯用的方式解决这个问题？

Answer 1

我怀疑是否存在惯用的方法，因为这不是常见的情况。

链接主要由指针/迭代器(例如 std::list)完成，实际链接主要在插入时完成。

有趣的是找到第一个链接以及如何处理循环链和错误情况。