c++ - para - secuencias numericas ejercicios

Inicializar de manera eficiente std:: set con una secuencia de números

Question

Un enfoque obvio (¿ingenuo?) Sería:

std::set<int> s;
for (int i = 0; i < SIZE; ++i) {
s.insert(i);
}

Es razonablemente legible, pero por lo que entiendo, no es óptimo ya que implica buscar repetidamente la posición de inserción y no aprovecha el hecho de que la secuencia de entrada ya está ordenada.

¿Hay alguna manera más elegante / eficiente (o de hecho) de inicializar un std::set con una secuencia de números?

O, de forma más genérica, ¿cómo se puede insertar eficientemente una lista ordenada de entradas en una colección?

Actualizar:

Al revisar los documentos, acabo de notar que el constructor que acepta un iterador indica la posición para la inserción:

iterator insert ( iterator position, const value_type& x );

Lo que significa que esto sería más eficiente:

std::set<int> s;
std::set<int>::iterator it = s.begin();
for (int i = 0; i < SIZE; ++i) {
it = s.insert(it, i);
}

Eso se ve razonablemente, pero todavía estoy abierto a más sugerencias.

Answer 1

Bueno, puedes usar la versión de insert() de set<> en la que puedes proporcionar la posición como pista donde el elemento podría insertarse.

iterator insert ( iterator position, const value_type& x );

Complejidad: esta versión es logarítmica en general, pero se mantiene constante si se inserta x justo después del elemento apuntado por posición.

Answer 2

El iterador derecho para usar como pista ha cambiado entre C ++ 03 y C ++ 11. Con C ++ 03, desea utilizar la posición del elemento anterior (tal como lo han mostrado usted y la mayoría de las respuestas).

En C ++ 11, quiere usar el iterador para el elemento inmediatamente después del que está por insertar. Cuando insertas en orden, esto hace las cosas un poco más simples: siempre usas your_container.end() :

std::set<int> s;
for (int i = 0; i < SIZE; ++i)
s.insert(s.end(), i);

Por supuesto, puede usar un algoritmo (p. Ej., std::iota ) o un iterador (por ej., boost::counting_iterator , como @pmr ya mencionado) para generar sus valores, pero en lo que respecta a la inserción en sí, para una corriente implementación que desea utilizar .end() como la sugerencia, en lugar del iterador devuelto por la inserción anterior.

Answer 3

Lo más lindo sería:

#include <set>
#include <boost/iterator/counting_iterator.hpp>
int main()
{
const int SIZE = 100;
std::set<int> s(boost::counting_iterator<int>(0),
boost::counting_iterator<int>(SIZE));
return 0;
}

Si busca la eficiencia en bruto, puede ser útil usar la versión de inserción sugerida:

const int SIZE = 100;
std::set<int> s;
auto hint = s.begin();
for(int i = 0; i < SIZE; ++i)
hint = s.insert(hint, i);

Ser capaz de declarar hint junto con el contador sería bueno y nos daría un alcance limpio, pero esto requiere struct piratería que me parece un poco ofuscante.

std::set<int> s;
for(struct {int i; std::set<int>::iterator hint;}
st = {0, s.begin()};
st.i < SIZE; ++(st.i))
st.hint = s.insert(st.hint, st.i);

Answer 4

#include <algorithm>
#include <set>
#include <iterator>
int main()
{
std::set<int> s;
int i = 0;
std::generate_n(std::inserter(s, s.begin()), 10, [&i](){ return i++; });
}

Esto es (creo) equivalente a su segunda versión, pero en mi humilde opinión se ve mucho mejor.

La versión C ++ 03 sería:

struct inc {
static int i;
explicit inc(int i_) { i = i_; }
int operator()() { return i++; }
};
int inc::i = 0;
int main()
{
std::set<int> s;
std::generate_n(std::inserter(s, s.end()), SIZE, inc(0));
}