迭代器进入已移动的容器

Question

迭代器进入已移动的容器

6

我有一个类，其中包含一个容器和一个该容器的迭代器。我应该如何正确实现移动构造函数？我记得根据标准，你不能依赖于移动后迭代器仍然有效（这太愚蠢了）。是否有一些方法可以“更新”迭代器，如果它被使无效或其他原因？还是我必须动态分配容器，移动它，然后通过这种方式使迭代器保持有效？

- Puppy

1

你可以使用 swap 函数，但无法确定是否可以移动元素："任何使用 swap() 函数交换容器中元素的引用、指针或迭代器都会失效。[注意: end() 迭代器不引用任何元素，因此可能会失效。—结尾注释]" [container.requirements.general]/10 - dyp

1

关于 "愚蠢" 的问题：如果你想到 std::array，它就不那么愚蠢了。在其他一些情况下，标准允许容器的移动构造函数具有线性复杂度，例如当分配器发生变化时。另一个例子可能是包含嵌入式第一个/最后或根节点的容器。 - Daniel Frey

1

它必须是任何容器吗？还是你有一个特定的容器在脑海中？有些容器会比其他容器更棘手。但我认为不同的容器可能有不同但合理的解决方案。例如，我会以不同的方式处理list和string，但我认为我可以为它们两个提出论据。 - Howard Hinnant

1

@LightnessRacesinOrbit：笔误，我是指“move”，而不是“move”。已更正。另外，你是怎么判断我指的是哪个 std::move 的——是在 <utility> 中只获取右值的那个，还是在 <algorithm> 中执行 0 或多个移动的那个？;-) - Steve Jessop

1

@LightnessRacesinOrbit：嗯，如果是这样的话，那么DeadMG的回忆（“按标准，您不能指望在移动后迭代器仍然有效”）就不完全正确了，至少对于在交换时保持有效性的容器来说是如此，这是大多数或可能是所有标准容器，除了array。那么问题的正确答案是“mu”。 - Steve Jessop

显示剩余18条评论

2个回答

1

我认为迭代器失效的隐式保证适用于移动构造函数。也就是说，对于除了 std::array 之外的所有容器，以下操作都应该有效：

template<class Container>
struct foo_base
{
    Container c;
    Container::iterator i;

    foo_base(foo_base&& rhs, bool is_end)
    : c( std::move(rhs.c) )
    , i( get_init(is_end, rhs.i) )
    {}

    Container::iterator get_init(bool is_end, Container::iterator ri)
    {
        using std::end; // enable ADL
        return is_end ? end(c) : ri;
    }
};

template<class Container>
struct foo : private foo_base<Container>
{
    foo(foo&& rhs)
    : foo_base(std::move(rhs), rhs.i == end(rhs.c))
    {}
};

复杂的基类初始化是必要的，因为如果分配器在移动赋值时不传播，则不需要移动赋值。检查迭代器是必要的，因为end()迭代器可能无效；必须在容器移动之前执行此检查。但是，如果您可以确保分配器会传播（或者对于您的情况，移动赋值不会使迭代器失效），则可以使用下面更简单的版本，将swap替换为移动赋值。

注意：get_init函数的唯一目的是启用ADL。可能foo_base有一个成员函数end，这会禁用ADL。using-declaration停止未限定的查找以查找可能的成员函数，因此始终执行ADL。如果您舒适地放弃ADL，也可以使用std::end(c)并摆脱get_init。

如果事实证明没有这样的移动构造函数的隐式保证，仍然存在swap的显式保证。为此，您可以使用：

template<class Container>
struct foo
{
    Container c;
    Container::iterator i;

    foo(foo&& rhs)
    {
        using std::end; // enable ADL
        bool const is_end = (rhs.i == end(rhs.c));

        c.swap( rhs.c );

        i = get_init(is_end, rhs.i);
    }

    Container::iterator get_init(bool is_end, Container::iterator ri)
    {
        using std::end; // enable ADL
        return is_end ? end(c) : ri;
    }
};

然而，交换操作有一些要求，这些要求定义在[container.requirements.general]/7+8中：

调用容器的swap函数的行为是未定义的，除非被交换的对象具有相等的分配器或allocator_traits::propagate_on_container_swap::value为true [...] 属于a和b的任何Compare、Pred或Hash对象都应该是可交换的，并且应该通过对非成员swap的不限定调用进行交换。如果allocator_traits::propagate_on_container_swap::value为true，则应该使用对非成员swap的不限定调用来交换a和b的分配器。否则，它们不应该被交换，除非a.get_allocator() == b.get_allocator()，否则行为是未定义的。

即两个容器应该（但不必）具有相等的分配器。

移动构造函数只需要确保没有抛出异常（对于支持分配器的容器而言）；分配器总是被移动。

- dyp

好的，我会在这里加上一个注释：在Container规范中，std::array有很多特殊情况。一个行为类似于std::array的非标准容器可能不符合Container要求，因为它不是std::array，因此不包含这些特殊情况。 - dyp

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Frey · Accepted Answer

更新: 使用 std::unique_ptr 作为容器的持有者是规范的通用解决方案 - 只需转移所有权并交换迭代器，而不要移动容器。正如您已经提到的，您可以将其作为优化特殊处理，尽管我希望通用解决方案也非常高效，并且只接受在证明它对您的用例真正有性能优势之后才会增加更多复杂性（也就是潜在错误）。

我将保留原先的答案以供后续读者参考：请阅读它和评论，了解为什么其他解决方案实际上无法工作，在哪些情况下它们会引起麻烦。

更新迭代器的明显方式是:

Container c = ...;
Container::iterator it = ...;

const auto d = std::distance( c.begin(), it );
Container n = std::move(c);
it = n.begin();
std::advance( it, d );

当迭代器是随机访问迭代器时，容器通常是线性的，但是常数是恒定的。

由于您可能不想这样做，因此有两种选项可以帮助您：要么默认构造新容器并在不使迭代器失效的情况下使用 swap，要么将容器放入 std::unique_ptr 中并移动它。

第一种方法（swap）需要两个实例都具有容器实例，而这可能比存储在 std::unique_ptr 中的简单单指针稍大。当您经常移动实例时，我认为基于 std::unique_ptr 的方法似乎更可取，尽管每个访问都需要一个额外的指针间接引用。请自行评估（和测量），看看哪种方案最适合您的情况。