问题
我有时间戳数据,我需要根据时间戳进行搜索,以获得与我最接近的输入时间戳匹配的现有时间戳.
优选地,这应该用STL解决. boost :: *或stl :: tr1 :: *(来自带有Featurepack的VS9)也是可能的.
带时间戳的数据示例：
- struct STimestampedData
- {
- time_t m_timestamp; // Sorting criterion
- CData m_data; // Payload
- }
使用stl :: vector,sort()和equal_range()的方法
由于地图或集合只允许我找到完全匹配,我不会再使用其中一个.
所以现在我有一个向量附加数据的向量.在搜索之前我使用< algorithm>的sort()并为它提供自定义比较函数.
之后,我使用< algorithm>的equal_range()来查找指定值x的两个邻居.
从这两个值我检查哪一个最接近x然后我有我最好的匹配.
虽然这不是太复杂,但我想知道是否有更优雅的解决方案.
也许STL已经有了一个完全正确的算法,所以我不会在这里重新发明一些东西？
更新：线性与二进制搜索
我忘了提到我有很多数据需要处理,所以我不想要线性搜索.
我使用sort()对向量进行排序的原因是因为它具有随机访问迭代器,而不是映射的情况.使用map不允许equal_range()以两倍的对数复杂度进行搜索.
我对么？
解决方法
我会使用set :: lower_bound来查找匹配或更大的值,然后递减迭代器以检查下一个较低的值.您应该使用std :: set而不是std :: map,因为您的密钥嵌入在对象中 – 您需要提供一个比较时间戳成员的仿函数.
- struct TimestampCompare
- {
- bool operator()(const STimestampedData & left,const STimestampedData & right) const
- {
- return left.m_timestamp < right.m_timestamp;
- }
- };
- typedef std::set<STimestampedData,TimestampCompare> TimestampedDataSet;
- TimestampedDataSet::iterator FindClosest(TimestampedDataSet & data,STimestampedData & searchkey)
- {
- TimestampedDataSet::iterator upper = data.lower_bound(searchkey);
- if (upper == data.begin() || upper->m_timestamp == searchkey.m_timestamp)
- return upper;
- TimestampedDataSet::iterator lower = upper;
- --lower;
- if (upper == data.end() ||
- (searchkey.m_timestamp - lower->m_timestamp) < (upper->m_timestamp - searchkey.m_timestamp))
- return lower;
- return upper;
- }
