c++ - example - std:: inserter with set-insert to begin() or end()?

tree set c++

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Hay alguna diferencia entre usar .begin () vs .end () para std :: inserter para std :: set? 2 respuestas

Tengo un código que se parece a esto:

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 que las inserciones se pueden hacer en tiempo constante amortizado si el valor que se inserta en el conjunto sigue inmediatamente al iterador dado como una "sugerencia". Obviamente, esto sería beneficioso cuando se ejecuta la intersección del conjunto, especialmente porque todo lo que se está escribiendo está ya en orden.

¿Cómo garantizo este óptimo rendimiento? Al crear el std::inserter , out está vacío, así que out.begin() == out.end() así que no veo ninguna diferencia si especifico out.begin() o out.end() como insinuación. Sin embargo, si esto se interpreta al insertar cada elemento en begin() , no parece que obtendría el rendimiento algorítmico óptimo. ¿Se puede hacer esto mejor?

Answer 1

De acuerdo a 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;
}

Donde iter originalmente señalaba el iterador que pasaste 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, debería ser óptimamente eficiente.

Answer 2

He elegido la respuesta de Alexander Gessler como la respuesta ''correcta'', porque me llevó a esta solución, que pensé que publicaría de todos modos. He escrito un last_inserter() , que garantiza que la posición de inserción siempre sea un iterador para el último elemento (o comience () si está vacío), porque set quiere un iterador para el elemento que precede a la posición de inserción real para un mejor desempeño (por lo tanto, no end () - sería uno después de la posición de inserción real).

El uso según el ejemplo original es así:

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 sugerencia de inserción es siempre un iterador para el último elemento, con la esperanza de proporcionar el mejor rendimiento al usar un iterador de salida para un conjunto con un rango ordenado, como se indicó anteriormente.

A continuación se muestra mi implementación. Creo que es una plataforma específica para la implementación STL de Visual C ++ 2010, porque se basa en gran medida en el insert_iterator existente, y solo puedo hacer que funcione derivando de std::_Outit . Si alguien sabe cómo hacer este portátil, hágamelo 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);
}

Answer 3

Podría usar un functor personalizado en lugar de std::inserter y re-call out.end() cada vez que se inserte un nuevo elemento.

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