正文 

当前位置： 首页 > 知识 >

在 std::map 中查找最接近或准确的键

     2023-02-22     217

关键词：

【中文标题】在 std::map 中查找最接近或准确的键【英文标题】：Finding the closest or exact key in a std::map 【发布时间】：2015-02-09 07:43:24 【问题描述】：

我需要创建一个将长度链接到时间间隔的查找表（两者都是双精度数据类型）。键在插入时线性递增，因此它已经被排序（也许 unordered_map 会更好？）。

我正在寻找一种方法来找到与提供的当前长度最匹配的密钥以获取时间值，或者更好地找到围绕长度的两个密钥（给定密钥在它们之间），这样我就可以找到两个时间值之间的插值。

我还需要尽可能好的性能，因为它会被实时调用。

编辑：我宁愿以下是对下面第一个答案的评论，但格式很难阅读。

我尝试执行以下操作，但它似乎返回相同的迭代器 (5.6)：

std::map<double, double> map;
map.insert(std::pair<double, double>(0.123, 0.1));
map.insert(std::pair<double, double>(2.5, 0.4));
map.insert(std::pair<double, double>(5.6, 0.8));

std::map<double, double>::iterator low, high;
double pos = 3.0;
low = map.lower_bound(pos);
high = map.upper_bound(pos);

我如何获得“低”以指向最后一个元素

编辑 2： 愚蠢的我，'低-'会做到这一点，前提是它不是第一个元素。

到达那里:)

【问题讨论】：

一些附加信息可能会有所帮助。到目前为止我得到的是有一个函数 l = f(t)。及其逆 t = f^-1(l)。您需要从一些数据点估计该函数并对其进行插值，对吗？而不是查找表，也许一些不断更新的近似函数会更好地为您服务。 如果地图中只有几个条目（比如少于 5 个），线性搜索通常比一开始使用地图要快。如果您有更多条目，则可以使用等距时间值“采样”您的查找表条目。然后，您无需搜索，但可以计算 LUT 中正确条目的索引。 【参考方案1】：

为此，您可以使用std::map::lower_bound

返回一个迭代器，指向不小于key的第一个元素。

或std::map::equal_range

返回一个范围，其中包含容器中具有给定键的所有元素。

在您的情况下，如果您想要最接近的条目，则需要检查返回的条目和之前的条目并比较差异。这样的事情可能会起作用

std::map<double, double>::iterator low, prev;
double pos = 3.0;
low = map.lower_bound(pos);
if (low == map.end()) 
    // nothing found, maybe use rbegin()
 else if (low == map.begin()) 
    std::cout << "low=" << low->first << '\n';
 else 
    prev = std::prev(low);
    if ((pos - prev->first) < (low->first - pos))
        std::cout << "prev=" << prev->first << '\n';
    else
        std::cout << "low=" << low->first << '\n';

【讨论】：

谢谢。搜索键总是 >= min 和 一个问题，不过。 std::map 是引擎盖下最快的吗？查找表可能包含多达 10000 个元素，但我可以通过更多近似值来减少它.. 哈希映射 (std::unordered_map) 在查找精确值时可能会更快，但是您没有排序的值。所以std::map 或排序的std::vector 似乎是这个用例最快的标准容器。当您总是想要最大或最小值时，使用优先级队列可能很有用。 好吧，既然我已经计算了新的时间，我发现我可以低至 100 个元素，并且不会在精度上损失太多。到目前为止一切顺利。【参考方案2】：

“可能的最佳性能” - 假设你以递增的顺序插入元素，你可以 push_back/emplace_back 将它们放入 std::vector 然后使用 std::lower_bound - 你会变得更好缓存利用率，因为数据将被打包到连续的地址空间中。

【讨论】：

谢谢，当我进一步优化它时，我会考虑移动到一个向量。对不起，我错过了你的答案。【参考方案3】：

您当然可以使用 lower_bound 和 upper_bound，它们在运行时是对数的。他们应该做你想做的。

std::map<double,double>::iterator close_low;
//... your_map ...
close_low=your_map.lower_bound (current_length);

这应该给你一个迭代器，指向第一个键为

【讨论】：

"对 upper_bound 做同样的事情，你的时间就会被包围。" - 这会使搜索时间加倍 - 通常最好简单地增加迭代器以达到大于元素或end()（前者必须紧跟在下限之后，但即使有multimap，如果可能有很多相同的关键元素，您可能只会担心上限，并且您不需要/不想单独迭代和操作它们。【参考方案4】：

std::lower_bound() 和 std::upper_bound() 函数在这里很有用。

lower_bound() 将&gt;= 的第一个元素赋予您要查找的值； upper_bound() 给出的第一个元素是&gt;，而不是值。

