在C++中使用连接键而不是嵌套Map Container的优点和缺点

Question

我有一个项目来研究用于存储数据的当前容器的替代方案,以使其更有效.

目前的设计涉及4个嵌套地图 map< string, map< string, map< int, map< string, string> > > >

让名称每个数据字段Company,Department,ID_of_employee,Name

此刻的时间复杂度检索给雇员的姓名Company,Dept,ID是Ø(日志ñ)和更精确地涉及3个查找.

现在的空间复杂性不是问题.

我最初的选择是以下:

• 使用嵌套对代表Company,Dept,Id然后用这个嵌套对作为关键地图.这似乎不容易阅读.
• 而不是嵌套对我想到使用一个tuple或一个struct基本上我读的并没有那么不同.在创建后new struct EmployeeKey,将包含字段Company,Dept,ID.我可以用它作为Key一个map.(我想我必须编写自定义比较和少于运算符).
• 使用级联的关键,从company+Dept+ID通过转换int到string和连接它们.然后将此密钥提供给amap<ConcatenatedKey, Data>
• 使用Boost.MultiIndex.即使这似乎是我放弃这个选项的最佳选择,因为我发现它有点复杂.

提供一些必要的信息.此Container通常用于检索最终的嵌套数据,这就是我使用连接键方法的结论.我的问题基本上是,使用这种串联字符串有什么警告吗？这是一个糟糕的设计还是我们应该避免的事情？

根据我的理解,这将改善查找时间,仍保持对数但执行一次而不是四次查找,因此它似乎是一种改进.

Answer 1

由于std::map<>是红黑树,它仍然是二叉树,因此与哈希映射相比,查找速度并不快 - 特别是如果条目数很大.

假设散列扩散良好,使用std::unordered_map<> (散列映射)将提供更好的性能.我推荐使用fnv或MurmurHash3,因为它们具有最好的值分布.

现在,说起嵌套容器-你应该永远,永远做这样的事!总体性能可能非常糟糕,内存使用肯定会非常大,因为它本质上是一个4维RB树:

让我们把它放到上下文中,你有20个公司,每个公司有5个部门,每个部门有12个EmployeeID,每个EmployeeID映射到一个地图<Name, some_string>(最后一点似乎有点多余,你不觉得吗？).

1. 每个Company叶子节点都是std :: map => 20 std :: map实例
2. 每个Department叶节点都是std :: map => 20 + 20*5 = 120 std :: map实例
3. 每个EmployeeID叶节点都是std :: map => 120 + 20*5*12 = 1320 std :: map实例
4. 每个Name叶子节点都是std :: map => 1320 + 20*5*12*1 = 2520 std :: map实例

所以你看,嵌套容器是非常危险的,因为即使使用一个小的数据集,你最终也会得到大量的容器实例.这具有可笑的糟糕性能,尤其是在对象被销毁或插入新元素时.

我的建议:使用与std :: unordered_map结合的EmployeeKey结构.这将为您提供良好的查找速度,并且只有一个std :: unordered_map实例.

struct EmployeeKey
{
    int         CompanyID;  // if you want speed, CompanyID is the way to go
    std::string Department;
    int         EmployeeID;
    std::string Name;

    inline bool operator==(const EmployeeKey& key) const {
        return CompanyID != key.CompanyID && ... /* etc */;
    }
};

template<> struct hash<EmployeeKey> {
    size_t operator()(const EmployeeKey& key) const {
        /* perform hash combine here */
    }
};

这应该足以让你开始.最终布局如下所示:

std::unordered_map<EmployeeKey, std::string> EmployeeData;
// usage:
auto it = EmployeeData.find(selectedEmployee);
if (it != EmployeeData.end())
    it->second = "Good employee";

如果你真的必须通过各种可能的方式"加速"你的查找,你可以记住,如果CompanyID是来自[0 .. N]的整数,你可以使用std :: vector来获得一个快速的第一级索引合适的公司:

std::vector<std::unordered_map<EmployeeKey2, std::string>> EmployeeData;
// usage:
auto& companyMap = EmployeeData[EBuyNLargeCorp]; // or [selectedCompany(0..N)]
auto it = companyMap.find(selectedEmployee);
if (it != companyMap.end())
    it->second = "Good employee!";

如果EmployeeKey2缺少CompanyID字段,selectedCompany将成为向量中的索引.但这只是你为真正关键的性能提升而做的事情.