5

给定以下代码：

struct Item
{
    std::string name;
    int someInt;
    string someString;
    Item(const std::string& aName):name(aName){}
};
std::unordered_map<std::string, Item*> items;
Item* item = new Item("testitem");
items.insert(make_pair(item.name, item);

项目名称将在内存中存储两次——一次作为 Item 结构的一部分，一次作为映射条目的键。是否可以避免重复？对于大约 100M 的记录，这种开销变得巨大。

注意：我需要在 Item 结构中包含名称，因为我使用 hashmap 作为另一个 Item-s 容器的索引，并且我无法访问映射的键值。

4

5 回答 5

3

好的，既然你说你使用指针作为值，我特此让我的答案恢复活力。

有点hacky，但应该可以。基本上你使用指针和自定义散列函数

struct Item
{
    std::string name;
    int someInt;
    string someString;
    Item(const std::string& aName):name(aName){}

    struct name_hash  
    { 
       size_t operator() (std::string* name)
       {
           std::hash<std::string> h;
           return h(*name);
       }
    };
};
std::unordered_map<std::string*, Item*, Item::name_hash> items;
Item* item = new Item ("testitem");
items.insert(make_pair(&(item->name), item);
于 2012-11-29T09:35:45.377 回答
2

假设您用于存储项目的结构首先是一个简单的列表，您可以将其替换为多索引容器。

这些方面的东西（未经测试）应该满足您的要求：

typedef multi_index_container<
    Item,
    indexed_by<
        sequenced<>,
        hashed_unique<member<Item, std::string, &Item::name
    >
> itemContainer;

itemContainer items;

现在您可以按插入顺序访问项目，也可以按名称查找它们：

itemContainer::nth_index<0>::type & sequentialItems = items.get<O>();
// use sequentialItems as a regular std::list

itemContainer::nth_index<1>::type & associativeItems = items.get<1>();
// uses associativeItems as a regular std::unordered_set

根据您的需要，您也可以使用其他索引。

于 2012-11-29T10:17:08.943 回答
1

不要std::string name在结构中存储字段。无论如何，当您执行查找时，您已经知道名称字段。

于 2012-11-29T09:26:33.983 回答
1

不，没有。你可以：

  • 不要单独存放name和Item传递。
  • Create Item，ItemData除了Itemname 和
    • 派生Item自std::pair<std::string, ItemData>(=value_type的类型) 或
    • 使其可转换为该类型。
  • 使用对字符串的引用作为键。您应该能够用作键并为键和搜索std::reference_wrapper<const std::string>传递键。你可能需要专攻，但这应该很容易。std::cref(value.name)std::cref(std::string(whatever))std::hash<std::reference_wrapper<const std::string>>
  • 使用std::unordered_set，但它的缺点是查找会Item为查找创建虚拟对象。
    • 当您实际上具有Item *as 值类型时，您可以将名称移动到基类并使用多态性来避免该缺点。
  • 创建自定义哈希映射，例如使用Boost.Intrusive。
于 2012-11-29T09:34:11.287 回答
1

TL；DR如果您使用的是 libstdc++（与 gcc 一起提供），那么您已经可以了。

有3种方法，2种是“简单的”：

  • 将您的对象拆分为两个键/值，并停止重复值中的键
  • 将您的对象存储在 aunordered_set中

第三个更复杂，除非您的编译器提供：

  • 使用std::string引用计数的实现（例如 libstdc++ 的）

在这种情况下，当您将 a 复制std::string到另一个时，内部缓冲区的引用计数器会递增……仅此而已。复制被推迟到所有者之一请求修改的时间：写时复制。

于 2012-11-29T09:36:14.513 回答