我有一个文件名列表，每个文件名代表一个时间点。该列表通常包含数千个元素。给定一个时间点，我想将这些文件名转换为时间对象(我使用的是boost::ptime)，然后找到该时间点相对于文件名std::lower_bound值。
例：
文件名(日期 + 时间，分钟增加，每个文件一分钟)：
station01_20170612_030405.hdf5
station01_20170612_030505.hdf5
station01_20170612_030605.hdf5
station01_20170612_030705.hdf5
station01_20170612_030805.hdf5
station01_20170612_030905.hdf5
如果我有一个时间点2017-06-12 03:06:00，那么它适合这里：
station01_20170612_030405.hdf5
station01_20170612_030505.hdf5
<--- The lower bound I am looking for is here
station01_20170612_030605.hdf5
station01_20170612_030705.hdf5
station01_20170612_030805.hdf5
station01_20170612_030905.hdf5
到目前为止，一切都很简单。现在的问题是文件列表可能掺杂了一些无效的文件名，这将使转换到时间点失败。
目前，我正在以简单/低效的方式执行此操作，我想对其进行优化，因为该程序将在服务器上运行并且运营成本很重要。所以，愚蠢的方式是：创建一个包含时间点的新列表，并且只推送有效的时间点：
vector<ptime> filesListTimePoints;
filesListTimePoints.reserve(filesList.size());
ptime time;
for(long i = 0; i < filesList.size(); i++) {
ErrorCode error = ConvertToTime(filesList[i], time);
if(error.errorCode() == SUCCESS)
filesListTimePoints.push_back(time);
}
//now use std::lower_bound() on filesListTimePoints
你看，问题是我正在使用一个线性解决方案，这个问题可以用O(log(N))复杂性来解决。我不需要转换所有文件，甚至不需要查看所有文件！
我的问题：我怎样才能将其嵌入到std::lower_bound中，使其保持最佳复杂性？
我对可能的解决方案的想法：
在 cpp 首选项上，有一个基本的实现std::lower_bound.我正在考虑修改它以获得有效的解决方案。但是我不确定当对置失败时该怎么办，因为该算法高度依赖于单调行为。这个问题有解决方案吗，即使是从数学上讲？
这是我最初考虑的版本：
template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value)
{
ForwardIt it;
typename std::iterator_traits<ForwardIt>::difference_type count, step;
count = std::distance(first, last);
while (count > 0) {
it = first;
step = count / 2;
std::advance(it, step);
ErrorCode error = ConvertToTime(*it, time);
if(error.errorCode() == SUCCESS)
{
if (*it < value) {
first = ++it;
count -= step + 1;
}
else
count = step;
}
else {
// skip/ignore this point?
}
}
return first;
}
我的最终解决方案(听起来可能很愚蠢)是使此方法成为列表的突变器，并删除无效的元素。有没有更清洁的解决方案？
您可以简单地按optional<ptime>索引。如果要缓存转换后的值，请考虑将其设为multimap<optional<ptime>, File>。
更好的是，创建一个表示文件的数据类型，并在其构造函数中计算时间点：
struct File {
File(std::string fname) : _fname(std::move(fname)), _time(parse_time(_fname)) { }
boost::optional<boost::posix_time::ptime> _time;
std::string _fname;
static boost::optional<boost::posix_time::ptime> parse_time(std::string const& fname) {
// return ptime or boost::none
}
};
现在，只需适当地定义operator<或使用例如 boost：：multi_index_container 按_time进行索引
进一步说明：
- 如果不清楚，这样的地图/套装将有自己的
lower_bound、upper_bound和equal_range操作，并且显然也会与std::lower_bound和朋友一起工作。 - 总有
filter_iterator适配器：http://www.boost.org/doc/libs/1_64_0/libs/iterator/doc/filter_iterator.html