c++ - 为什么 `std::sort` 会尝试比较不在输入列表中的值？

Question

我正在使用此处说明的方法 How to obtain the index permutation after the sorting为了找到对数组元素进行排序的索引排列。

奇怪的是，在某些情况下我会遇到段错误。追溯问题，我发现 std::sort 尝试调用具有有效范围之外的索引的比较器。我确信总是在调用 std::sort 之前，index 数组填充了正确的索引(即 0 到 data .size()-1).

有趣的是，在我的例子中，data 的长度始终为 32 并且我意识到比较器是用第一个参数 145 调用的(第二个始终在 0 到 31 范围内)。

知道为什么会发生这种情况吗？

代码如下:

class compare {
      private:        
         const double* list;
      public:
         compare(const double* d): list(d) {}
         bool operator()(const size_t& a, const size_t& b) {
               // indeed I observe that this function gets called with a = 145 and b in 
               // the range of 0 to 31

              return (list[a] < list[b]);
         }
  };

std::vector<double> data(32);
std::vector<size_t> idx(32);

compare cmp(&data[0]);
size_t i;

// populate the data array ... for example:
for (i = 0; i < 32; i++)
    data[i] = 1.0 * (rand() % 100) / 50; 

for (i = 0; i < 32; i++)
  idx[i] = i;
std::sort(idx.begin(), idx.end(), cmp);

Answer 1

我无法重现您观察到的内容。这是您的代码的清理版本，似乎可以正常工作(gcc 和 clang)。

#include <vector>
#include <algorithm>
#include <stdexcept>

#include <cstdlib>
#include <cstdio>

#define LSIZE 32

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

class compare 
{
private:        
    const double* ptr;

public:

    compare(): ptr(0) {}
    compare( const double* d ): ptr(d) {}

    bool operator()( size_t a, size_t b ) 
    {
        if ( ptr == 0 ) throw std::runtime_error("Null pointer to data.");
        if ( a >= LSIZE || b >= LSIZE ) throw std::out_of_range("Index out of range.");

        // Uncomment to show the comparisons:
        // printf( "Comparing data[%lu] (%.2f) and data[%lu] (%.2f)\n", 
        //      a, ptr[a], b, ptr[b] );

        return ptr[a] < ptr[b];
    }
};

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

int main()
{
    std::vector<double> data(LSIZE);
    std::vector<size_t> idx(LSIZE);

    for ( unsigned i=0; i<LSIZE; ++i )
    {
        idx[i]  = i;
        data[i] = 1.0 * (rand() % 100) / 50; 
    }

    std::sort( idx.begin(), idx.end(), compare( data.data() ) );
}