std :: inserter with set - insert to 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::inserterout пуст, поэтому out.begin() == out.end(), поэтому я не вижу, имеет значение, укажу ли я out.begin() или out.end() в качестве подсказки. Однако, если это интерпретируется при вставке каждого элемента в begin(), похоже, что я бы не получил оптимальную алгоритмическую производительность. Можно ли это сделать лучше?

Answer 1

Вы можете использовать пользовательский функтор вместо std::inserter и переадресовать out.end() каждый раз, когда вставлен новый элемент.

В качестве альтернативы, если ваши значения отсортированы по убыванию, out.begin() будет в порядке.

Answer 2

Я выбрал ответ Александра Гесслера как «правильный» ответ, потому что он привел меня к этому решению, которое, как я думал, я опубликую в любом случае. Я написал last_inserter(), что гарантирует, что позиция вставки всегда является итератором для последнего элемента (или begin(), если она пуста), потому что set хочет, чтобы итератор с элементом , предшествующим, фактическую позицию вставки для лучшей производительности (так not 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 

Это гарантирует, что вставка подсказка всегда итератор для последнего элемента, мы надеюсь, обеспечивая производительность лучшего случая при использовании итератора вывода к набор с отсортированным диапазоном, как указано выше.

Ниже приводится моя реализация. Я думаю, что это платформа, специфичная для реализации STL Visual C++ 2010, потому что она в значительной степени основана на существующем 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 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. Поэтому он всегда будет указывать на одно значение, которое вы только что вставили, и если вы вставляете его в порядок, должно быть оптимально эффективным.