例如，在以下列表中搜索值 5：1,3,5,5,61 使用 lower_bound() 返回第三个元素，而 upper_bound() 将返回第五个元素。 如果这两个函数返回相同的东西x，那么您要查找的值不在列表中。 它前面的值是x-1，后面的值是x。

1正如Tony D 在评论中指出的那样，该问题要求地图，一般不包含重复元素。 我保留这个例子来说明这两个功能。

【讨论】：

【参考方案5】：

完整的通用解决方案（最初的想法取自Olaf Dietsche的answer）：

#include <map>
#include <iostream>
#include <cstdint>

template <typename T1, typename T2>
T1 findClosestKey(const std::map<T1, T2> & data, T1 key)

    if (data.size() == 0) 
        throw std::out_of_range("Received empty map.");
    

    auto lower = data.lower_bound(key);

    if (lower == data.end()) // If none found, return the last one.
        return std::prev(lower)->first;

    if (lower == data.begin())
        return lower->first;

    // Check which one is closest.
    auto previous = std::prev(lower);
    if ((key - previous->first) < (lower->first - key))
        return previous->first;

    return lower->first;


int main () 
double key = 3.3;

std::map<double, int> data = -10, 1000, 0, 2000, 10, 3000;

std::cout << "Provided key: " << key << ", closest key: " << findClosestKey(data, key) << std::endl;
return 0;

【讨论】：

【参考方案6】： 
#include <map>

template <typename T1, typename T2>
std::map<T1, T2>::iterator nearest_key(const std::map<T1, T2>& map, T1 key) 
    auto lower_bound = map.lower_bound(key);
    auto upper_bound = lower_bound; upper_bound++;
    if (lower_bound == map.end()) return upper_bound;
    if (upper_bound == map.end()) return lower_bound;
    unsigned int dist_to_lower = std::abs((int)lower_bound->first - (int)key);
    unsigned int dist_to_upper = std::abs((int)upper_bound->first - (int)key);
    return (dist_to_upper < dist_to_lower) ? upper_bound : lower_bound;

【讨论】：

【参考方案7】：

以上是错误的。应该是这样的 模板

typename std::map<T1, T2>::const_iterator nearest_key(const std::map<T1, T2>& map, T1 key)

    auto lower_bound = map.lower_bound(key);
    if (lower_bound == map.end()) return --lower_bound;
    auto upper_bound = lower_bound; upper_bound++;
    if (upper_bound == map.end()) return lower_bound;
    auto dist_to_lower = lower_bound->first - key;
    auto dist_to_upper = upper_bound->first - key;
    return (dist_to_upper < dist_to_lower) ? upper_bound : lower_bound;

【讨论】：

虽然此代码可能会为 OP 的问题提供解决方案，但强烈建议您提供有关此代码为何和/或如何回答问题的额外上下文。从长远来看，只有代码的答案通常会变得毫无用处，因为未来遇到类似问题的观众无法理解解决方案背后的原因。

是否可以使用 boost.any 作为 std::map 中的键（或类似的东西）？

】是否可以使用boost.any作为std::map中的键（或类似的东西）？【英文标题】：Isitpossibletouseboost.anyasakeyinastd::map(orsomethingsimiliar)?【发布时间】：2009-05-0509:01:20【问题描述】：std::map&lt;any,string&gt;不工作所以我想知道是否有另... 查看详情

在 mutil 组中查找最接近的值

】在mutil组中查找最接近的值【英文标题】：Findingtheclosestvalueswithinmutilgroup【发布时间】：2021-12-2613:02:04【问题描述】：我的数据1是id1value119811011118117029522013160470我的数据2是id2value211001120210522003300如何使用group_by或mutate(dplyr)从data... 查看详情

在最接近指定日期的列表中查找上一个日期

】在最接近指定日期的列表中查找上一个日期【英文标题】：Findapreviousdateonalistclosesttoaspecifieddate【发布时间】：2014-03-1219:51:48【问题描述】：我想要一个VBA代码或公式，它们将采用可变日期值并在日期列表范围内找到它。如果... 查看详情

在字符串的 std::map 中查找编译错误，长

】在字符串的std::map中查找编译错误，长【英文标题】：Compilationerrorinfindinastd::mapofstring,long【发布时间】：2017-01-0705:19:09【问题描述】：我正在使用VC++开发VisualStudio2013。我有一个std::map如下，std::map<std::string,unsignedint>myMap;... 查看详情

如何在最接近条件的数组中查找数据

】如何在最接近条件的数组中查找数据【英文标题】：Howtofinddatainsidearraythatismostclosesttoacondition【发布时间】：2014-02-2608:06:05【问题描述】：我有一个双Double[]array=newDouble[5];数组例如，如果数组包含这样的数据：0.5,1.5,1.1,0.6,2如... 查看详情

