在排序的STL容器中查找给定键的“最佳匹配键”
问题
我有带时间戳的数据，我需要根据时间戳进行搜索，以便获得与我的输入时间戳最匹配的现有时间戳。
最好使用STL来解决这个问题。boost::*或stl::tr1::* (来自带有Featurepack的VS9 )也是可能的。
带时间戳的数据示例：
struct STimestampedData
{
time_t m_timestamp; // Sorting criterion
CData m_data; // Payload
}使用stl::vector、sort()和equal_range()的方法
因为map或set只允许我找到完全匹配的内容，所以我不能再使用它们中的任何一个。因此，现在我有了一个vector，当数据传入时，我会将数据追加到它。在搜索之前，我使用了<algorithm>的sort()，并为它提供了一个自定义的比较函数。
之后，我使用<algorithm>的equal_range()来查找具有指定值x的两个邻居，从这两个值中，我检查哪一个最接近x，然后得到我的最佳匹配。
虽然这并不太复杂，但我想知道是否有更优雅的解决方案。
也许STL已经有一个算法可以做到这一点，所以我不会在这里重新发明一些东西？
更新:线性搜索与二进制搜索
我忘了提一下，我有相当多的数据要处理，所以我不想线性搜索。
我之所以使用sort()对向量进行排序，是因为它具有随机访问迭代器，而map并非如此。使用map将不允许equal_range()以两倍的对数复杂度进行搜索。
我说的对吗？
回答 4
Stack Overflow用户
发布于 2008-10-20 14:55:18
我将使用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)
{
if (data.empty())
return data.end();
TimestampedDataSet::iterator upper = data.lower_bound(searchkey);
if (upper == data.end())
return --upper;
if (upper == data.begin() || upper->m_timestamp == searchkey.m_timestamp)
return upper;
TimestampedDataSet::iterator lower = upper;
--lower;
if ((searchkey.m_timestamp - lower->m_timestamp) < (upper->m_timestamp - searchkey.m_timestamp))
return lower;
return upper;
}Stack Overflow用户
发布于 2008-10-20 14:10:14
我也会使用equal_range来做这样的事情。
如果您每次都对向量使用sort()，那么使用映射(或集合)可能更好，因为它总是自动排序的，并使用成员equal_range
但这取决于插入/查询的数量/数据量。(尽管对于在查询时总是需要排序的东西，映射将是我的第一选择，并且我只会在有非常好的理由时才使用向量)
Stack Overflow用户
发布于 2008-10-20 14:08:55
根据您的使用情况，您可以进行简单的线性搜索，而不是排序。提出一个“距离”函数，循环跟踪到目前为止的最佳匹配，以及它的距离。当你找到一个更好的匹配，忘记前一个，并保留新的和它的距离。当您遍历所有内容时，您就有了匹配项。
结果是O(N*S)，其中N是向量中的项数，S是搜索次数。
您当前的方法是O((N+S)*LogN)，如果搜索的数量很少且有界，这个值会更大。否则，排序/二进制搜索更好。
https://stackoverflow.com/questions/218488
复制相似问题
腾讯云开发者
