wake-up-neo.net

Was ist der schnellste Weg, um einen Schlüssel eines Elements in std :: map zu ändern?

Ich verstehe die Gründe, warum man das nicht einfach machen kann (Rebalancing und so):

iterator i = m.find(33);

if (i != m.end())
  i->first = 22;

Aber bis jetzt ist die einzige Möglichkeit (ich weiß ungefähr), den Schlüssel zu ändern, den Knoten aus dem Baum zu entfernen und dann den Wert mit einem anderen Schlüssel zurückzusetzen:

iterator i = m.find(33);

if (i != m.end())
{
  value = i->second;
  m.erase(i);
  m[22] = value;
}

Dies erscheint mir aus mehreren Gründen eher ineffizient:

  1. durchquert den Baum dreimal (+ Kontostand) anstatt zweimal (+ Kontostand)
  2. eine weitere unnötige Kopie des Wertes
  3. unnötige Freigabe und anschließende Neuzuweisung eines Knotens innerhalb des Baums

Ich finde die Zuteilung und die Aufhebung der Sperrung von diesen dreien am schlechtesten. Fehlt mir etwas oder gibt es einen effizienteren Weg, dies zu tun?

UPDATE: Ich denke, theoretisch sollte es möglich sein, daher denke ich nicht, dass das Ändern einer anderen Datenstruktur gerechtfertigt ist. Hier ist der Pseudo-Algorithmus, den ich mir vorstelle:

  1. finde den Knoten in der Baumstruktur, dessen Schlüssel ich ändern möchte.
  2. trennen, wenn vom Baum getrennt (nicht freigegeben)
  3. ausgleichen
  4. Ändern Sie den Schlüssel im abgelösten Knoten
  5. fügen Sie den Knoten wieder in den Baum ein
  6. ausgleichen
42
Peter Jankuliak

In C++ 17 können Sie mit der neuen Funktion map::extract den Schlüssel ändern.
Beispiel:

std::map<int, std::string> m{ {10, "potato"}, {1, "banana"} };
auto nodeHandler = m.extract(10);
nodeHandler.key() = 2;
m.insert(std::move(nodeHandler)); // { { 1, "banana" }, { 2, "potato" } }
21
21koizyd

Ich habe Ihren Algorithmus für die assoziativen Container vor etwa 18 Monaten hier vorgeschlagen:

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#839

Achten Sie auf den markierten Kommentar: [2009-09-19 Howard fügt hinzu:].

Zu dieser Zeit waren wir zu nahe an FDIS, um diese Änderung in Betracht zu ziehen. Ich finde es jedoch sehr nützlich (und Sie stimmen offenbar zu), und ich würde es gerne in TR2 einführen. Vielleicht können Sie helfen, indem Sie Ihren Vertreter der nationalen C++ - Stelle herausfinden und benachrichtigen, dass dies eine Funktion ist, die Sie gerne sehen würden.

Update

Es ist nicht sicher, aber ich denke, es gibt eine gute Chance, dass wir diese Funktion in C++ 17 sehen werden! :-)

28
Howard Hinnant

Sie können das Kopieren von value weglassen.

const int oldKey = 33;
const int newKey = 22;
const iterator it = m.find(oldKey);
if (it != m.end()) {
  // Swap value from oldKey to newKey, note that a default constructed value 
  // is created by operator[] if 'm' does not contain newKey.
  std::swap(m[newKey], it->second);
  // Erase old key-value from map
  m.erase(it);
}
23
Viktor Sehr

Schlüssel in STL-Karten müssen unveränderlich sein.

Anscheinend könnte eine andere Datenstruktur oder -struktur sinnvoller sein, wenn Sie auf der Schlüsselseite Ihrer Paarungen so viel Volatilität haben.

6
Joe

Du kannst nicht.

Wie Sie bemerkt haben, ist dies nicht möglich. Eine Map ist so organisiert, dass Sie den mit einem Schlüssel verknüpften Wert zwar effizient ändern können, jedoch nicht umgekehrt.

Sie haben einen Blick auf Boost.MultiIndex und insbesondere dessen Standard Container-Abschnitte emulieren . Boost.MultiIndex-Container bieten eine effiziente Aktualisierung.

5
Matthieu M.

Sie sollten die Zuteilung dem Zuteiler überlassen. :-)

Wie Sie sagen, wenn sich der Schlüssel ändert, kann es zu einer Neuausrichtung kommen. So funktioniert ein Baum. Vielleicht ist 22 der erste Knoten im Baum und 33 der letzte? Was wissen wir?

Wenn das Vermeiden von Zuordnungen wichtig ist, sollten Sie vielleicht einen Vektor oder einen Deque ausprobieren? Sie weisen größere Blöcke zu, so dass sie weniger Anrufe beim Zuweiser einsparen, aber möglicherweise Speicherplatz verschwenden. Alle Container haben ihre Kompromisse und es liegt an Ihnen, zu entscheiden, welcher der Hauptvorteile ist, die Sie in jedem Fall benötigen (vorausgesetzt, es spielt eine Rolle).

Für Abenteuerlustige:
Wenn Sie sicher sind, dass das Ändern des Schlüssels die Reihenfolge nicht beeinflusst, und Sie niemals einen Fehler machen, kann ein wenig const_cast würde Sie den Schlüssel trotzdem ändern.

1
Bo Persson

Wenn Sie wissen, dass der neue Schlüssel für die Kartenposition gültig ist (das Ändern der Reihenfolge ändert sich nicht), und Sie nicht die zusätzliche Arbeit durch Entfernen und Hinzufügen des Elements zur Karte wünschen, können Sie zum Ändern einen const_cast verwenden der Schlüssel, wie in unsafeUpdateMapKeyInPlace unten:

template <typename K, typename V, typename It>
bool isMapPositionValidForKey (const std::map<K, V>& m, It it, K key)
{
    if (it != m.begin() && std::prev (it)->first >= key)
        return false;
    ++it;
    return it == m.end() || it->first > key;
}

// Only for use when the key update doesn't change the map ordering
// (it is still greater than the previous key and lower than the next key).
template <typename K, typename V>
void unsafeUpdateMapKeyInPlace (const std::map<K, V>& m, typename std::map<K, V>::iterator& it, K newKey)
{
    assert (isMapPositionValidForKey (m, it, newKey));
    const_cast<K&> (it->first) = newKey;
}

Wenn Sie eine Lösung wünschen, die sich nur dann ändert, wenn sie gültig ist, und andernfalls die Kartenstruktur ändert:

template <typename K, typename V>
void updateMapKey (const std::map<K, V>& m, typename std::map<K, V>::iterator& it, K newKey)
{
    if (isMapPositionValidForKey (m, it, newKey))
    {
        unsafeUpdateMapKeyInPlace (m, it, newKey);
        return;
    }
    auto next = std::next (it);
    auto node = m.extract (it);
    node.key() = newKey;
    m.insert (next, std::move (node));
}
0
yairchu