Gibt es eine Möglichkeit zum begrenzen der Größe einer STL-Map?

Ich umsetzen will, eine Art lookup-Tabelle in C++, der als ein cache. Es soll zu emulieren, ein Stück hardware, die ich bin, zu simulieren.

Die Tasten sind nicht ganzzahlig, so ich raten bin, ein hash ist in Ordnung. Ich habe nicht die Absicht, zu erfinden das Rad, so dass ich verwenden möchten std::map für diese (auch wenn Vorschläge für alternativen sind willkommen).

Die Frage ist, gibt es eine Möglichkeit zur Begrenzung der Größe der hash zu emulieren, die Tatsache, dass meine hardware ist von endlicher Größe? Ich würde erwarten, dass der hash ist einfügen - Methode eine Fehlermeldung zurück oder werfen eine Ausnahme, wenn das limit erreicht ist.

Wenn es keine solche Möglichkeit, ich werde einfach überprüfen Sie Ihre Größe bevor Sie versuchen, Sie zu legen, aber das scheint wie eine unelegant Weg, es zu tun.

Was Sie tun können, ist zu werfen bad_alloc, und das kann getan werden, durch die Umsetzung Ihrer eigenen allocator. Hier ist alles, was Sie brauchen: stackoverflow.com/questions/1591591/...
Eine Karte ist ein Baum, nicht eine hash-Tabelle Struktur. Es wird für lookups, aber die Suche in O(log N) (im Vergleich zu O(1) für eine optimale hash -)
Eine Karte umgesetzt werden können, doch der Autor wählte, so lange, wie die Umsetzung erfüllt die STL Komplexität Anforderungen für den Typ. Es ist am besten, nicht vorstellen, eine gegebene STL-Typ implementiert, die in einer bestimmten Art und Weise - die Komplexität der Anforderungen sind für alle garantiert.
Ich weiß, dass der standard verlangt nicht eine konkrete Datenstruktur, sondern die Anforderungen in der Zeit die Komplexität in der Bemerkung halten: lookup-Operationen in einer map sind O(log N) im standard. Es ist auch eine Tatsache, dass alle vorhandenen STL-Implementierungen verwenden Sie Bäume, die intern für Karten (also auch wenn aus theoretischer Sicht die Implikation map => Baum nicht halten, aus einer pragmatischen Sicht ist es nicht). Ein Teil der Grund ist, dass es schwer ist zu kommen mit eine andere Datenstruktur, die alle Anforderungen in allen Operationen, die der standard macht halten.
Der Namensraum "std" nicht "stl", so habe ich Sie bearbeitet die Frage, zu sagen: "std::map" anstelle von "stl::map".
Eine hash-Tabelle erfordert, die Tasten sind hashable; Bäume benötigen, die Schlüssel sind bestellt. Der C++ - standard erfordert, dass std::map Tasten sind sortierbar, aber nicht verlangen, Sie hashable. Auch, itertion über eine std::map hat, Durchlaufen Sie alle Schlüssel in diesem genauen Reihenfolge Sortieren. Daher können wir sicher sagen, dass der standard nicht zulässt, dass std::map eine hashtable.

InformationsquelleAutor Nathan Fellman | 2010-04-26

c++map stl

10

Erste Sache ist, dass ein map Struktur, ist nicht eine hash table, sondern einen ausgeglichenen binären Baum. Dieses hat eine Auswirkung in der Suche mal O(log N) statt O(1) für eine optimale hash-Implementierung. Dies kann oder kann nicht beeinflussen, dein problem (wenn die Anzahl der tatsächlichen Schlüssel und Operationen ist klein, kann es ausreichen, aber die emulation der cache kann irgendwie suboptimal.

Die einfachste Lösung, die Sie tun können, ist die Kapselung der eigentlichen Daten-Struktur in einer Klasse, die prüft, die Größe in jedem einfügen (Größe lookups sollte umgesetzt werden in konstanter Zeit in allen STL-Implementierungen), und schlägt fehl, wenn Sie versuchen, hinzufügen zu viele Elemente.
```
class cache {
public:
   static const int max_size = 100;
   typedef std::map<key_t, value_t> cache_map_t;
   void add( key_t key, value_t value ) {
      cache_map_t::const_iterator it = m_table.find( key );
      if ( it != m_table.end() && m_table.size() == max_size ) { 
         //handle error, throw exception...
      } else {
         m_table.insert( it, std::make_pair(key,value) );
      }
   }
private:
   cache_map_t m_table;
};
//Don't forget, in just one translation unit:
const int cache::max_size;
```
- Die details der Implementierung eines bestimmten std::map sind außerhalb des Bereichs der C++ - Spezifikation. Es gibt keine Garantie, eine Karte ist ein Baum.
- stimmt, aber die Komplexität der Anforderungen, die für std::map in den standard-don ' T lassen Sie viel Wahl für die Umsetzung. Ich fordere Sie auf, finden eine standard-konforme std::map-Implementierung, die nicht ein Baum 🙂
- Habe ich bereits beantwortet dem entspricht die Bemerkung in der Frage. Nehmen Sie alle Anforderungen aus der Norm und versuchen, sich mit einer anderen Implementierung (d.h. umzusetzen versuchen einem ständig wachsenden Karte, für die Insertionen nehmen O(log N) mit einem hash) oder alternativ, erwähnen, einer STL-Implementierung für die Karten sind nicht ausbalanciert Bäume.
- Soweit ich weiß, nur ein Baum oder skip-Liste erfüllen können, die Einschränkungen der standard setzt auf einen map/set. In jedem Fall ist es nicht - hash-map. (Und war es immer ein Baum sein.)
InformationsquelleAutor David Rodríguez - dribeas
4

Gibt es keine Möglichkeit "automatisch" beschränken Sie die Größe eines std::map einfach, da eine "limited std::map" wäre das nicht eine std::map mehr.

Wickeln Sie die std::map in einer Klasse von Ihrer eigenen, die prüft nur die Größe der std::map gegen eine Konstante vor dem einsetzen, und tut, was auch immer Sie wollen in dem Fall die maximale Größe erreicht wurde.

InformationsquelleAutor Daniel Daranas
2

Wenn Sie implementieren LRU-caches oder ähnliches, die ich gefunden habe, boost::bimap von unschätzbarem Wert sein. Verwenden Sie index, um die primäre "Objekt-ID" - Taste (die eine effiziente vector-Ansicht, wenn Sie eine einfache Aufzählung von Objekten), und die anderen index eine geordnete Zeitstempel.

InformationsquelleAutor timday

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.