优化查找和排序(代码片段)

优化查找和排序C++程序会进行许多查找操作。从编程语言的编译器到浏览器，从控制链表到数据库，许多反复进行的程序活动都会在某个内部的循环底层进行查找操作。就经验而言，查找操作通常会出现在热点函数的列表中。因... 查看详情

在数组中查找三个元素之和最接近给定数字

】在数组中查找三个元素之和最接近给定数字【英文标题】：Findingthreeelementsinanarraywhosesumisclosesttoagivennumber【发布时间】：2011-01-0510:27:19【问题描述】：给定一个整数数组，A1,A2,...,An，包括负数和正数，以及另一个整数S。现在... 查看详情

在sql server中查找最接近的匹配行

】在sqlserver中查找最接近的匹配行【英文标题】：Findtheclosestmatchingrowinsqlserver【发布时间】：2016-11-0314:29:32【问题描述】：我有下表。TableName:MaskColumns:MaskIdINTMaskCodeVARCHAR(100)如果我将Input作为MaskId=1传递，那么我得到两条不同掩... 查看详情

使用 lambda 函数在 std::unordered_map 中查找最小值

】使用lambda函数在std::unordered_map中查找最小值【英文标题】：Usinglambdafunctiontofindaminimumvalueinastd::unordered_map【发布时间】：2019-01-3023:55:21【问题描述】：我正在尝试在地图中找到具有最小值的元素。例如，如果我的地图有(1,12.3),(... 查看详情

c++map怎样根据索引的内容查找到key

c++的std::map有两种方式可以实现依据索引的内容查找对应的键值使用std::map的find接口。例子如下：std::map<std::string,int>mapTest;std::map<std::string,int>::iteratorit=mapTest.find("index");if(it!=mapTest.end())returnit->second;使用std::map... 查看详情

Excel - 在同一个列表中查找最接近的值

】Excel-在同一个列表中查找最接近的值【英文标题】：Excel-Findingnearestvalueinsamelist【发布时间】：2016-07-1402:09:54【问题描述】：我有一个沿路的东西的清单，我正在寻找一个可以告诉我最近的东西在哪里的公式。考虑-RoadLocation(m)... 查看详情

部分匹配 std::map 的键

】部分匹配std::map的键【英文标题】：Partialmatchforthekeyofastd::map【发布时间】：2012-03-1002:59:33【问题描述】：我有一个std::map，我想使用子字符串搜索一个键。例如，我有以下代码：#include<iostream>#include<map>#include<string&g... 查看详情

ios NSPredicate 在 NSDictionary 中查找最接近的值

】iosNSPredicate在NSDictionary中查找最接近的值【英文标题】：iosNSPredicatetofindnearestvalueinNSDictionary【发布时间】：2014-08-0806:34:51【问题描述】：我有一个字典数组，如下所示：(key=1,value=40,key=4,value=50,key=8,value=60这些是这样的，for&g... 查看详情

使用 std::string 作为 std::map 的键

】使用std::string作为std::map的键【英文标题】：Usinganstd::stringasakeyforanstd::map【发布时间】：2011-06-2318:39:08【问题描述】：我想要一个std::map(int.NET4.0)。我们当然知道地图是一棵树，并且需要一个operator错误24错误C2676:二进制\'所以... 查看详情

在PHP中查找总和的最接近值的算法

】在PHP中查找总和的最接近值的算法【英文标题】：AlgorithmtofindnearestvaluesfortotalsuminPHP【发布时间】：2015-11-1315:14:41【问题描述】：我有一个total_sum变量（例如20.00）和数组，它不完全等于total_sum的组合，但非常接近：array=[array(8... 查看详情

使用 protobuf 对象作为 std::map 中的键

】使用protobuf对象作为std::map中的键【英文标题】：Usingprotobufobjectsaskeyinthestd::map【发布时间】：2019-04-0619:34:01【问题描述】：我是协议缓冲区概念的新手，如果我使用protobuf对象作为std::map中的键，我手头有一个任务可以解决。... 查看详情

在 Actionscript 3 中查找前 3 个最接近的目标

】在Actionscript3中查找前3个最接近的目标【英文标题】：Findtop3closesttargetsinActionscript3【发布时间】：2010-09-1414:36:06【问题描述】：我有一个点字符数组，我想获取任何字符并能够遍历该数组并找到前3个最近的（使用Point.distance）... 查看详情

C++：查找数组中最接近的值

】C++：查找数组中最接近的值【英文标题】：C++:Findtheclosestvaluesinanarray【发布时间】：2015-04-0308:15:58【问题描述】：我正在寻找一种漂亮的方法来在数组中搜索两个最接近的值并返回它们之间的差异。例如：如果我给出这些数字... 查看详情