La elección de un contenedor STL con singularidad y que mantiene la inserción de ordenar

Question

Soy incapaz de decidir qué contenedor STL a utilizar en el siguiente caso:

1. que quieren preservar el orden de inserción de los elementos
2. El los elementos en el contenedor deben ser únicos.

¿Hay alguna contenedor prefabricado disponible para esto? No quiero usar un vector y luego realizar un std::find antes de hacer un push_back cada vez.

Answer 1

Boost MultiIndex debería ser capaz de hacer exactamente lo que quiere - que sólo puede utilizar un índice secuenciados para obtener los requerimientos "ordenado por orden de inserción", y, o bien un índice hashed_unique o ordered_unique de satisfacer los requerimientos singularidad.

Answer 2

Puede haber una buena construida en forma de hacerlo, pero de una manera más sencilla es utilizar tanto un hash_map y una lista. Compruebe el hash_map antes de cada inserción, luego inserte en ambos. Querrás encapsular esto en una clase, probablemente.

Answer 3

implementar una clase de envoltura sobre el recipiente que elija (por ejemplo, lista, vector, deque), y volver a escribir los métodos de inserción/push_back para comprobar que el elemento insertado es único antes de insertar el elemento.

Por desgracia, no sé cualquier contenedor STL para que coincida con sus criterios.

Answer 4

Ningún contenedor biblioteca estándar le da lo que desea directamente. Comenzaría con un std :: vector y escribiría una función gratuita para hacer la inserción que hace el hallazgo y el push_back por usted. Si esto es suficiente, no avance más. Si tiene problemas de rendimiento, piense en una solución más complicada.

Answer 5

Como han dicho otros, ningún contenedor STL único puede hacer esto. Me gusta la respuesta de Neil Butterworth. Otra opción sería usar un conjunto y un vector. Cuando vaya a insertar, verifique si el elemento está en el conjunto. Si es así, no puede insertar porque eso violaría su requisito de exclusividad. Si no es así, agréguela al conjunto y luego insértela en el vector. Esto es fácil de implementar y se puede incluir en una sola clase. La compensación es una sobrecarga de memoria aumentada. Pero cambias eso para aumentar el tiempo de cálculo al hacer que te encuentres en el único vector. Todo depende de la cantidad de datos con los que esté trabajando en su dominio problemático y de sus limitaciones de tiempo y memoria (si corresponde).

Answer 6

Si ya tiene boost instalado, me gusta esa opción. De lo contrario, ¿por qué no utilizar una lista o vector y agregar una marca (find(k) == std::npos) en la inserción? Supongo que podría ser un poco lento en una lista verdaderamente grande, pero para la mayoría de los casos funcionaría bien.

Answer 7

Usted puede hacer esto:

• Crear una envoltura alrededor de la clase de elemento con dos miembros: su elemento, y un índice. Vamos a llamarlo 'InsertedElement'. El índice será el orden de inserción.

• Definir operador de comparación para esta clase, que sólo tiene en cuenta su elemento, pero no el índice. Esto asegurará la singularidad de los elementos, al recordar su orden de inserción.

• Ajustar un std :: set y un contador de inserción en otra clase.Luego, cuando desee insertar un nuevo elemento, ya sea:

• Ya existe, no hay nada que hacer.
• No: insertarlo en el mapa mientras que le da el índice máx + 1.

Algo así como:

class CMagicContainer 
{ 
    public: 
    std::set<InsertedElement> collection; 
    int indexGenerator; 

    ... 
}; 

Answer 8

Bueno, una vez tuve una situación similar. Una cosa que me vino a la mente fue '¿Puedo usar varias teclas'? Busqué en Google por un tiempo y encontré una muestra usando std :: set. Entonces, si no tiene acceso para impulsar (lo recomiendo, no tiene sentido reinventar la rueda); puedes probar algo como el siguiente ejemplo. Creo que puede usar la tecla secundaria como posición de inserción (autoincremento). Del ejemplo que encontré en internet; lo adapté para mis necesidades Esta es una versión modificada de la misma.

