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