std :: pair作爲地圖中的關鍵字

Question

我有一個很大的圖像數據集，在特定的時間拍攝，其中每個圖像捕獲start_time和stop_time已知並編碼爲雙打。 我想根據模擬時間將每個連續的圖像加載到我的模擬中，即 - 檢查當前模擬時間是否落入開始/停止時間間隔內。

我想爲此使用地圖，其中關鍵是std::pair<double, double>開始&停止時間，值是圖像的完整路徑。

std::map<std::pair<double, double>, std::string> _sequence; // t1, t2 and full path 

我的問題： 如何搜索這樣的地圖找到，如果_currentTime是時間間隔對中？

Answer 1

首先，如果搜索包含是您想要做的主要事情，請不要使用map作爲std::pair<double, double>。這不僅僅是一個對數據結構有意義的操作。

但如果你堅持，代碼看起來像這樣（在C++ 11）：

bool isWithinInterval() const { 
    for (const auto& pr : _sequence) { 
     if (_currentTime >= pr.first.first && _currentTime <= pr.first.second) { 
      return true; 
     } 
    } 
    return false; 
} 

預C++ 11，同樣的想法，只是略有不同的循環語法。理想情況下，我們使用std::find_if，但表達地圖的value_type是一件麻煩事。在C++ 14雖然沒有這樣的麻煩：

auto it = std::find_if(_sequence.begin(), 
         _sequence.end(), 
         [_currentTime](const auto& pr) { 
          return _currentTime >= pr.first.first && _currentTime <= pr.first.second; 
         }); 
return it != _sequence.end(); 

或者只是：

return std::any_of(_sequence.begin(), _sequence.end(), 
        [_currentTime](const auto& pr) { 
         return _currentTime >= pr.first.first && _currentTime <= pr.first.second; 
        }); 

Answer 2

double search = 0.; /* or some other value */ 
bool found = false; 
for (auto & key_value_pair : _sequence) { 
    // key_value_pair.first == map key 
    // key_value_pair.second == key's associated value 
    if (key_value_pair.first.first <= search || search <= key_value_pair.first.second) { 
     found = true; 
     break; 
    } 
} 
if (found) { 
    /* it's within an interval pair! */ 
} else { 
    /* it's not within an interval pair! */ 
} 

我會建議也尋找到boost::icl

Answer 3

一種方法可能是不到使用std::map<std::pair<double, double>, std::string>而不是std::map<double, std::pair<double, std::string>>：您將使用m.lower_bound(current_time)來查找元素範圍的起點current_time可能適合。然後，您會走的迭代，直到它到達終點，落入相關範圍，或者超出了結束時間：

auto it = _sequence.lower_bound(current_time); 
for (; it != _sequence.end() && current_time <= it->second; ++it) { 
    if (it.first <= current_time) { 
     // found a matching element at it 
    } 
} 

與std::pair<double, double>的關鍵有別扭需要拿出一個使用佈局第二次。不過，您可以使用std::make_pair(current_time, current_time)。

Answer 4

如果可能，請不要使用std :: pair作爲鍵。它並不是真正意義上的關鍵，因爲最終會出現兩個重疊範圍映射到相同元素的情況。

無論如何，這裏是我將如何實施解決這個問題。 lower_bound/upper_bound是你的朋友在這裏。此外，您可以通過在停止時間鍵入值來避免逆向迭代器技巧。

#include <map> 
#include <stdio.h> 

struct ImageStuff 
{ 
    double startTime; 
    double stopTime; 
    char data[1000]; 
}; 

typedef std::map<double, ImageStuff> starttime_map_type; 
starttime_map_type starttime_map; 

ImageStuff & MakeImage (double start, double stop) { 
    ImageStuff newImage; 
    newImage.startTime = start; 
    newImage.stopTime = stop; 
    return starttime_map[start] = newImage; 
} 

starttime_map_type::iterator FindByTime (double time) { 
    starttime_map_type::reverse_iterator i = starttime_map_type::reverse_iterator(starttime_map.upper_bound(time)); 
    if (i == starttime_map.rend() || time > i->second.stopTime) { 
    printf ("Didn't find an image for time %f\n", time); 
    return starttime_map.end(); 
    } 
    else { 
    printf ("Found an image for time %f\n", time); 
    return i.base(); 
    } 
    return starttime_map.end(); 
} 


int main (void) 
{ 
    MakeImage (4.5, 6.5); 
    MakeImage (8.0, 12); 
    MakeImage (1, 1.2); 

    auto i = FindByTime(3); 
    i = FindByTime(4.5); 
    i = FindByTime(9); 
    i = FindByTime(15); 

    return 0; 
}