6

我有一个类，其中包含一个容器，以及一个进入该容器的迭代器。如何正确实现移动构造函数？我似乎记得按照标准，您不能依赖迭代器在移动后保持有效（这太愚蠢了）。如果迭代器无效或其他什么，是否有一些方法可以“更新”迭代器？还是我必须动态分配容器，移动它，然后让迭代器保持有效？

4

2 回答 2

3

更新：使用 astd::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而不使迭代器无效，要么将容器放入 astd::unique_ptr并移动它。

第一种方法 ( swap) 要求两个实例都有容器实例，这可能比存储在std::unique_ptr. 当您经常移动实例时，std::unique_ptr基于 - 的方法对我来说似乎更可取，尽管每次访问都需要一个指针间接。自己判断（和衡量）什么最适合您的情况。

于 2013-10-26T19:45:06.637 回答
1

我认为对迭代器失效的隐含保证适用于移动 ctor。也就是说，以下内容应该适用于所有容器，但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

如果事实证明，对于 move ctor 没有这样的隐含保证，那么对于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<allocator_type>::propagate_on_container_swap::value是true [...] Any Compare, Pred, or Hashobjects 属于a并且b应该是可交换的，并且应该通过对非成员的不合格调用来交换swap. 如果allocator_traits<allocator_type>::propagate_on_container_swap::value是true，则 和 的分配器a也b应使用对 non-member 的不合格调用进行交换swap。否则，它们不应被交换，并且除非 a.get_allocator() == b.get_allocator().

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

移动构造OTOH只要求不抛出异常（对于分配器感知容器）；分配器总是被移动。

于 2013-10-26T22:18:58.430 回答