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()) 遍历第二个 map 中的所有元素。相反，使用 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 的键是排序的，你可以修改一个standard technique of finding the intersection of two sorted arrays对于这种情况。这会将运行时间减少到Θ(m + n)。请注意，修改有点棘手，因为您不是要查找精确元素的交集，而是要查找“足够接近”元素的交集。

  这里是这个案例的伪代码:

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