Vermeiden Sie doppelte Speicherung von Kartenschlüssel

Question

Nehmen wir an, ich habe eine std::map<std::string, T> (oder unordered_map) und ich möchte den Schlüssel von einem Iterator/Verweis/Zeiger auf den Inhalt zugreifen.

Gibt es eine Möglichkeit, dies zu tun, ohne zwei Kopien des Schlüssels std::string (einer im Besitz der Karte, einer innerhalb des Inhaltsobjekts)? Kann man sich auf den anderen beziehen?

Answer 1

Beide können eine Referenz auf den gleichen Wert sein. Zum Beispiel:

#include <stdio.h> 
#include <string> 
#include <map> 

struct xx { std::string mykey; int value; }; 

int main (int argc, char **argv) 
{ 
    std::string      key1("the-key"); 
    std::map<std::string, xx>  map; 

    map[key1].mykey = key1; 
    map[key1].value = 13; 

    std::string &lookup_key = map[key1].mykey; 

    printf("%d\n", map[lookup_key].value); 
} 

Answer 2

Warum Sie zwei Objekte nicht erstellen:

std::set<std::string> wordSet; 
std::map<std::string*, T> yourMap; 

T Zeiger enthalten muss std :: string und yourMap muss benutzerdefinierten Komparator. Zusätzlich können Sie alle diese in eine Klasse einbinden.

Answer 3

Würden Sie boost :: bimap verwenden? Unten ist ein einfaches Beispiel:

#include <boost/bimap.hpp> 
#include <string> 
struct Person 
{ 
    Person() 
    {} 
    Person(const std::string& f, const std::string& l, int a) : first(f), last(l), age(a) 
    {} 
    std::string first; 
    std::string last; 
    int age; 
}; 

bool operator <(const Person& lhs, const Person& rhs) 
{ 
    if(lhs.last < rhs.last) 
     return true; 
    return false; 
} 

std::ostream& operator << (std::ostream& os, const Person& p) 
{ 
    os << "First Name: " << p.first << " Last Name: " << p.last << " Age: " << p.age; 
    return os; 
} 

int main() 
{ 
    typedef boost::bimap<std::string, Person> people; 
    typedef people::value_type value; 

    people m; 
    m.insert(value("12345",Person("fred", "rabbit", 10))); 
    m.insert(value("67890",Person("benjamin", "bunny", 12))); 

    Person p = m.left.at("12345"); 
    std::cout << "Person with serial no. 12345 is: " << p << "\n"; 
    std::cout << "Serial number of " << p << " is: " << m.right.at(p) << "\n"; 

} 

Answer 4

Der Grund, warum sie dies hart gemacht haben, ist, weil es gefährlich ist. Sie müssen GARANTIEREN, dass keiner der std::string Mitglieder, von denen ein Schlüssel abgezogen wird, niemals den Wert ändert oder die gesamte Karte ungültig wird. Interessant, die erste Lösung, die in den Sinn kommt, erscheint wahnsinnig hackish, und sieht wie UB, aber ich glaube, dass ich sehr vorsichtig die UB.

struct key_type { 
    mutable const char* ptr;  
}; 
bool operator<(const key_type& lhs, const key_type& rhs) 
{return strcmp(lhs.ptr, rhs.ptr)<0;} 

struct person { 
    std::string name; 
    int age; 
}; 
person& people_map_get(std::map<key_type, person>& map, const char* name) { 
    auto it = map.insert(name, person{name}).first; //grab, possibly insert 
    if->first.ptr = it->second.name.c_str(); //in case of insert, fix ptr 
    return it->second; 
} 
person& people_map_assign(std::map<key_type, person>& map, person p) { 
    auto pair = map.insert(name, p); //grab, possibly insert 
    auto it = pair.first;  
    if (pair.second == false) 
     it->second = std::move(p); 
    if->first.ptr = it->second.name.c_str(); //ptr probably invalidated, so update it 
    return it->second; 
} 

int main() { 
    std::map<key_type, person> people; 
    people_map_assign(people, person{"ted"}); 
    person frank = people_map_get(people, "frank"); 
} 

Wie ich hoffe, ist klar, das ist verrückt der Nähe von UB und sehr viel nicht zu empfehlen. Während eines Einfüge-/Suchvorgangs zeigt der Schlüssel auf das temporäre Objekt oder die Eingabezeichenfolge, und sobald das Objekt eingefügt/gefunden wird, wird der Schlüssel so geändert, dass er auf den im Zeichenfolgenelement enthaltenen Wert zeigt, und solange Sie tun nie etwas, das würde den Rückgabewert von .c_str() auf jedem enthaltenen person Objekt ungültig machen, alles funktioniert nur knapp. Ich denke.