gpt4 book ai didi

c++ - 带有 set 的 std::inserter - 插入到 begin() 或 end()?

转载 作者:IT老高 更新时间:2023-10-28 22:05:26 34 4
gpt4 key购买 nike

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

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() 处插入每个元素时解释这一点,我似乎不会获得最佳算法性能。这可以做得更好吗?

最佳答案

我选择 Alexander Gessler 的答案作为“正确”答案,因为它引导我找到了这个解决方案,我认为无论如何我都会发布。我写了一个 last_inserter(),它保证插入位置始终是最后一个元素的迭代器(如果为空,则为 begin()),因为 set 想要一个元素的迭代器 preceding 实际插入位置以获得最佳性能(所以不是 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);
}

关于c++ - 带有 set 的 std::inserter - 插入到 begin() 或 end()?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3609941/

34 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com