Cavaet: Está utilizando macros. Sé que son malvados en general, pero este uso es o.k. supongo.

#include <set> 
#include <functional> 
#include <iostream> 
#include <algorithm> 
#include <iterator> 
#include <string> 

#define MULTIKEYDEF(NAME,TYPE) \ 
    inline TYPE const & NAME() const { return d_##NAME; } \ 
    inline void NAME(TYPE const & t) { d_##NAME = t; } \ 
    TYPE d_##NAME; \ 
class T##NAME \ 
    : public std::unary_function<Tmultikey*,bool> { \ 
private: \ 
    TYPE d_compare; \ 
public: \ 
    T##NAME(TYPE t) : d_compare(t) {} \ 
    T##NAME(T##NAME const & self) \ 
    : d_compare(self.d_compare) {} \ 
    bool operator()(Tmultikey * mk) { \ 
    return d_compare == mk->##NAME(); \ 
    } \ 
    inline TYPE const& name() const { return d_compare; } \ 
    } 

class Tmultikey { 
public: 
    // Actual keys 
    // Can be accessed through d_primary and d_secondary, 
    // or primary() and secondary() 
    MULTIKEYDEF(primary , std::string); 
    MULTIKEYDEF(secondary, unsigned int); 
    // Mandatory 
    bool operator < (Tmultikey const& mk) const { 
     if(primary() < mk.primary()) return true; 
     else if(primary() == mk.primary()) { 
      return secondary() < mk.secondary(); 
     } 
     return false; 
    } 
    // Constructor 
    Tmultikey(std::string p, unsigned int s) 
     : d_primary(p), d_secondary(s) {} 

    // Eraser for std::set 
    template<typename Compare> 
     static void erase(std::set<Tmultikey> & c, Compare op) { 
      typename std::set<Tmultikey>::iterator pos = c.begin(); 
      while(pos != c.end()) { 
       if(op(&(*pos))) { 
        c.erase(pos++); 
       } else ++pos; 
      } 
     } 
     // Eraser for std::set 
     template<typename Compare> 
     static std::set<Tmultikey>::iterator find_ex(std::set<Tmultikey> & c, Compare op) { 
     typename std::set<Tmultikey>::iterator pos = c.begin(); 
     while(pos != c.end()) { 
      if(op(&(*pos))) { 
       break; 
      } else ++pos; 
     } 
     return pos; 
     } 
}; 

int main(int argc, char* argv[]) 
{ 
    std::set<Tmultikey> mkset; 

    mkset.insert(Tmultikey("1",5)); 
    mkset.insert(Tmultikey("6",4)); 
    mkset.insert(Tmultikey("3",7)); 
    mkset.insert(Tmultikey("1",6)); 

    std::set<Tmultikey>::iterator bg = mkset.begin(); 
    for (;bg != mkset.end(); ++bg) 
    { 
     std::cout<<(*bg).primary()<<std::endl; 
    } 

    Tmultikey::erase(mkset,Tmultikey::Tsecondary(4)); 
    //Tmultikey::erase(mkset,Tmultikey::Tprimary("1")); 

    std::cout<<"After erase ....\n"; 
    bg = mkset.begin(); 
    for (;bg != mkset.end(); ++bg) 
    { 
     std::cout<<(*bg).primary()<<std::endl; 
    } 
    bg = mkset.find(Tmultikey("3",7)); 
    if (bg != mkset.end()) 
    { 
     std::cout<<"Absolute Find:"<<(*bg).primary()<<" "<<(*bg).secondary()<<std::endl; 
    } 
    //bg = Tmultikey::find_ex(mkset,Tmultikey::Tprimary("1")); 
    bg = Tmultikey::find_ex(mkset,Tmultikey::Tsecondary(5)); 
    if (bg != mkset.end()) 
    { 
     std::cout<<"Partial Find:"<<(*bg).primary()<<" "<<(*bg).secondary()<<std::endl; 
    } 
    else { 
     std::cout<<"Partial Find: FAILED\n"; 
    } 

    return 0; 
} 

HTH,