通过节点拼接构建从迭代器中构建新的forward_list

Question

如果您有一个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进行编译时同时打印vector和洗牌list同意（eacd b）的结果：

但是，当我尝试使用std :: forffer_forcep_list编写变体版本时，事情变得更加糟糕。这是唯一一个不发表的版本（带有指示更改的注释）：

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> forward_list，它只是输出< code>e: Try it online! If you try other fun things like replacing splice_loc = it;带有++ splice_loc;（在逻辑上等效；您在当前位置后在节点中剪接，然后推进迭代器应将您移至该新节点），然后将其转移。

我想我知道为什么会破裂（完整代码的两种不同的方法和++ splice_loc ），而且我认为我采用的方法不可挽救。在segfaulting代码中，当我拼写节点时，迭代器仍然有效，但是在我到达它们之前，原始结构中的某些迭代器已移动（例如，我使用位置1的迭代器以2的方式移动项目，并且我尝试尝试要通过2移动3，它会移动新列表中2的其他随机事物），现在我试图将新forward> forward_list中的内容拼接（并违反API，正如我声称它们来自args时，当它们实际上已移至shuffled_args时）。在我选择的Afaict的设计中，没有任何良好的修复。 更新：在非隔离代码中，我应该保存std :: next（IT）在剪接之前，然后将其分配给splice_loc （通过分配it，它可能仍在原始forward_list中，splice_loc现在指向原始列表，我可能参与不确定的行为最终比新列表更改了原始列表）。

我的问题是：

是否有好做我想做的事的方法，从forward_list中夺取迭代器，将它们乱七八糟（使用shuffle或排序或其他），然后通过直接节点传输（无包含元素的任何副本或移动）构建新的forward_list 如此有效吗？我能想到的最好的是为 node做一个新的专用forward_list，vector，所以我可以将单个节点拼接到最终forward_list。这感觉很难看，并且可能比list等效行为贵。有更好的方法吗？许多单元素forward_list解决方案实际上很棒吗？

---

出于好奇：这是我正在编写一种键入分类算法的问题的删除复制品（如Schwartzian Transform aka aka diborate-sort-sort-noctate），这完全是个人的挑战。我正在尝试为std :: list和std :: forward_list制作一个专门版本，该版本避免了通过装饰迭代器而不是而不是通过装饰迭代的值分类的任何副本或移动值本身，因此，一旦我按计算密钥对集合进行了排序，我就可以通过使用splice来构造新的list forward_list /splice_after以排序的顺序重建容器，而无需复制或移动包含的值之一。

Answer 1

这是一个基于我的原始建议，使用一堆单节std :: forffer_list s。 感觉效率低下，使所有此std :: forffer_list s s，但据我所知，std :: forffer_list是指定的狭义地，几乎可以肯定地将其作为单个指针围绕的包装器实施，这应该是很低的开销。它确实有效，没有包含元素的副本或移动，也没有（由于使用Deque）当我们将它们清空以将它们拼接到输出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;
}

更好的解决方案，我很高兴听到他们的消息，并希望将复选标记提供给更干净的东西。

Answer 2

您想要的与单连锁列表的概念不兼容（这是forward_list IS）。您的算法以此为核心，需要能够将迭代器使用到列表中，作为足够的信息来从列表中提取该节点。

要从此列表中删除节点，您需要获取上一个节点并更改其“下一个”指针，以指向待命的节点的“下一个”指针。您不能仅在单连锁列表中的特定节点中获得以前的节点。

如果您将一堆指针弄乱到单个链接列表的节点（这是forward_list :: iterator s），则无法获取先前的节点以提取该节点。

您唯一可以做的就是将所有节点提取到单个forward_list s中， s含有一个元素，将它们弄乱，然后将这些单元素列表拼写到最终列表中。但是，即使这也需要护理，因为splice_after不返回迭代器。因此，您需要从单元素列表中获取迭代器，然后将其拼接成拼接，然后将其用作下一个剪接的pos。第一个不应该是剪接。相反，这应该是一个举动。