如何从有序集合中返回最近的元素？

Question

我有一个向量，其中包含一些浮点值彼此合理，并根据某些功能排序。例如，

double foo(double x) 
{ 
    return 199.1*x; 
} 
double x = 3000000.3157; 
double y = x + DBL_EPSILON; 

std::vector<double> s { y,y+10}; 
std::sort(s.begin(),s.end(),[](double x,double y) { return foo(x) < foo(y) ;}); 

现在有人有一个关键是贴着一张我在s，如x。在lambda时代，都有自己的小功能来进行搜索，比如

std::cout<<std::distance(s.begin(),std::lower_bound(s.begin(),s.end(),x, 
[] (double x,double y) { return foo(x) < foo(y);}))<<std::endl; 
    std::cout<<std::distance(s.begin(),std::lower_bound(s.begin(),s.end(),x, 
[] (double x,double y) { double f1 = foo(x); 
         double f2 = foo(y); 
         return f1 < f2;}))<<std::endl; 

，并得到不同的位置（以及相应的值有很大的不同）。

注视使用，它一出现，它们与发现了一个关键k

• 最近的元素从有序集中占尽天时地利的浮点值。
• 的比率，r，其（理想地应该是[0,1]）附连到连续值x1 & x2这样一个函数f(x1,x2,r)的返回值是大约等于k。

它们都看起来像相关，并且与插值有关。我如何实现它们？

注：

在下面

double f1 = foo(x); 
double f2 = foo(y); 
bool l = foo(x) < foo(y); 
std::cout<<std::boolalpha<<(f1<f2)<< " "<<l<<" "<<(f1 == f2) << std::endl; 
std::cout << std::boolalpha << (foo(x) < foo(y)) << " "<< (foo(y) < foo(x)) 
      << " "<<(foo(x) == foo(y))<<std::endl; 
std::cout << std::boolalpha << std::isless(foo(x) , foo(y)) 
      << " "<< std::isless(foo(y) , foo(x)) <<std::endl; 

我一个X86机器上得到输出，GCC为

false true true 
true true false 
false false 

短代码，而我的猜测是，GCC做更高的精度（80bit的）在飞行，除非我强迫它存储结果，导致不同的结果l & (f1<f2)（导致上述问题）。我也有兴趣知道为什么foo(x) < foo(y)和foo(y) < foo(x)都说true！

Answer 1

这两句话一事无成，因为DBL_EPSILON比1ulp这些数字较小：

double x = 3000000.3157; 
double y = x + DBL_EPSILON; 

可以肯定，我印双方x和y的十六进制表示，得到了以下几点：

4146E3602868DB8C 
4146E3602868DB8C 

当我通过几个不同版本的G ++（4.4.5和4.8.0）在（-O3）和off（无标志）优化的情况下在问题底部运行示例时，我得到以下输出：

false false true 
false false true 
0 0 

我怀疑你所看到的行为是正是你推测的原因：你的编译器的中间结果承载更高的精度和流血通过对这些比较。

您使用的是哪种版本的编译器，并且应用程序中的其他代码是否可以调整任何舍入模式？你使用什么编译标志？

---

编辑1

我能够通过优化重新编译过和32位模式下重现你的行为。在这种模式中，我看到，编译叶foo结果浮点堆栈：

_Z3food: 
.LFB1053: 
    .cfi_startproc 
    pushl %ebp # 
    .cfi_def_cfa_offset 8 
    .cfi_offset 5, -8 
    movl %esp, %ebp #, 
    .cfi_def_cfa_register 5 
    subl $8, %esp #, 
    movl 8(%ebp), %eax # x, tmp61 
    movl %eax, -8(%ebp) # tmp61, x 
    movl 12(%ebp), %eax # x, tmp62 
    movl %eax, -4(%ebp) # tmp62, x 
    fldl -8(%ebp) # x 
    fldl .LC0 # 
    fmulp %st, %st(1) #, 
    leave 

这表明，这是在i386 ABI的怪癖。为了测试这个理论，我更仔细地观察了i386 ABI。在page 38 of this PDF（又名“3-12页”通过内部页码），我发现什么是可能的确凿证据：

%st(0)浮点返回值出现在 浮顶点寄存器堆栈; 寄存器中的单精度值或双精度值的表示没有区别。如果该函数没有返回浮点值，则该寄存器必须为空。在G 进入功能之前，该寄存器必须为空。

它接着说几段后：出现在Intel387 寄存器堆栈的顶部

一个浮点返回值。然后调用者必须从 Intel387堆栈中删除该值，即使它不使用该值。 方未能履行其义务导致未定义的程序行为。标准调用序列不包括检测此类故障的任何方法，也不包括检测返回值类型不匹配的方法。因此， 用户必须正确声明所有功能。 在 浮点寄存器中，单精度值，双精度值或扩展精度值的表示在 中没有区别。

进一步搜索到第3-27页（PDF第53页）和第3-28页（PDF第54页）给出了以下令人困惑的曲折。图3-30中的表格表明初始舍入模式为“53位（双精度）”，这就是进程初始化时的模式。

它接着进一步给下一个页面上的以下警告：

初始浮点状态应该小心被改变。特别是，如果精度控制设置为小于53位，许多浮点例程可能会产生未定义的行为 行为。 _fpstart例程（见第6章）将精度控制更改为64位，并设置要求提供的所有异常。这是符合ANSI C标准和IEEE 754 浮点标准所需的默认状态 。

couple甲reference S于净指示的Linux确实设置的x87至扩展精度（至少在32位ABI）。

---

编辑2

看来扩展精度的确是罪魁祸首。我添加以下代码以测试情况下，as suggested by this page：

void set_fpu (unsigned int mode) 
{ 
     asm ("fldcw %0" : : "m" (*&mode)); 
} 

// ... 

set_fpu(0x27F); 

随着这些行添加，测试用例返回我与64位ABI看到了同样的值。

因此，假设您在Linux下编译32位程序，这似乎是您看到奇怪的比较和排序结果的原因。

你可以重新运行你的排序和FPU设置为53位精度的搜索代码，如上所述，看看是否能解决你看到的两个lambda表达式之间的差异？