blocks|key|3997215|text|根据您的使用情况，您可以进行简单的线性搜索，而不是排序。提出一个“距离”函数，循环跟踪到目前为止的最佳匹配，以及它的距离。当你找到一个更好的匹配，忘记前一个，并保留新的和它的距离。当您遍历所有内容时，您就有了匹配项。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3997216|结果是O(N*S)，其中N是向量中的项数，S是搜索次数。|3997217|您当前的方法是O((N%2BS)*LogN)，如果搜索的数量很少且有界，这个值会更大。否则，排序/二进制搜索更好。|3997218|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

<p>Depending on what your usage is, you could do a simple linear search instead of a sort.  Come up with a "distance" function, loop through keeping track of the best match so far, and its distance.  When you find a better match, forget the previous one, and keep the new one and its distance.  When you've looped through everything, you have your match.</p>

<p>This works out to be O(N*S) where N is the number of items in the vector and S is the number of searches.</p>

<p>Your current way is O((N+S)*LogN) which is greater if the number of searches is small and bounded.   Otherwise the sort / binary search is better.</p>


blocks|key|5407864|text|我也会使用equal_range来做这样的事情。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5407865|如果您每次都对向量使用sort()，那么使用映射(或集合)可能更好，因为它总是自动排序的，并使用成员equal_range|5407866|但这取决于插入/查询的数量/数据量。(尽管对于在查询时总是需要排序的东西，映射将是我的第一选择，并且我只会在有非常好的理由时才使用向量)|5407867|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

<p>I would use equal_range too for such a thing.</p>

<p>If you are using sort() every time on your vector it might be better to use a map (or set), as that's always sorted automatically, and use the member equal_range</p>

<p>But that depends on the the amount of inserts / queries / amount of data. (although for something that always needs to be sorted when I query, a map would be my first choice, and I'd only use a vector if there was a very good reason)</p>


blocks|key|828967|text|我将使用set::lower_bound查找匹配或更大的值，然后递减迭代器以检查下一个较低的值。您应该使用std::set而不是std::map，因为您的键嵌入在对象中-您需要提供一个函数来比较时间戳成员。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|828968|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()+%7C%7C+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;
}|code-block|syntax|javascript|828969|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

<p>I would use set::lower_bound to find the matching or greater value, then decrement the iterator to check the next lower value.  You should use std::set rather than std::map since your key is embedded in the object - you'll need to provide a functor that compares the timestamp members.</p>

<pre><code>struct TimestampCompare
{
    bool operator()(const STimestampedData &amp; left, const STimestampedData &amp; right) const
    {
        return left.m_timestamp &lt; right.m_timestamp;
    }
};
typedef std::set&lt;STimestampedData,TimestampCompare&gt; TimestampedDataSet;

TimestampedDataSet::iterator FindClosest(TimestampedDataSet &amp; data, STimestampedData &amp; 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-&gt;m_timestamp == searchkey.m_timestamp)
        return upper;
    TimestampedDataSet::iterator lower = upper;
    --lower;
    if ((searchkey.m_timestamp - lower-&gt;m_timestamp) &lt; (upper-&gt;m_timestamp - searchkey.m_timestamp))
        return lower;
    return upper;
}
</code></pre>


blocks|key|5407932|text|//the+function+should+return+the+element+from+iArr+which+has+the+least+distance+from+input
double+nearestValue(vector<double>+iArr,+double+input)
{
++++double+pivot(0),temp(0),index(0);
++++pivot+=+abs(iArr[0]-input);
++++for(int+m=1;m<iArr.size();m%2B%2B)
++++{+++++++++++
++++++++temp+=+abs(iArr[m]-input);

++++++++if(temp<pivot)
++++++++{
++++++++++++pivot+=+temp;
++++++++++++index+=+m;
++++++++}
++++}

++++return+iArr[index];
}

void+main()
{
++++vector<double>+iArr;

++++srand(time(NULL));
++++for(int+m=0;m<10;m%2B%2B)
++++{
++++++++iArr.push_back(rand()%2520);
++++++++cout<<iArr[m]<<"+";
++++}

++++cout<<"\nnearest+value+is:+"<<lib.nearestValue(iArr,16)<<"\n";
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|5407933|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>//the function should return the element from iArr which has the least distance from input
double nearestValue(vector&lt;double&gt; iArr, double input)
{
    double pivot(0),temp(0),index(0);
    pivot = abs(iArr[0]-input);
    for(int m=1;m&lt;iArr.size();m++)
    {           
        temp = abs(iArr[m]-input);

        if(temp&lt;pivot)
        {
            pivot = temp;
            index = m;
        }
    }

    return iArr[index];
}

void main()
{
    vector&lt;double&gt; iArr;

    srand(time(NULL));
    for(int m=0;m&lt;10;m++)
    {
        iArr.push_back(rand()%20);
        cout&lt;&lt;iArr[m]&lt;&lt;" ";
    }

    cout&lt;&lt;"\nnearest value is: "&lt;&lt;lib.nearestValue(iArr,16)&lt;&lt;"\n";
}
</code></pre>


<h2>Problem</h2>

<p>I have timestamped data, which I need to search based on the timestamp in order to get the one existing timestamp which matches my input timestamp the closest.<br>
Preferably this should be solved with the STL. boost::* or stl::tr1::* (from VS9 with Featurepack) are also possible.<br>
Example of timestamped data:</p>

<pre><code>struct STimestampedData
{
 time_t m_timestamp; // Sorting criterion
 CData m_data;       // Payload
}
</code></pre>

<h2>Approach with <code>stl::vector</code>, <code>sort()</code> and <code>equal_range()</code></h2>

<p>Since a <code>map</code> or <code>set</code> only allows me to find exact matches, I don't get any further using one of these.
So now I have a <code>vector</code> to which I append data as it is coming in. Before searching I use <code>&lt;algorithm&gt;</code>'s <code>sort()</code> and supply it with a custom comparison function.<br>
After that I use <code>&lt;algorithm&gt;</code>'s <code>equal_range()</code> to find the two neighbors of a specified value <code>x</code>.
From these two values I check which one is closest to <code>x</code> and then I have my best match.</p>

<p><br>
While this is not too complex, I wonder if there are more elegant solutions to this.<br>
Maybe the STL already has an algorithm which does exactly that so I'm not re-inventing something here?</p>

<h2>Update: Linear vs. binary search</h2>

<p>I forgot to mention that I have quite a lot of data to handle so I don't want to have to search linearly.<br>
The reason I am sorting a vector with <code>sort()</code> is because it has random access iterators which is not the case with a <code>map</code>. Using a <code>map</code> would not allow <code>equal_range()</code> to do a search with twice logarithmic complexity.<br>
Am I correct?</p>


Finding "best matching key" for a given key in a sorted STL container

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

问题我有带时间戳的数据，我需要根据时间戳进行搜索，以便获得与我的输入时间戳最匹配的现有时间戳。最好使用STL来解决这个问题。boost::*或stl::tr1::* (来自带有Featurepack的VS9 )也是可能的。带时间戳的数据示例：struct STimestampedData{ time_t m_times...

问在排序的STL容器中查找给定键的“最佳匹配键”
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在排序的STL容器中查找给定键的“最佳匹配键”EN