如何对两个容器的元组进行排序？

Question

我有两个元组，每个元组包含不同类型的容器。

std::tuple<containerA<typesA>...> tupleA;
std::tuple<containerB<typesB>...> tupleB;

因此，以一个示例来说明，tupleA 可以这样定义：

std::tuple<list<int>, list<float>> tupleA;

这两个容器，containerA和containerB是不同类型的。 typesA 和 typesB 不相交。我想按它们的大小对元组中的容器进行排序，并能够通过它们的类型访问它们。所以，举个例子：

std::tuple<list<int>, list<float>> tupleA {{2}, {3.3f, 4.2f}};
std::tuple<deque<double>, deque<uint8_t>> tupleB {{2.0, 1.2, 4.4}, {}};

auto sortedArray = sort(tupleA, tupleB);
sortedArray == {deque<uint8_t>, list<int>, list<float>, deque<double>};
sortedArray.get<list<float>>() == {3.3f, 4.2f};
std::get<list<int>>(tupleA).push_back(4);
std::get<list<int>>(tupleA).push_back(5);
std::get<list<int>>(tupleA).push_back(6);
sortedArray = sort(tupleA, tupleB);
sortedArray == {deque<uint8_t>, list<float>, deque<double>, list<int>};

最重要的部分是我必须存储sortedArray，而元组中元素的大小可能会改变。我无法创建这样的sort函数。访问sortedArray的实际语法并不重要。

我尝试使用容器数据的朴素索引来访问sortedArray内部的信息，例如使用std::pair<A, 1>来引用元组A中的第二个元素，但是我无法通过它访问元组的信息，因为它不是constexpr。

- user975989

---

дҪ ж— жі•дҪҝз”Ёstd::sortеҜ№е…ғз»„иҝӣиЎҢжҺ’еәҸпјҢеӣ дёәе®ғ们зҡ„йЎәеәҸжҳҜдёҚеҸҜеҸҳзҡ„гҖӮиҝҷж ·еҒҡдјҡеҲӣе»әдёҖдёӘж–°зұ»еһӢгҖӮ - user975989

你说“我想按大小排序元组中的容器。” 你所说的“大小”是指什么？它们包含的元素数量吗？如果是这样，那就是运行时信息，而在元组中类型的顺序是类型信息，因此需要在编译时确定。 - Jonathan Mee

@JonathanMee 是的，根据它们包含的元素数量。我不是指实际 tuple 的排序，而是我创建的 sortedArray 的排序。这个 sortedArray 可以是一个 vector 或者任何你需要的类型。 - user975989

我很好奇你是怎么得出这个要求的。 - Lightness Races in Orbit

我同意。毫无疑问，有人会建议使用void或其他绕过语言规则的方法来处理此问题。但这个问题与语言本身相抵触。最好的解决方案将涉及使用模板的力量，并利用*语言的能力。但要找到这样的解决方案，需要更多关于需求动机的信息。 - Jonathan Mee

Answer 1

这是可能的，但并不容易。

首先，您需要生成N个元素的每个排列的编译时列表（有N个阶乘）。

编写运行时和编译时排列对象（分开）。

将排列映射到索引的运行时映射。 （映射步骤）

将元组转换为（索引，大小）的向量。按大小排序。提取排列。将其映射到排列集的索引。 （排序步骤，使用映射步骤）

编写“魔术开关”，它接受函数对象f和排列索引，并使用编译时排列调用f。 （魔法步骤）

编写代码，根据编译时排列重新排序元组。 （重新排序步骤）

编写代码，接受函数对象f和元组。执行（排序步骤）。执行（魔法步骤），向其提供第二个函数对象g，该对象获取传入的排列和元组并（重新排序步骤），然后调用f。

将执行此操作的函数称为bob。

std::tuple<list<int>, list<float>> tupleA {{2}, {3.3f, 4.2f}};
std::tuple<deque<double>, deque<uint8_t>> tupleB {{2.0, 1.2, 4.4}, {}};

bob(concat_tuple_tie(tupleA, tupleB), [&](auto&& sorted_array){
  assert( std::is_same<
    std::tuple<deque<uint8_t>&, list<int>&, list<float>&, deque<double>&>,
    std::decay_t<decltype(sorted_array)>
  >::value, "wrong order" );
  sortedArray.get<list<float>>() == {3.3f, 4.2f};
});
std::get<list<int>>(tupleA).push_back(4);
std::get<list<int>>(tupleA).push_back(5);
std::get<list<int>>(tupleA).push_back(6);
bob(concat_tuple_tie(tupleA, tupleB), [&](auto&& sorted_array){
  assert( std::is_same<
    std::tuple<deque<uint8_t>&, list<float>&, deque<double>&, list<int>&>,
    std::decay_t<decltype(sorted_array)>
  >::value, "wrong order" );
});

个人而言，我怀疑你不需要这样做。

我可以做到这一点，但可能需要花费数小时，因此我不会在SO答案中这样做。您可以查看我的魔法开关代码以获取上述最神奇的内容。另一个困难的部分是排列步骤。

请注意，该代码使用延续传递样式。还要注意，实例化了lambda的每个排列，包括错误的排列，因此您的代码必须对每个排列有效。这可能导致疯狂的代码膨胀。

另一种替代方案可能涉及在容器周围创建类型抹消包装器，然后仅对这些包装器进行排序，但这不是您要求的。

- Yakk - Adam Nevraumont

Answer 2

您所描述的问题非常像是需要动态多态性，而不是静态多态性——您在解决问题时遇到的困难是因为固守于使用静态多态工具来表达。即，您需要一种集合类型（层次结构）或指向集合的指针，在运行时能够选择集合和数据类型，但仍能提供您所需的函数的统一接口，例如size（例如通过继承和虚拟函数）。例如，一个简单的示意草图可如下所示：

struct SequencePointer
{
    virtual size_t size() const = 0;
    virtual boost::any operator[](size_t n) const = 0;
};

template <typename Sequence>
struct SLSequencePointer
{
    const Sequence *ptr;
    size_t size() const { return ptr->size(); }
    boost::any operator[](size_t n) const { return (*ptr)[n]; }
};

- user1084944