首页 文章

std :: map get value - find vs handcrafted loop [关闭]

提问于
浏览 次
5

我有一个std :: map对象 map<string , Property*> _propertyMap ，其中 string 是属性的名称， Property* 包含属性值 .

我需要处理属性值并将它们转换为特定的数据格式 - 每个属性都有自己的格式，例如..如果映射初始化如下：

_propertyMap["id"]   = new Property(Property::UUID, "12345678");
_propertyMap["name"] = new Property(Property::STRING, "name");
....

然后 "id" 的处理方式应与 "name" 等不同 .

这意味着我需要在 Map 中查找每个属性并相应地处理其值 .

我想到了两种方法 .

一，使用 std::map::find 方法获取特定属性，如下所示：

map<string , Property*>::iterator it1 = _propertyMap.find("id");
if(it1 != _propertyMap.end())
{
   //element found - process id values
} 
map<string , Property*>::iterator it2 = _propertyMap.find("name");
if(it2 != _propertyMap.end())
{
   //element found - process name values
} 
....

二，迭代 Map ，并为每个条目检查属性的名称是什么，并相应地继续：

for (it = _propertyMap.begin(); it != _propertyMap.end(); ++it )
    {
        //if it is events - append the values to the matching nodes
        if (it->first == "id")
        {
           //process id values
        }
        else if (it->first == "name")
                {
                    //process name values
                }
        .....
    }

鉴于Time complexity of std::map::find is O(logN)，第一个解决方案的复杂性是 O(NlogN) . 我不确定第二个解决方案的复杂性，因为它迭代 Map 一次（ O(N) ），但每次迭代执行很多 if-else . 我试图google常见 map::find() 问题，但找不到任何有用的信息;他们中的大多数只需要从 Map 中获取一个值，然后 find() 以更好的复杂度（ O(logN) vs O(N) ）执行此操作 .

什么是更好的方法？或者还有另一个我没想到的？

另外，代码样式说话，哪一个更好，清晰的代码？

c++ performance coding-style time-complexity stdmap

3 回答

  • 2

    我在这里看到了一些不同的用例，具体取决于你的想法：

    固定属性

    （只是为了完整性，我想这不是你想要的）如果应该修复可能的属性的名称和类型，最好的版本是使用一个简单的类/结构，可能使用 boost::optional （ std::optional 与C17）的值可能存在与否

    struct Data{
    int id = 0;
    std::string name = "";
    boost::optional<int> whatever = boost::none;
}

    优点：

    • 所有"lookups"在编译时解析

    缺点：

    • 无法在运行时扩展

    根据其密钥仅处理特定选项

    如果您只想处理特定的选项子集，但保留选项以拥有（未处理的）自定义键，您的方法似乎是合适的 .

    在这种情况下，请记住使用find这样：

    it1 = _propertyMap.find("id");

    具有复杂度O（logN）但使用了M次，其中M是处理选项的数量 . 这不是 Map 的大小，它是您使用 find() 获取特定属性的次数 . 在您的（缩短的）示例中，这意味着O（2 * logN）的复杂性，因为您只查找2个键 .

    因此，当只有 Map 的大小增加时，基本上使用M-times find() 比循环更好，但如果以相同的方式增加查找数量则更糟 . 但只有剖析可以告诉你哪一个对你的大小和用例更快 .

    根据类型处理所有选项

    由于您的 Map 看起来很像键可以是自定义的，但类型来自一个小子集，考虑在 Map 上循环并使用类型而不是名称来确定如何处理它们 . 像这样的东西：

    for (it = _propertyMap.begin(); it != _propertyMap.end(); ++it )
{
    if (it->first.type() == Property::UUID)
    {
       //process UUID values
    }
    else if (it->first.type() == Property::STRING)
    {
        //process STRING values
    }
    .....
}

    这样做的好处是，您不需要任何有关 Map 键真正含义的信息，只需要它能够存储的类型 .

    回复于
  • 1

    假设我们有一个N属性的映射，我们正在寻找P属性的子集 . 这是一个粗略的分析，不知道密钥的统计分布：

    • 在纯映射方法中，搜索P次，复杂度为O（log（n）），即O（p * log（n））

    • 在chained-if方法中，您将遍历 Map . 那是O（N） . 但是你不应该忘记if-then链也是P元素列表的（hiden）遍历 . 因此，对于N个元素中的每一个，您正在搜索可能最多为P的元素 . 所以你在这里有一个复杂的O（p * n） .

    这意味着 Map 方法将优于您的遍历，并且性能差距将随着n而显着增加 . 当然，这并没有考虑到if-chain中没有的map中的函数调用开销 . 因此，如果P和N很小，你的方法仍然可以进行理论比较 .

    您最终可以进一步提高性能的方法是使用 unordered_map ，复杂度为O（1），将问题复杂度降低到O（P） .

    回复于
  • 1

    还有另一种选择，结合了两者的优点 . 给定这样的函数（这是 std::set_intersection 的改编）：

    template<class InputIt1, class InputIt2, 
         class Function, class Compare>
void match(InputIt1 first1, InputIt1 last1,
           InputIt2 first2, InputIt2 last2,
           Function f, Compare comp)
{   
    while (first1 != last1 && first2 != last2) {
        if (comp(*first1,*first2)) {
            ++first1;
        } else {
            if (!comp(*first2,*first1)) {
                f(*first1++,*first2);
            }
            ++first2;
        }
    }
}

    您可以使用它在O（N M）时间内处理所有属性 . 这是一个例子：

    #include <map>
#include <string>
#include <functional>
#include <cassert>

using std::map;
using std::string;
using std::function;

struct Property {
  enum Type { UUID, STRING };
  Type type;
  string value;
};

int main()
{
    map<string,Property> properties;
    map<string,function<void(Property&)>> processors;

    properties["id"] = Property{Property::UUID,"12345678"};
    properties["name"] = Property{Property::STRING,"name"};

    bool id_found = false;
    bool name_found = false;

    processors["id"]   = [&](Property&){ id_found = true; };
    processors["name"] = [&](Property&){ name_found = true; };

    match(
       properties.begin(),properties.end(),
       processors.begin(),processors.end(),
       [](auto &a,auto &b){ b.second(a.second); },
       [](auto &a,auto &b) { return a.first < b.first; }
    );

    assert(id_found && name_found);
}

    processors Map 可以单独构建重用以减少开销 .

    回复于

相关问题