c++ - 避免映射键的重复存储

Question

假设我有一个std::map<std::string, T>（或unordered_map）并且我想从迭代器/引用/指针访问内容的密钥。

有没有办法做到这一点而没有两个std::string密钥副本（一个由地图拥有，一个在内容对象内）？一个可以参考另一个吗？

Answer 1

你会考虑使用 boost::bimap 吗？下面是一个简单的例子：

#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 2

他们之所以这样做，是因为它很危险。您必须保证所有std::string被键控的成员都不会改变值，否则整个地图将失效。有趣的是，想到的第一个解决方案看起来非常骇人，看起来像 UB，但我相信我非常小心地避开了 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");
}

我希望很清楚，这在 UB 附近太疯狂了，非常不推荐。基本上，在插入/查找期间，键指向您的临时对象或输入字符串，然后一旦插入/找到对象，键就会更改为指向字符串成员中包含的值，并且只要您永远不会做任何会使.c_str()任何包含person对象的返回值无效的事情，一切都几乎无法正常工作。我认为。

Answer 3

为什么不创建两个对象：

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

T 必须包含指向 std::string 的指针，并且 yourMap 需要自定义比较器。此外，您可以将所有这些包装在某个类中。

Answer 4

两者都可以是对相同值的引用。例如：

#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);
}