如何从带容差自定义键的std::map中获取原始添加键？

我使用包含double类型标识符的自定义键myKey创建std::map，通过重载<和==运算符实现了键的容差匹配：使用与原始键a存在微小差异的键b，可成功检索a对应的值。但现在需要获取map中存储的原始键a，以比较a与b的差异，请问是否存在无需遍历整个map的实现方式？

原示例代码：

#include <iostream>
#include <map>

class myKey {

public:
  myKey(double x, double tolerance=0.5);
  double getX() const;
  bool operator<(const myKey& rhs) const;
  bool operator==(const myKey& rhs) const;

private:

  double _x;
  double _tolerance;

};

myKey::myKey(double x, double tolerance){
  _x = x;
  _tolerance = tolerance;
}

double myKey::getX() const {
  return _x;
}

bool myKey::operator<(const myKey& rhs) const {
  return (rhs._x - _x) > _tolerance;
}

bool myKey::operator==(const myKey& rhs) const {
  return std::abs(_x - rhs._x) < _tolerance;
}


// --------------------------------------------------

int main() {

  std::map<myKey, double> myMap;

  // 创建键并赋值
  myKey a = myKey(1.234, 0.5);
  double aval = 3.14159;
  myMap[a] = aval;

  double value_of_a_in_map = myMap[a];
  std::cout << "Checking myMap[a]: ";
  std::cout << "same value? " <<
    (aval == value_of_a_in_map) << std::endl;

  // 创建符合容差要求的新键b
  myKey b = myKey(1.345, 0.5);
  std::cout << "a == b? " << (a == b) << std::endl;

  // 通过b检索a对应的值
  double value_of_a_in_map_using_b = myMap[b];

  std::cout << "Checking myMap[b]: ";
  std::cout << "same value? " <<
    (aval == value_of_a_in_map_using_b) << std::endl;

  // 如何获取map中存储的原始键a？能否避免遍历整个map？

  // 当前可行但需要遍历的方式
  for (auto entry: myMap){
    myKey mapKey = entry.first;
    if (mapKey == b) {
      std::cout << "Found a ! x= " << mapKey.getX() << std::endl;
    }
  }

  return 0;
}

解决方案：分离存储键与搜索键 #

原代码的核心问题是myKey同时承担了存储标识和容差搜索两个职责，破坏了std::map依赖的严格弱序规则，导致无法通过查找直接定位原始键。正确的做法是拆分出两个独立的类，分别负责存储和搜索：

改进后的代码 #

#include <iostream>
#include <map>
#include <cassert>

// 仅用于存储的键类，保证精确比较
class myIDKey {
public:
  myIDKey(double x);
  myIDKey(){};
  double getX() const;

private:
  double _x;
};

myIDKey::myIDKey(double x){
  _x = x;
}

double myIDKey::getX() const {
  return _x;
}

// 精确比较，维护map的有序性
bool operator<(const myIDKey& lhs, const myIDKey& rhs) {
  return lhs.getX() < rhs.getX();
}

bool operator==(const myIDKey& lhs, const myIDKey& rhs) {
  return lhs.getX() == rhs.getX();
}

// 用于容差搜索的键类
class mySearchKey : public myIDKey {
public:
  mySearchKey(double x, double tolerance = 0.5);
  mySearchKey(){};
  double getTolerance() const;

private:
  double _tolerance;
};

mySearchKey::mySearchKey(double x, double tolerance): myIDKey(x) {
  _tolerance = tolerance;
}

double mySearchKey::getTolerance() const {
  return _tolerance;
}

// 自身的精确比较规则
bool operator<(const mySearchKey& lhs, const mySearchKey& rhs) {
  return lhs.getX() < rhs.getX();
}

bool operator==(const mySearchKey& lhs, const mySearchKey& rhs) {
  return lhs.getX() == rhs.getX();
}

// 搜索键与存储键的容差比较逻辑
bool operator<(const mySearchKey& lhs, const myIDKey& rhs) {
  return (lhs.getX() - rhs.getX()) < -lhs.getTolerance();
}

bool operator==(const mySearchKey& lhs, const myIDKey& rhs) {
  return std::abs(rhs.getX() - lhs.getX()) < lhs.getTolerance();
}

bool operator<(const myIDKey& lhs, const mySearchKey& rhs) {
  return (lhs.getX() - rhs.getX()) < -rhs.getTolerance();
}

bool operator==(const myIDKey& lhs, const mySearchKey& rhs) {
  return std::abs(rhs.getX() - lhs.getX()) < rhs.getTolerance();
}

// --------------------------------------------------

int main() {
  // 使用std::less<>作为比较器，支持跨类型键的比较
  std::map<myIDKey, double, std::less<>> myMap;

  myIDKey keyA(1.);
  myMap[keyA] = 1.;

  myIDKey keyB(2.);
  myMap[keyB] = 2.;

  mySearchKey searchKeyA = mySearchKey(1., 0.5);
  mySearchKey searchKeyA2 = mySearchKey(1.2, 0.5);

  // 通过搜索键直接定位原始存储键
  auto search1 = myMap.find(searchKeyA);
  if (search1 != myMap.end()) {
    assert(search1->first.getX() == keyA.getX());
    std::cout << "Search 1 successful" << std::endl;
    // 获取原始键值：search1->first.getX()
  } else {
    std::cout << "Search 1 failed" << std::endl;
  }

  auto search2 = myMap.find(searchKeyA2);
  if (search2 != myMap.end()) {
    assert(search2->first.getX() == keyA.getX());
    assert(search2->first.getX() != searchKeyA2.getX());
    std::cout << "Search 2 successful" << std::endl;
    // 对比原始键与搜索键的差异
    double originalX = search2->first.getX();
    double searchX = searchKeyA2.getX();
    std::cout << "原始键值：" << originalX << "，搜索键值：" << searchX << "，差异：" << std::abs(originalX - searchX) << std::endl;
  } else {
    std::cout << "Search 2 failed" << std::endl;
  }

  std::cout << "Done." << std::endl;
  return 0;
}

关键说明 #

1. 职责拆分：

   • myIDKey仅作为map的存储键，使用精确的double值比较，确保map内部红黑树的有序性和唯一性，完全符合std::map的底层要求。
   • mySearchKey专门用于容差搜索，继承自myIDKey并携带容差参数，通过重载与myIDKey的比较运算符实现模糊匹配逻辑。

2. 比较器选择：

   • 使用std::map<myIDKey, double, std::less<>>替代默认的std::less<myIDKey>，std::less<>会根据传入的参数类型自动调用对应的重载<运算符，支持mySearchKey与myIDKey之间的跨类型比较。

3. 直接获取原始键：

   • 调用myMap.find(searchKey)后，返回的迭代器指向map中的原始myIDKey条目，通过search->first即可直接获取存储的原始键，无需遍历整个map。

内容的提问来源于stack exchange，提问作者mivkov