Wie füge ich einen neuen Wert in einen Satz ein und lösche gleichzeitig einen anderen?

Question

Jeder Satz enthält Elemente in einer bestimmten Reihenfolge. Ich möchte eine Schranke für die Größe eines Satzes angeben und automatisch das letzte Element zu löschen, wenn ein neues streng kleiner (in Bezug auf die Reihenfolge) eingesetzt ist und die angegebene Größe ist bereits erreicht.

Natürlich könnte ich so etwas wie die folgenden tun:

class bounded_set 
{ 
private: 
    using set = std::set<Key, Compare, Allocator>; 
    using iterator = typename set::iterator; 

public: 
    bounded_set(std::size_t size) 
     : m_size(size) 
    { } 

    std::pair<iterator, bool> insert(Key const& value) 
    { 
     if (m_set.size() < m_size) 
      return m_set.insert(value); 

     auto last = std::prev(m_set.end()); 
     if (Compare()(value, *last)) 
     { 
      m_set.erase(last); 
      return m_set.insert(value); 
     } 
     return std::make_pair(last, false); 
    } 

private: 
    set m_set; 
    std::size_t m_size; 
}; 

Neben der Tatsache, dass bounded_set ist nicht der beste Name (seit begrenzt Behälter eine bekannte Sache in der Welt der gleichzeitigen Programmierung sind), Mache ich mir Sorgen über die Speicherzuweisung in dieser Implementierung. Höchstwahrscheinlich wird zuerst der von last verwendete Speicherplatz freigegeben. Aber sofort danach muss neuer Speicher für value reserviert werden.

Was ich wirklich tun möchte, ist die Verwendung des Speichers für last zugewiesen und kopieren Sie über die Daten für value an diesen Ort, unter Beibehaltung der Reihenfolge.

Answer 1

Wenn ich Ihre Fragen richtig zu verstehen, je nachdem, wie die zugrunde liegenden Datenstruktur arbeitet, ist das nicht unbedingt möglich sein würde, ohne dass Sie eine benutzerdefinierte Speicherzuordner schreiben oder ein aus einer Bibliothek verwenden. Zum Beispiel verwendet std::set einen Rot-Schwarz-Baum als zugrundeliegende Datenstruktur. Somit sind die Speicherstelle der Knoten und die relationalen Zeiger zu und von diesen Knoten intrinsisch an die Gesamtordnung des Baumes gebunden. Sie können den Speicher von einem Knoten, der der "kleinste" Wert ist, nicht erneut verwenden und einen anderen Wert dort platzieren, der kein neuer, vollständig geordneter "geringster" Wert ist, ohne auch alle Zeiger zu diesem Knoten neu zu sortieren an der richtigen Stelle im Baum für den Wert dieses Knotens.

Wenn Sie immer noch Bedenken über die Speicherauslastung und wollen mit der STL, anstatt std::set bleiben, sollten Sie vielleicht in eine Prioritätswarteschlange fester Länge oder etwas dieser Art, die einen Array-basierten Heap als verwendet die zugrundeliegende Datenstruktur, so dass der Speicher nicht ständig für neue Knoten zugewiesen und neu zugewiesen wird.

Answer 2

Ich sehe ein paar Möglichkeiten für Sie, und eine verlorene Gelegenheit, durch den Ausschuss Standards, die leicht zu lösen Ihr Problem haben würde.

N3586 eine Lösung für Ihr Problem vorgeschlagen.

std::pair<iterator, bool> insert(Key const& value) 
{ 
    if (m_set.size() < m_size) 
     return m_set.insert(value); 

    auto last = std::prev(m_set.end()); 
    if (Compare()(value, *last)) 
    { 
     auto temp = m_set.remove(last); 
     *temp = value; 
     return m_set.insert(temp); 
    } 
    return std::make_pair(last, false); 
} 

In diesem hypothetischen Rewrite ist temp ein node_ptr die value_type an den Knoten der nicht konstanten Zugriff erlaubt. Sie können den Knoten entfernen, in ihn schreiben und ihn erneut einfügen, ohne dass Knoten zugeordnet werden müssen.

Der Ausschuss lehnte dankend diesen Vorschlag.

Ein benutzerdefinierter Allokator für std::set könnte den Trick in einer weniger eleganten Art und Weise tun. Ein solcher Allokator würde einfach Knoten zwischenspeichern, und Ihr vorhandenes insert wird einfach funktionieren. Ein kleiner Nachteil dieses Ansatzes besteht darin, dass der benutzerdefinierte Zuordner zwar die Freigabe Ihres Knotens verhindert, aber nicht verhindert, dass Ihre Key zerstört und dann konstruiert wird, wenn Sie sie ändern. Einige Arten sind in der Zuordnung effizienter als in einem Zerstörungs-Konstruktions-Zyklus. Und manchmal kann ersteres noexcept sein, während letzteres nicht sein kann.

Insgesamt sehe ich die benutzerdefinierte allocator Ansatz als letztes Mittel. Du kannst es zum Laufen bringen.Aber es braucht etwas sorgfältig geplanten und nicht intuitiven Code.

Die Verwendung von push_heap, pop_heap kommt in den Sinn. Die Verwendung ist jedoch umständlich, wenn Sie wirklich einen Iterator für das eingefügte oder gleiche zurückgegebene Element benötigen. Wenn Sie mit dem Rückgabetyp void umgehen kann, könnte es wie folgt aussehen:

void insert(Key const& value) 
{ 
    if (m_set.size() < m_size) 
    { 
     m_set.push_back(value); 
     std::push_heap(m_set.begin(), m_set.end(), Compare{}); 
    } 

    if (Compare()(value, m_set.front())) 
    { 
     std::pop_heap(m_set.begin(), m_set.end(), Compare{}); 
     m_set.back() = value; 
     std::push_heap(m_set.begin(), m_set.end(), Compare{}); 
    } 
} 

Aber es ist umständlich den Heap für den neu eingefügten Wert zu suchen, und push_heap bietet nicht diese Informationen.

Noch eine weitere Option ist eine sortierte Vektor + Einfügesortierung. Sie müssen die Insertion selbst schreiben, aber das ist eine relativ kleine Programmieraufgabe. Der Grund für das Einfügen von Sortierung ist, dass Sie immer ein sortiertes Array mit Ausnahme des letzten Elements sortieren werden. Und die Sortierung ist optimal für diesen Job.

Keine dieser Lösungen ist perfekt, und keine außer N3586 bieten alles, was eine Lösung "out of the box" nähert, d. H. Eine, die nicht mehr als eine Handvoll Codezeilen benötigt. Und N3586 existiert nicht. Wenn Sie der Ansicht sind, dass es existieren sollte, wenden Sie sich an Ihren Vertreter der nationalen C++ - Vertretung und teilen Sie es ihm mit. Oder engagieren Sie sich selbst im C++ - Komitee und setzen Sie sich dafür ein.