std :: inserter con set - insert to begin() o end()?

Question

ho qualche codice che assomiglia a questo:

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

ho inserti di lettura può essere fatto in tempo costante ammortizzato se il valore viene inserito al set segue immediatamente l'iteratore dato come un "suggerimento". Ciò sarebbe ovviamente utile quando si esegue l'intersezione impostata, soprattutto perché tutto ciò che viene scritto su out è già in ordine.

Come garantire questa prestazione ottimale? Quando si crea std::inserter, out è vuoto quindi out.begin() == out.end() quindi non riesco a vedere fa alcuna differenza se si specifica out.begin() o out.end() come suggerimento. Tuttavia, se questo viene interpretato all'inserimento di ogni elemento su begin(), non sembra che otterrei le prestazioni algoritmiche ottimali. Questo può essere fatto meglio?

Answer 1

È possibile utilizzare un functor personalizzato anziché std::inserter e richiamare out.end() ogni volta che viene inserito un nuovo elemento.

In alternativa, se i valori sono ordinati in modo discendente, out.begin() andrà bene.

Answer 2

Ho scelto la risposta di Alexander Gessler come risposta "corretta", perché mi ha portato a questa soluzione, che ho pensato di pubblicare comunque. Ho scritto un last_inserter(), che garantisce che la posizione di inserimento sia sempre un iteratore dell'ultimo elemento (o begin() se vuoto), perché set desidera un iteratore per l'elemento precedente la posizione di inserimento effettiva per la migliore prestazione (quindi non fine() - che sarebbe uno dopo la posizione di inserimento effettiva).

L'uso come nell'esempio originale è così:

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 

Ciò garantisce che il suggerimento inserto è sempre un iteratore all'ultimo elemento, fornendo spera prestazioni nel caso migliore quando si utilizza un iteratore uscita ad un impostato con un intervallo ordinato, come sopra.

Di seguito è la mia implementazione. Penso che sia una piattaforma specifica per l'implementazione STL di Visual C++ 2010, perché è basata pesantemente sul insert_iterator esistente, e posso solo farlo funzionare derivando da std::_Outit. Se qualcuno sa come fare questo portatile, fatemelo sapere:

// 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

Secondo 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; 
} 

Dove iter originariamente indicò l'iteratore avete passato a std::inserter. Quindi l'iter punta sempre a superare il valore appena inserito e se stai inserendo in ordine, dovrebbe essere ottimamente efficiente.