2010-08-31 40 views
15

que tienen un código que se parece a esto:std :: inserter con set - insertar para begin() o end()?

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())); 

He leído inserciones se puede hacer en un tiempo constante amortizado si el valor que se inserta en el conjunto sigue inmediatamente el repetidor dado como un "toque". Obviamente, esto sería beneficioso al ejecutar la intersección establecida, especialmente porque todo lo que se está escribiendo en out ya está ordenado.

¿Cómo puedo garantizar este rendimiento óptimo? Al crear el std::inserter, out está vacío así que out.begin() == out.end() así que no puedo ver si hay alguna diferencia si especifico out.begin() o out.end() como sugerencia. Sin embargo, si esto se interpreta al insertar cada elemento en begin(), no parece que obtenga el rendimiento algorítmico óptimo. ¿Se puede hacer esto mejor?

+1

@Ahsleys: Al menos al seleccionar 'end' no pesimiza el algoritmo ya que no hay un elemento siguiente (lo que economiza una comparación). Sin embargo, me pregunto (como lo está) si el iterador que pasa evolucionará o se quedará bloqueado al principio/final. –

Respuesta

2

Puede utilizar un functor personalizado en lugar de std::inserter y volver a llamar al out.end() cada vez que se inserta un nuevo elemento.

Alternativamente, si sus valores se ordenan de forma descendente, out.begin() estará bien.

+0

Entonces, esencialmente, ¿escribo mi propio 'end_inserter' que siempre llama' end() 'al insertar? Voy a dar una oportunidad ... – AshleysBrain

+0

para un conjunto, los iteradores nunca se invalidan, a excepción de un elemento que se eliminó, por lo que no es necesario volver a llamar 'out.end()' cada vez, su otro La solución es correcta, sin embargo, para obtener la antes del final.Tenga en cuenta que para C++ 11, ha cambiado constante si pertenece justo antes de la sugerencia. – Jarryd

5

Elegí la respuesta de Alexander Gessler como la respuesta "correcta", porque me llevó a esta solución, que pensé que publicaría de todos modos. Escribí un last_inserter(), que garantiza que la posición de inserción siempre es un iterador del último elemento (o begin() si está vacío), porque set quiere un iterador para el elemento que precede a la posición de inserción real para obtener el mejor rendimiento (por lo no end() - eso sería uno después de la posición de inserción real).

El uso de acuerdo con el ejemplo original es la siguiente:

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 

Esto garantiza que la pista de inserción es siempre un iterador al último elemento, es de esperar que proporciona un rendimiento mejor de los casos cuando se utiliza un iterador de salida a una establecer con un rango ordenado, como arriba.

A continuación se muestra mi implementación. Creo que es una plataforma específica para la implementación de STL de Visual C++ 2010, porque se basa en gran medida en el existente insert_iterator, y solo puedo hacerlo funcionar derivando de std::_Outit. Si alguien sabe cómo hacer que este portátil, que me haga saber:

// 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); 
} 
1

Según 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; 
} 

Dónde iter señaló originalmente para el iterador que pasó a std::inserter. Por lo tanto, iter siempre apuntará a uno más allá del valor que acaba de insertar y si lo está insertando en orden, debe ser óptimamente eficiente.

+0

[cppreference] (http://en.cppreference.com/w/cpp/container/set/insert) también observa que los bucles que insertan elementos en orden (como lo hace la intersección de conjuntos) deben usar 'end' como sugerencia, como la inserción ocurrirá justo * antes de * la pista (que es constante desde C++ 11, mientras que antes tenía que ser * después de * la pista) – pascal

Cuestiones relacionadas