带 set 的 std::inserter - 插入到 begin() 或 end()？

Question

我有一些看起来像这样的代码：

std::set<int> s1, s2, out;

// ... s1 and s2 are populated ...

std::set_intersection(s1.begin(), s1.end(),
                      s2.begin(), s2.end(),
                      std::inserter(out, out.end()));

我读过，如果插入到集合中的值立即跟随作为“提示”给出的迭代器，则插入可以在摊销常数时间内完成。这在运行集合交集时显然是有益的，特别是因为写入 out 的所有内容都已按排序顺序排列。

我如何保证这种最佳性能？创建 std::inserter 时，out 为空，因此 out.begin() == out.end() 所以我不能看看我指定 out.begin() 还是 out.end() 作为提示有什么区别。但是，如果在 begin() 处插入每个元素时解释这一点，那么我似乎不会获得最佳的算法性能。这可以做得更好吗？

Answer 1

我选择 Alexander Gessler 的答案作为“正确”答案，因为它引导我找到了这个解决方案，我想无论如何我都会发布该解决方案。我编写了一个 last_inserter() ，它保证插入位置始终是最后一个元素的迭代器（如果为空则为 begin() ），因为 set 需要一个指向实际插入位置之前的元素的迭代器，以获得最佳性能（因此不是 end() - 它将是实际插入位置之后的一个）。

原始示例的用法如下：

std::set<int> s1, s2, out;

// ... s1 and s2 are populated ...

std::set_intersection(s1.begin(), s1.end(),
                      s2.begin(), s2.end(),
                      last_inserter(out));  // note no iterator provided

这保证插入提示始终是最后一个元素的迭代器，希望在对具有排序范围的集合使用输出迭代器时提供最佳情况性能，如上所述。

下面是我的实现。我认为它是特定于 Visual C++ 2010 的 STL 实现的平台，因为它很大程度上基于现有的 insert_iterator，而且我只能通过从 std::_Outit 派生来使其工作。如果有人知道如何使其便携，请告诉我：

// VC10 STL wants this to be a checked output iterator.  I haven't written one, but
// this needs to be defined to silence warnings about this.
#define _SCL_SECURE_NO_WARNINGS

template<class Container>
class last_inserter_iterator : public std::_Outit {
public:
    typedef last_inserter_iterator<Container> _Myt;
    typedef Container container_type;
    typedef typename Container::const_reference const_reference;
    typedef typename Container::value_type _Valty;

    last_inserter_iterator(Container& cont)
        : container(cont)
    {
    }

    _Myt& operator=(const _Valty& _Val)
    {
        container.insert(get_insert_hint(), _Val);
        return (*this);
    }

    _Myt& operator=(_Valty&& _Val)
    {
        container.insert(get_insert_hint(), std::forward<_Valty>(_Val));
        return (*this);
    }

    _Myt& operator*()
    {
        return (*this);
    }

    _Myt& operator++()
    {
        return (*this);
    }

    _Myt& operator++(int)
    {
        return (*this);
    }

protected:
    Container& container;

    typename Container::iterator get_insert_hint() const
    {
        // Container is empty: no last element to insert ahead of; just insert at begin.
        if (container.empty())
            return container.begin();
        else
        {
            // Otherwise return iterator to last element in the container.  std::set wants the
            // element *preceding* the insert position as a hint, so this should be an iterator
            // to the last actual element, not end().
            return (--container.end());
        }
    }
};

template<typename Container>
inline last_inserter_iterator<Container> last_inserter(Container& cont)
{
    return last_inserter_iterator<Container>(cont);
}

Answer 2

您可以使用自定义函子代替 std::inserter ，并在每次插入新元素时重新调用 out.end() 。

或者，如果您的值按降序排序，则 out.begin() 也可以。

Answer 3

根据 http://gcc.gnu.org/onlinedocs /gcc-4.8.0/libstdc++/api/a01553_source.html

insert_iterator&
operator=(typename _Container::value_type&& __value)
{
  iter = container->insert(iter, std::move(__value));
  ++iter;
  return *this;
}

其中 iter 最初指向您传递给 std::inserter 的迭代器。因此 iter 将始终指向您刚刚插入的值之后的一个，如果您按顺序插入，则应该具有最佳效率。