代码之家 › 专栏 › 技术社区 › AshleysBrain

std::inserter with set-insert to begin()或end()?[复制品]

set iterator insert stl c++

AshleysBrain · 技术社区 · 14 年前

这个问题已经有了答案:

Is there a difference between using .begin() vs .end() for std::inserter for std::set? 2答

我有一些代码如下所示:

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.begin() == out.end() 所以我看不出我说的有什么区别 out.begin() 或 out.end() 作为提示。但是,如果在插入 begin() 似乎我得不到最佳的算法性能。这能做得更好吗?

3 回复 | 直到 11 年前

Alexander Gessler 14 年前

您可以使用自定义函数而不是 std::inserter 再呼叫 out.end() 每次插入新元素时。

或者,如果值按降序排序, out.begin() 会很好。

AshleysBrain 14 年前

我选择了亚历山大格斯勒的答案作为“正确的”答案,因为它引导我找到了这个解决方案,我认为我无论如何都会发表。我写了一篇 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

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

下面是我的实现。我认为它是特定于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);
}

robson 11 年前

根据 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总是指向刚刚插入的值的一个值,如果按顺序插入,应该是最有效的。