c++ - 创建 boost::tuple 和 std::vector 的映射

Question

我想用键创建映射，作为两个字符串和一个整数的组合，值可以是基于键的多个整数。所以我尝试创建 boost::tuple 和 std::vector 的映射。我尝试为此编写示例程序，如下所示:

#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <string>
#include <boost/tuple/tuple.hpp>
#include <boost/unordered_map.hpp>

using namespace std;

typedef boost::tuple<std::string, std::string, int> tpl_t;

struct key_hash : public std::unary_function<tpl_t, std::size_t>
{
    std::size_t operator()(const tpl_t& k) const
    {
        return boost::get<0>(k)[0] ^ boost::get<1>(k)[0] ^ boost::get<2>(k);
    }
};

struct key_equal : public std::binary_function<tpl_t, tpl_t, bool>
{
    bool operator()(const tpl_t& v0, const tpl_t& v1) const
    {
        return (
                 boost::get<2>(v0) == boost::get<2>(v1) &&
                 boost::get<0>(v0) == boost::get<0>(v1) &&
                 boost::get<1>(v0) == boost::get<1>(v1)               
               );
   }
};

typedef boost::unordered_map<tpl_t, std::vector<int>, key_hash,key_equal> map_t;

void function1(map_t& myMap, std::string file, std::string txt, int num1, int num2)
{
    tpl_t key = boost::make_tuple(file, txt, num1);
    map_t::iterator itr = myMap.find(key);
    if(itr != myMap.end())
    {
        itr->second.push_back(num2);
    }
    else
    {
        std::vector<int> num2Vec;
        num2Vec.push_back(num2);
        myMap.insert(std::make_pair(boost::make_tuple(file,txt,num1),num2Vec));
    }   
}

int main()
{
    map_t myMap;

    function1(myMap, "file1", "text", 5, 10);
    function1(myMap, "file1", "text_t", 5, 30);
    function1(myMap, "file2", "text", 5, 50);
}

这个程序工作正常，但我想知道是否有更好的方法来做到这一点。我担心性能，因为 map 的大小可以增长到任何大小。不过我还没有测量性能。

谢谢，
史瑞克

Answer 1

I am worried about performance as size of map can grow to anything. I have not measured performance though.

在您担心您的设计可能不适合该任务之前，您应该先考虑进行性能测量。

设计一些用例，并创建样本数据分布 - 复合键和值的常见情况、每边的标准差和尾部。不仅要考虑数据集本身，还要考虑其设置和使用配置文件 - 插入、搜索、删除的频率。

也就是说，总的来说，您将复合键建模为元组的方法是明智的，尽管主观上我更喜欢结构，但这是一个非常次要的评论。

对于值 - 考虑使用 multi-map而不是带有 vector 的 map ，这可能会更快，但这取决于值的数量。

这里还有一些需要考虑的事情:

• 您的(多) map 必须排序还是可以保持无序？根据使用情况，无序 map 可能会快得多。
• 您能否调整您对键的了解以更快地进行比较？例如，如果字符串很长且是静态的(例如，几乎总是“file1”)，您可以先评估两个比较键的整数部分吗？
• 使用分层 map 而不是具有复合键的 map 对您有好处吗？

最好用示例数据和场景来回答上面的许多问题，这些示例数据和场景构成程序测试套件的一部分。这样您就可以在更改数据结构时观察性能变化。