Liste mit einzigartigen Elementen

Ich brauche einen container, wo:

  • wenn ich ein neues element hinzuzufügen, der noch nicht existiert, wird es Hinzugefügt, um die Spitze der Liste
  • wenn ich ein element, das schon existiert, ist nicht Hinzugefügt, und ich bekomme ich den index in der Liste
  • nachdem das element eingefügt wird, es hat immer den gleichen index, und es kann zugegriffen werden über diesen index

std::set allein ist nicht ausreichend, da ich keinen Zugriff auf die Elemente mit [index]. std::list keines von beiden, denn es speichert nicht nur einzigartige Elemente.

Habe ich eine gemischte Lösung mit list und map aber vielleicht gibt es einige standard, generische Vorlage für?

Möchte ich nicht verwenden, zu steigern. Aufrufen list::unique nach jedem einfügen ist auch keine Lösung.

Wie über Ihre eigenen Rollen? Haben Sie versucht,? Klingt wie ein sehr dünner wrapper über list...
Die Umsetzung dieser mit list wäre nicht gut; die erste Kollision-Erkennung wäre O(n), als würden die suchen Dinge, die durch den index.
list und anzeigen, wenn Sie Häufig fügen Sie vorhandene Elemente.
Ich weiß, Sie wollen nicht, um die Verwendung von Boost, aber das ist effektiv das, was Steigern.bimap hat!
Es sind effektiv 2 Tasten (das element selbst, und die zugeordneten integer-index, der Ihr zugewiesen wurde).

InformationsquelleAutor Jakub M. | 2012-04-20

  1. 3

    Wenn Sie nur ein std::list (oder std::vector, für diese Angelegenheit),
    du wirst nicht um einen linearen Suche, wenn Sie nicht wollen
    vermeiden Sie doppelt, aber Sie wollen, um die original-Reihenfolge. Eine einfache
    std::vector basierte Lösung könnte sein:

    int
createIndex( std::vector<T>& references, T const& newValue )
{
    int results = std::find( references.begin(), references.end(), newValue )
                                    - references.begin();
    if ( results == references.size() ) {
        references.push_back( newValue );
    }
    return results;
}

    Alternativ können Sie std::map:

    int
createIndex( std::map<T, int>& references, T const& newValue )
{
    st::map<T, int>::iterator results = references.find( newValue );
    if ( results == references.end() ) {
        results = references.insert(
                    std::make_pair( newValue, references.size() ) ).first;
    }
    return results->second;
}

    (Das setzt Voraus, dass T unterstützt <. Wenn nicht, müssen Sie zum herstellen
    eine Bestell-Kriterien sind. Oder verwenden Sie unordered_map " und definieren Sie einen hash-code für
    es.)

    InformationsquelleAutor James Kanze

Schreibe einen Kommentar