std::map 获取价值 - 查找与手工制作的循环

Question

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

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

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

那么 "id" 的处理方式应该不同于 "name" 等

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

我想到了两种方法。

一，使用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
} 
....

第二步，遍历映射并为每个条目检查属性的名称并相应地进行：

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)。我不确定第二个解决方案的复杂性，因为它迭代地图一次 (O(N))，但每次迭代执行很多 if-else。我尝试 google 常见 map::find() 问题，但找不到任何有用的信息；他们中的大多数只需要从地图中获取一个值，然后 find() 以更复杂的方式完成此操作 (O(logN) vs O(N))。

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

另外，从代码样式上来说，哪一个代码更好更清晰？

Answer 1

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

固定属性

（只是为了完整性，我想这不是你想要的）如果可能属性的名称和类型都应该固定，最好的版本是使用简单的 class/struct，可能使用 boost::optional（std::optional with C++17）对于可能存在或不存在的值

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

优点：

所有“查找”都在编译时解决

缺点：

运行时没有扩展的灵活性

根据键只处理特定选项

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

在这种情况下，请记住像这样使用查找：

it1 = _propertyMap.find("id");

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

所以基本上使用 M 倍 find() 比循环更好，当只增加地图的大小时，但如果你以相同的方式增加发现的数量则更糟。但只有分析才能告诉您哪一个对于您的大小和用例来说更快。

根据类型处理所有选项

由于您的地图看起来很像键可以自定义，但类型来自一小部分，请考虑遍历地图并使用类型而不是名称来确定如何处理它们。像这样：

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
    }
    .....
}

这样做的好处是，您不需要任何关于地图键的真实信息，只需要它能够存储的类型。

Answer 2

假设我们有 N 个属性的地图，我们正在寻找 P 个属性的子集。这里粗略分析一下，不知道key的统计分布：

在纯映射方法中，您搜索 P 次，复杂度为 O(log(n))，即 O(p*log(n))
在 chained-if 方法中，您将遍历一次地图。那是 O(N)。但是你不应该忘记，if-then 链也是对 P 元素列表的（隐藏）遍历。因此，对于 N 个元素中的每一个，您正在搜索可能多达 P 个元素。所以你在这里有 O(p*n).

这意味着地图方法将胜过您的遍历，并且性能差距将随着 n 显着增加。当然，这没有考虑您在 if 链中没有的地图中的函数调用开销。所以如果 P 和 N 很小，你的方法仍然经得起理论比较。

为了进一步提高性能，您最终可以做的是使用 unordered_map，复杂度为 O(1)，将问题复杂度降低为 O (P)。

Answer 3

还有另一种选择，它结合了两者的优点。给定一个这样的函数（它是 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 地图可以单独构建并重复使用以减少开销。

std::map 获取价值 - 查找与手工制作的循环

std::map get value - find vs handcrafted loop

c++

performance

coding-style

stdmap

time-complexity

固定属性

根据键只处理特定选项

根据类型处理所有选项