Std :: pair as a key in a map
I have a large set of image data taken at a specific time, where each image capture is start_time
both stop_time
known and encoded as doubles. I want to load each sequential image into my simulation based on simulation time i.e. Check when the current simulation time falls within the start / stop interval.
I want to use a map for this, where the key is the std::pair<double, double>
start and stop times and the value is the full path to the image.
std::map<std::pair<double, double>, std::string> _sequence; // t1, t2 and full path
My question is: How can I find a map like this to determine if _currentTime is within an interval?
source to share
First, don't use map
with a key std::pair<double, double>
if searching for include is the main thing you want to do. It just isn't an operation that makes sense with this data structure.
But if you insist, the code will look something like this (in C ++ 11):
bool isWithinInterval() const {
for (const auto& pr : _sequence) {
if (_currentTime >= pr.first.first && _currentTime <= pr.first.second) {
return true;
}
}
return false;
}
Pre-C ++ 11, same idea, just slightly different loop syntax. Ideally we would use std::find_if
, but it was a problem to express the map value_type
. However, in C ++ 14 there are no such problems:
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();
Or simply:
return std::any_of(_sequence.begin(), _sequence.end(),
[_currentTime](const auto& pr) {
return _currentTime >= pr.first.first && _currentTime <= pr.first.second;
});
source to share
One approach might be to not use std::map<std::pair<double, double>, std::string>
, but rather std::map<double, std::pair<double, std::string>>
: you would use m.lower_bound(current_time)
to find the start of a series of elements where it current_time
can fit. Then you iterate through the iterator until it reaches the end, falls within the appropriate range, or reaches the end 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
}
}
Using a c layout std::pair<double, double>
, the key has the inconvenient need to come up with a second time. You could use std::make_pair(current_time, current_time)
.
source to share
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 associated value
if ( key_value_pair.first.first <= search || search <= key_value_pair.first.second ) {
found = true;
break;
}
}
if ( found ) {
/* it within an interval pair! */
} else {
/* it not within an interval pair! */
}
I would recommend also looking at boost::icl
source to share
If possible, don't use std :: pair as a key. It doesn't make sense as a key, because you end up with a situation where two overlapping ranges map to the same element.
Anyway, here's how I could implement a solution to this problem. lower_bound
/ upper_bound
is your friend here. Also, you can avoid the reverse iterator trick by specifying the values at the time of the stop.
#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;
}
source to share