STL + Conjunto ordenado + sin duplicados

Question

Necesito tener un conjunto ordenado de valores sin duplicados. Entonces, ¿cuál es el método más rápido/mejor:

1 - Cree un vector, ordénelo y elimine los duplicados? 2 - ¿Utiliza un tipo de vector "ordenado" (si existe)?

¿Cuál puede ser el más eficiente?

Answer 1

Usar std :: set. Está ordenado y no permite duplicados.

El único inconveniente es que no se obtiene acceso aleatorio a los elementos aunque esto no se especificó como un requisito.

Answer 2

¿Por qué no usaría un std::set?

Answer 3

Eso depende de la eficiencia que desee. Si desea algo que sea "simplemente rápido", use std :: set <> (como ya se sugirieron otros).

Sin embargo, si necesita coherencia de chaché o mantener las cosas en un vector (memoria alineada garantizada) en lugar de un conjunto (nada garantizado, implementado como un árbol si no recuerdo mal) tendrá que usar directamente std: : vector combinado con algunos algoritmos estándar que suponen que el contenedor que proporciona ya está ordenado (y luego realiza la comprobación más rápido), como std::binary_search().

Answer 4

Si va a cargar la lista una vez y luego la usa varias veces, usar std :: vector en lugar de std :: set probablemente sea más eficiente en el uso de la memoria y lo itere.

Si va a agregar y eliminar elementos continuamente, definitivamente debe usar std :: set.

Para uso general use std :: set porque es menos trabajo (construir el vector requiere que ordene y elimine duplicados después de que haya terminado de agregar todos los elementos), a menos que tenga una necesidad particular de eficiencia en poca memoria- uso o algún otro golpe de rendimiento que indique que se requiere un vector.

Answer 5

Insertar en un conjunto lleva el registro (n). Y el género es gratis.

Insertar en un vector (push_back) lleva un tiempo constante. Ordenar un vector toma n * log (n). Pero aún necesita eliminar duplicados.

Si inserta de una vez y luego ordena, también puede considerar el vector. Si inserta con frecuencia el conjunto es el correcto.

Answer 6

La eficiencia dependerá de la proporción de inserciones/accesos que tenga (es decir, el número de veces que necesitará ordenar su vector). Si el rendimiento es realmente importante allí, le sugiero que pruebe ambos enfoques y use el más rápido para un caso real de uso de la aplicación.

Nota: std::set no es un vector ordenado porque no es contiguo en la memoria (es un árbol). El "vector ordenado" que desea es un montón sobre std::vector. Ver: http://stdcxx.apache.org/doc/stdlibug/14-7.html.

Answer 7

Siempre hay Loki::AssocVector

De lo contrario se puede rodar fácilmente su propia:

• utilizar un std::vector o std::deque como el contenedor de base
• uso lower_bound/upper_bound/equal_range y binary_search algoritmos genéricos para buscar un objeto
• también inplace_merge es genial cuando usted ya sabe que el valor no está presente

Pero, en realidad, utiliza un std::set :)

Answer 8

probar este en su .h o .hpp:

struct TestWithTime 
{ 
    TestWithTime(unsigned long long timeSecs) : m_timeSecs(timeSecs) {} 

    unsigned long long m_timeSecs; 
} 

struct OrderedByTime 
{ 
    bool operator() (const TestWithTime* first, const TestWithTime* second) const 
    { 
     // Important: if the time is equal 
     if (first->m_timeSecs == second->m_timeSecs) 
     { 
      // then compare the pointers 
      return first < second; 
     } 
     return first->m_timeSecs < second->m_timeSecs; 
    } 
}; 

typedef std::set<TestWithTime*, OrderedByTime> OrderedDataByTime; 

Ahora usted puede utilizar su OrderedDataByTime establecer !!