C++ 在两个 std::map 之间查找匹配项的有效方法

Question

我有一个用 RGB-D 相机采集的数据集和一个文本文件，其中存储了数据集的每个图像的时间戳和文件名。我所做的是解析这个文件并填充两个 std::map，一个用于 rgb 图像，另一个用于深度图像。现在，由于时间戳不相交，我必须编写一个例程来根据时间戳查找匹配的图像。这是我到目前为止写的：

typedef map<double,string> StampImageMap;

...

vector<string> &vstrImageFilenamesRGB;
vector<string> &vstrImageFilenamesD;
vector<double> &vTimestampsRGB;
vector<double> &vTimestampsDPT;

double tolerance = 0.02;

for(StampImageMap::iterator it=rgb_images.begin(); it != rgb_images.end(); it++) {
        bool found = false;
        StampImageMap::iterator jt=depth_images.begin();
        while(found == false && jt!=depth_images.end()) {
            if(fabs(it->first - jt->first) < tolerance) {
                found = true;
                vstrImageFilenamesRGB.push_back(it->second);
                vstrImageFilenamesD.push_back(jt->second);
                vTimestampsRGB.push_back(it->first);
                vTimestampsDPT.push_back(jt->first);
            }
            jt++;
        }
    }

我想知道是否有更有效的方法来执行此任务！

Answer 1

正如您现在编写的代码，复杂度为 Θ(n·m)，其中 n，m 是序列的大小。至少有两种方法可以改善这一点（第二种更有效，但更难编码）。

在外层循环体中，不要通过while(found == false && jt!=depth_images.end())遍历第二个映射中的所有元素。相反，使用 std::map::lower_bound 和 std::map::upper_bound 分别搜索 it->first - tolerance 和 it->first + tolerance。仅在这两个调用的结果之间循环。

所以，代码变成这样：
```
for(StampImageMap::iterator it=rgb_images.begin(); it != rgb_images.end(); it++) {
    StampImageMap::const_iterator lower = depth_images.lower_bound(it->first - tolerance);
    StampImageMap::const_iterator upper = depth_images.lower_bound(it->first + tolerance);

    // Now just search between lower and upper.
}
```
这会将每次迭代减少到Θ(log(m)) + p，其中p是这个范围的大小。
由于map的key是排序的，所以可以修改一个standard technique of finding the intersection of two sorted arrays到这种情况。这会将运行时间减少到 Θ(m + n)。请注意，修改有点棘手，因为您不是要查找确切元素的交集，而是要查找 "close enough" 个元素的交集。

这里是这个案例的伪代码：
```
 it = rgb_image.begin();
 jt = depth_image.begin();

 while(it != rgb_image.end() && jt != depth_image.end()) {
     if(fabs(it->first - jt->first) < tolerance) {
         // Match found!
         ++it;
         ++jt;
         continue;
     }

     if(it.first > jt.first + tolerance) {
         ++jt;
         continue;
     }

     ++it;
 }
```

C++ 在两个 std::map 之间查找匹配项的有效方法

C++ efficient way to find matches between two std::map

c++

algorithm

stdmap

dataset

matching