使用一个小的重载助手,您可以使用std::lower_bound
:Live on Coliru
列出的第一个匹配项将是您查找的匹配项(std::pair<>
已按顺序排列(first,right)
,升序排列)。
在这种情况下,助手是:
struct ByKeyFirst final { int value; };
inline bool operator<(Map::value_type const& v, ByKeyFirst target) {
return v.first.first < target.value;
}
如您所见,唯一“增加的复杂性”是检查是否找到了匹配项,但效率应该没问题。而且您始终可以将复杂性隐藏在(可单元测试的)助手中:
Map::const_iterator byKeyFirst(Map const& map, int target)
{
auto const e = end(map);
auto lbound = lower_bound(begin(map), e, ByKeyFirst { target });
if (lbound != e && lbound->first.first == target)
return lbound;
return e;
}
现在查找代码变得仅仅是:
int main()
{
const Map myMap {
{ { 1, 200 }, {} },
{ { 1, 202 }, {} },
{ { 2, 198 }, {} },
{ { 2, 207 }, {} },
};
auto match = byKeyFirst(myMap, 2);
if (end(myMap) != match)
std::cout << "Matching key: (" << match->first.first << "," << match->first.second << ")\n";
}
完整演示
#include <map>
#include <tuple>
#include <limits>
using namespace std;
struct A {};
using Pair = pair<int,int>;
using Map = map<Pair, A>;
namespace /*anon*/
{
struct ByKeyFirst final { int value; };
inline bool operator<(Map::value_type const& v, ByKeyFirst target) { return v.first.first < target.value; }
Map::const_iterator byKeyFirst(Map const& map, int target)
{
// you can just find the first match, Pair is already sorted by `first`, then `second`:
auto const e = end(map);
auto lbound = lower_bound(begin(map), e, ByKeyFirst { target });
if (lbound != e && lbound->first.first == target)
return lbound;
return e;
}
}
#include <iostream>
int main()
{
const Map myMap {
{ { 1, 200 }, {} },
{ { 1, 202 }, {} },
{ { 2, 198 }, {} },
{ { 2, 207 }, {} },
};
auto match = byKeyFirst(myMap, 2);
if (end(myMap) != match)
std::cout << "Matching key: (" << match->first.first << "," << match->first.second << ")\n";
}