使用std::equal_range查找经排列索引排序的向量元素失败问题

你的代码无法找到目标元素的核心问题在于比较逻辑错误，具体如下：

错误原因 #

1. 比较对象错误：你的compare结构体中，错误地将permutation[index]作为values的索引，而index本身就是permutation数组中的元素（即values的索引）。这导致实际比较的是values[permutation[index]]而非values[index]，完全偏离了匹配目标值的逻辑。
   • 例如，你要找的目标值6对应values[4]，而permutation[4]是5，values[5]是5，这会让程序错误地认为该元素对应的值是5而非6，自然无法匹配。
2. 冗余成员：compare结构体中的permutation成员完全多余，因为index已经是permutation数组中的元素，直接使用values[index]即可。

修正后的代码 #

#include <algorithm>
#include <iostream>
#include <vector>

struct compare {
  bool operator()(float value, int index) const { return value < values[index]; }
  bool operator()(int index, float value) const { return values[index] < value; }
  const std::vector<float>& values;
};

int main() {
  std::vector<float> values = { 1., 2., 2., 4., 6., 5. };
  std::vector<int> permutation = { 0, 1, 2, 3, 5, 4 };

  const auto p = std::equal_range(permutation.begin(), permutation.end(), 6., compare{values});
  for (auto i = p.first; i != p.second; ++i) {
    std::cout << *i << '\n';
  }
}

修正说明 #

• 移除了compare中冗余的permutation成员，直接通过index访问values的对应元素。
• 修正后，std::equal_range会正确匹配permutation数组中所有对应values值为6的元素，输出结果为4（即values中值为6的索引）。

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