如果您有一个std::list，并且希望以不同的顺序将其重建为新的std::list，而不需要从迭代器复制到原始的std::list，这是非常简单的，例如，如果您对迭代器进行混洗并从混洗的顺序重建：
int main(int argc, char **argv)
{
std::list<std::string> args(&argv[1], &argv[argc]);
std::vector<std::list<std::string>::const_iterator> vec;
for (auto it = std::cbegin(args), last = std::cend(args); it != last; ++it) {
vec.push_back(it);
}
std::shuffle(std::begin(vec), std::end(vec), std::mt19937(42)); // Shuffle with reproducible PRNG
std::cout << "Shuffled vec:n";
for (auto it : vec) {
std::cout << *it << std::endl;
}
std::list<std::string> shuffled_args;
for (auto it : vec) {
shuffled_args.splice(std::end(shuffled_args), args, it);
}
std::cout << "Shuffled list:n";
for (const auto& s : shuffled_args) {
std::cout << s << std::endl;
}
return 0;
}
这非常有效；在我的系统上，当使用g++ -std=c++17 -O3 -flto -Wall shuffle_list.cpp编译并使用./a.out a b c d e运行时，打印vector和混洗的list的结果一致(按顺序为e a c d b)：在线试用！
但是，当我尝试使用std::forward_list编写一个变体版本时，事情变得更加棘手。这是唯一一个没有segfault的版本(注释指示更改)：
int main(int argc, char **argv)
{
std::forward_list<std::string> args(&argv[1], &argv[argc]);
std::vector<std::forward_list<std::string>::const_iterator> vec;
for (auto it = args.cbefore_begin(), last = std::cend(args); std::next(it) != last; ++it) { // Changed to store iterators before each element since splice_after needs them
vec.push_back(it);
}
std::shuffle(std::begin(vec), std::end(vec), std::mt19937(42));
std::cout << "Shuffled vec:n";
for (auto it : vec) {
std::cout << *std::next(it) << std::endl; // Must advance each iterator to see value stored
}
std::forward_list<std::string> shuffled_args;
auto splice_loc = shuffled_args.cbefore_begin(); // Must begin inserting at beginning of new forward_list
for (auto it : vec) {
shuffled_args.splice_after(splice_loc, args, it); // splice_loc is before when node should go, it points to node before node to splice, great
splice_loc = it; // it should now be last element, it will be next splice location
}
std::cout << "Shuffled list:n";
for (const auto& s : shuffled_args) {
std::cout << s << std::endl;
}
return 0;
}
这里的输出与vector的输出相同，但对于生成的forward_list，它只输出e：在线试用！如果你尝试其他有趣的事情，比如用++splice_loc;替换splice_loc = it;(这在逻辑上是等效的；你在当前位置后面拼接了一个节点，推进迭代器应该会把你移到那个新节点)，它会出错。
我想我知道为什么它会被破坏(完整代码和用++splice_loc替换有两种不同的方式)，我认为我所采取的方法是不可行的。在分段错误代码中，当我拼接节点时，迭代器仍然有效，但原始结构中的一些迭代器在我到达它们之前就被移动了(例如，我使用位置1的迭代器将项目移动到2，当我尝试将3移动到2时，它会移动新列表中2后面的其他随机事物)，现在我正试图在新的forward_list中拼接它们后面的内容(这违反了API，因为我声称它们来自args，而实际上它们已经被移动到shuffled_args)。在我选择AFAICT的设计中，没有很好的解决方案更新：在非分段错误代码中，我应该在拼接之前保存std::next(it)，并将其分配给splice_loc(通过分配可能仍在原始forward_list中的it，splice_loc现在指向原始列表，并且我可能正在进行未定义的行为，最终会对原始列表进行比新列表更多的修改)。
我的问题是：
有没有一种好的方法来做我想要的事情，从forward_list中提取迭代器，将它们混合在一起(使用shuffle或排序或其他什么)，然后通过直接节点传输(不复制或移动所包含元素的任何)以替代顺序构建新的forward_list，并有效地做到这一点我能想到的最好办法是为vector中的每个节点制作一个新的专用forward_list，这样我就可以将该单个节点拼接到最终的forward_list。这感觉很难看，而且可能比list等效行为更昂贵。有更好的方法吗？多元素forward_list解决方案真的很棒吗？
对于好奇的人来说：这是一个问题的精简再现，我正在编写一个键控排序算法(如Schwartzian变换，又名装饰排序取消装饰)，这完全是一个个人挑战。我正试图为std::list和std::forward_list制作一个专门的版本，通过装饰迭代器而不是值本身来避免对正在排序的值进行任何复制或移动，所以一旦我根据计算的键对集合进行了排序，我就可以通过使用splice/splice_after以排序顺序重建容器来构造新的list或forward_list，而不复制或移动所包含的值中的单个值。
这是一个基于我最初建议使用一堆单节点std::forward_lists的工作版本。制作所有这些std::forward_lists感觉效率很低，但据我所知，std::forward_list的规格非常窄，几乎可以保证它被实现为一个围绕单个指针的包装器，这应该是非常低的开销。它确实可以工作，没有所包含元素的副本或移动，也没有(由于使用了deque)forward_list本身的任何副本或移动(除了我们清空它们以将它们拼接到输出forward_list上时)，并且它只遍历输入forward_list一次(通过反复提取第一个节点来破坏它，直到它被清空)。
它不是最漂亮的，但也没有我预期的那么难看或效率低下。
int main(int argc, char **argv)
{
std::forward_list<std::string> args(&argv[1], &argv[argc]);
std::deque<std::forward_list<std::string>> deq; // Use deque so we never have to move existing forward_lists, and don't need to pre-walk to find size to reserve for vector
while (!args.empty()) {
auto& flist = deq.emplace_back();
flist.splice_after(flist.cbefore_begin(), args, args.cbefore_begin()); // Extract a single node from input to populate new forward_list
}
std::shuffle(std::begin(deq), std::end(deq), std::mt19937(42)); // Shuffle with reproducible PRNG
std::cout << "Shuffled deq:n";
for (auto& flist : deq) {
std::cout << flist.front() << std::endl;
}
std::forward_list<std::string> shuffled_args;
auto splice_loc = shuffled_args.cbefore_begin();
for (auto&& flist : deq) {
shuffled_args.splice_after(splice_loc, std::move(flist)); // splice single element forward_list contents onto end
++splice_loc; // We added one element, move the iterator forward by one
}
std::cout << "Shuffled list:n";
for (const auto& s : shuffled_args) {
std::cout << s << std::endl;
}
return 0;
}
在线试用！
需要明确的是，如果有人有更好的解决方案，我很高兴听到他们的消息，我很乐意给更清洁的东西打勾。
您想要的与单链表的概念不兼容(这就是forward_list)。算法的核心要求能够在列表中使用迭代器作为从列表中提取该节点的足够信息。
要从这样的列表中删除一个节点，您需要获取前一个节点并更改其"；下一个"；指向要删除节点的"的指针；下一个"；指针。不能仅从单链列表中的特定节点获取上一个节点。
如果将指向单链表节点的一堆指针弄乱(这就是forward_list::iterator)，则无法获取前一个节点来提取该节点。
您唯一能做的就是将所有节点提取到只包含一个元素的单个forward_list中，将它们弄乱，然后将这些单个元素列表拼接到最终列表中。但即使这样也需要小心，因为splice_after不会返回迭代器。因此，您需要在拼接之前从单个元素列表中获取迭代器，将其拼接，然后将其用作下一个拼接的pos。第一个不应该是拼接；相反，这应该是一个举动。