4

我试图避免重新实现我自己笨拙的标准算法版本，因此正在使用标准库版本。由于我不是 C++ 专家，因此我谨慎行事并打开了完整的调试选项。

具体来说，我在valarray容器上使用二进制搜索。以下代码块似乎产生了正确的结果，并且valgrind没有抱怨。尽管如此，我确实觉得我在一个滑坡上，因为我不确定我正在做的事情是否真的被允许，或者我只是被编译器放过了。

有代表性的一段代码：

#include <iostream>
#include <valarray>
#include <algorithm>
#include <typeinfo>

using namespace std;

int main(){

 valarray<double> v(10);
 for (int i=0 ; i<10 ; ++i){
   v[i]=2. *i ; 
   cout<<v[i]<<"  ";
 }
 cout << "\n";

 double what=17;
 double* it=lower_bound(&v[0], &v[10],what) ; 

 cout<<it-&v[0]<<" "<<typeid(&v[0]).name()<<" ";
 cout<<typeid(it).name()<<" "<<typeid(it-&v[0]).name()<<"\n"; // ???

 int idx=it-&v[0];
 cout<<"v["<<idx<<"]="<<v[idx]<<"\n";
}

问题：

  1. 我在这里做的事情真的合法吗？
  2. 为什么两个指向 double 的指针之间的差异变成了 int？（与???评论一致）
  3. 类型转换的开销是多少？--- 我关心的是效率，因为这种功能将位于代码部分，占用超过 90% 的计算时间。
4

3 回答 3

2

  1. 您正在使用int索引到valarray. 这对示例有效，但不是一般情况。使用 anstd::size_t索引到 avalarray中。（对于std::vector普通数组也是如此。）

  2. 指向任何类型的两个指针之间的差异是未指定的整数类型，可能int或long总是足够小以适合std::ptrdiff_t.

  3. 哪个转换？

于 2011-03-09T01:14:07.727 回答
1

我相信这是所有已定义的行为，将继续适用于任何实现。查看 valarray 的各种文档，看起来它必须是合法的才能使所有其他事情::std::valarray成立。指向元素的裸指针应该保持完全有效，直到resize成员函数被调用或被valarray销毁。

唯一真正的问题是是否valarray需要连续保持其元素。我在一篇文章中找到了该问题的答案。我将在这里摘录：

是的，valarray 也使用连续存储。标准中的具体措辞是 ($26.3.2.3/3)：表达式 &a[i+j] == &a[i] + j 对于所有 size_t i 和 size_t j 的计算结果为真，使得 i+j 小于非常量数组 a 的长度。

当然，切片仍然不能直接与标准算法一起使用，尽管创建切片迭代器应该不会太难。制作一个双向的很容易，但要创建一个随机访问迭代器要困难得多（很多棘手的数学你必须完全正确）。

两个指针之间的差异变为（正如其他人所说）::std::ptrdiff_t。这将是不同平台上的不同类型。我在 64 位 Fedora 14 下使用 gcc，类型long适合我。这种“类型转换”没有开销。它甚至不是真正的转换。编译器只是做减法，就好像两个指针是普通的旧数字一样，结果是某种类型的普通旧数字。使用::std::ptrdiff_tfor 类型是为了确保使用的数字类型足够大，可以容纳系统中任意两个指针之间的差异。

于 2011-03-09T01:09:27.090 回答
0

这些it-&v[0]真的吓到我了..你的意思是it->v[0]？lower_bound 的返回值是 type valarray<double>::iterator，请用它代替double*! 所有其他取消参考问题将自动消失。例如你可以做*it，it++但你不能做it->v[0]，因为它不是一个指针而是一个迭代器。它很可能是一个v.end()-iterator 使您的所有尝试都使其值非法。

有关迭代器的更多信息：http ://www.cppreference.com/wiki/iterator/start

编辑：哦，现在我明白了，您正在使用可怕的指针算术！那太 C 了，我们不再这样做了；）

于 2011-03-09T01:14:42.910 回答