Wie verringere ich die Anzahl eines Elements in einem Multiset in C++?

Question

Ich benutze eine Multi-Menge in C++, die ich glaube ein Element und die entsprechende Anzahl von es speichert, wenn es eingefügt wird.

Hier wird, wenn ich ein Element gelöscht werden soll, ich möchte nur um 1 die Zählung dieses Elements in der Menge zu verringern, bis es größer als 0

ist

Beispiel C++ Code:

multiset<int>mset; 
    mset.insert(2); 
    mset.insert(2); 
    printf("%d ",mset.count(2)); //this returns 2 
    // here I need an O(1) constant time function (in-built or whatever) 
    // to decrease the count of 2 in the set without deleting it 
    // Remember constant time only 

     -> Function and its specifications 

    printf("%d ",mset.count(2)); // it should print 1 now . 

Gibt es eine Möglichkeit, das zu erreichen, oder sollte ich gehen, indem ich das lösche und das Element 2 mit den erforderlichen (count-1) Zeiten einfüge?

Answer 1

... Ich bin mit einem Multi-Set in C++, die ein Element und die jeweilige Anzahl der speichert ...

Nein, Sie nicht sind. Sie verwenden ein Multi-Set, das n Kopien eines Werts speichert, der n mal eingefügt wurde.

Wenn Sie einen Wert für eine Zählung speichern möchten, verwenden Sie einen assoziativen Container wie std::map<int, int> und verwenden Sie map[X]++, um die Anzahl der Xs zu erhöhen.

... Ich brauche einen O (1) konstante Zeitfunktion ... die Zählung zu verringern ...

Sowohl map und set haben O (log N) Komplexität nur zu Fund das Element, das Sie ändern möchten, so ist dies bei ihnen unmöglich. Verwenden Sie std::unordered_map/set, um O (1) -Komplexität zu erhalten.

... Ich möchte nur die Zählung dieses Elements in dem Satz von 1 zu verringern, bis es ist> 0

Ich bin mir nicht sicher, was das bedeutet.

• mit einem Satz:

  • alle Kopien eines Elements aus dem Satz zu entfernen, equal_range verwenden, um einen Bereich (Paar von Iteratoren) zu bekommen, und löscht dann diesen Bereich
  • Um alle Kopien in einem nicht leeren Bereich zu entfernen, erhöhen Sie einfach den ersten Iterator im Paar und prüfen Sie, ob der zweite Iterator immer noch nicht gleich ist, bevor Sie den neuen Bereich löschen.

  diese beide einen O (log N) lookup (equal_range) Schritt durch eine lineare Zeitlöschschritt (obwohl es linear mit der Anzahl von Elementen mit dem gleichen Schlüssel haben, nicht N ist).

• mit einer Karte:

  • die Zählung von einer Karte zu entfernen, löschen Sie einfach den Schlüssel
  • die Zählung auf eins zu setzen, verwenden Sie einfach map[key]=1;

  beides haben ein O (log N) Lookup gefolgt von einem Konstant-Zeit Löschen

• mit einer ungeordneten Karte ... für Ihre Zwecke ist es identisch mit der obigen Karte, außer mit O (1) com Plexität.

Hier ist ein kleines Beispiel mit unordered_map:

template <typename Key> 
class Counter { 
    std::unordered_map<Key, unsigned> count_; 
public: 
    int inc(Key k, unsigned delta = 1) { 
     auto result = count_.emplace(k, delta); 
     if (result.second) { 
      return delta; 
     } else { 
      unsigned& current = result.first->second; 
      current += delta; 
      return current; 
     } 
    } 
    unsigned dec(Key k, unsigned delta = 1) { 
     auto iter = count_.find(k); 
     if (iter == count_.end()) return 0; 
     unsigned& current = iter->second; 
     if (current > delta) { 
      current -= delta; 
      return current; 
     } 
     // else current <= delta means zero 
     count_.erase(iter); 
     return 0; 
    } 
    unsigned get(Key k) const { 
     auto iter = count_.find(k); 
     if (iter == count_.end()) return 0; 
     return iter->second; 
    } 
}; 

und es verwenden, etwa so:

int main() { 
    Counter<int> c; 
    // test increment 
    assert(c.inc(1) == 1); 
    assert(c.inc(2) == 1); 
    assert(c.inc(2) == 2); 
    // test lookup 
    assert(c.get(0) == 0); 
    assert(c.get(1) == 1); 
    // test simple decrement 
    assert(c.get(2) == 2); 
    assert(c.dec(2) == 1); 
    assert(c.get(2) == 1); 
    // test erase and underflow 
    assert(c.dec(2) == 0); 
    assert(c.dec(2) == 0); 
    assert(c.dec(1, 42) == 0); 
}