Using standard C ++ library algorithms with valarray

Question

I try to avoid overestimating my own awkward versions of standard algorithms and thus play with standard versions of libraries. Since I am not an expert in C ++, I proceed with caution and all debugging options are enabled.

In particular, I use binary search in a valarray container. The following code seems to block the correct results, and valgrind not complaining. However, I feel like on a slippery slope, as I'm not sure if what I'm doing is really allowed, or if the compiler just releases me.

Representative part of the code:

 #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"; } 

Questions:

• Is this really legal?
• How is it that the difference between two pointers to double becomes int? (in line with comment ??? )
• What is type conversion overhead? --- I'm interested in efficiency, since this function will sit in that part of the code that takes up more than 90% of the calculation time.

Answer 1

• You use int to index in valarray . This is true for an example, but not in general. Use std::size_t for indexing in valarray . (The same goes for std::vector and regular arrays.)

• The difference between two pointers to any type is of an undefined integer type, probably int or long and is always small enough to match std::ptrdiff_t .

• What kind of conversion?

Answer 2

I believe that this is all defined behavior that will continue to work on any implementation. If you look at the documentation for valarray, it looks like it should be legal so that all other things about ::std::valarray saved. Bare pointers to elements must remain valid until a resize member function is called or valarray is destroyed.

The only real question is whether valarray is valarray in order to hold its elements contiguously or not. And I found the answer to this question in a post . I will stand it here:

Yes, valarray also uses adjacent storage locations. Specific wording from the standard ($ 26.3.2.3 / 3): the expression & a [i + j] == & a [i] + j evaluates to true for all size_t i and size_t j that i + j is less than the length of the variable array a.

Of course, fragments still cannot be used directly with standard algorithms, although creating a slice iterator should not be too complicated. It would be fairly easy to do bidirectional, but much harder (a lot of the complicated math you need to get exactly) to create a random access iterator.

The difference between the two pointers becomes (as someone else said) ::std::ptrdiff_t . It will be a different type on different platforms. I use gcc under 64-bit Fedora 14, and the type is long for me. There is no overhead in this type conversion. This is not even a conversion. The compiler simply does the subtraction, as if the two pointers were prime old numbers, and the result was a plain old number of some type. Using ::std::ptrdiff_t for a type is to make sure that the type of the number used is large enough to hold the difference between any two pointers in the system.

Answer 3

These it-&v[0] really scare me .. did you mean it->v[0] ? The return value lower_bound is of type valarray<double>::iterator , use double* instead! All other reinstallation problems will disappear automatically. For example, you can do *it and it++ , but you cannot do it->v[0] , because this is not a pointer, but an iterator. It can very well be v.end() -iterator, which makes all your certificates invalid.

Additional information about iterators: http://www.cppreference.com/wiki/iterator/start

Edit: Oh, now I see you are using scary pointer arithmetic! This is sooo C, we do not do this anymore;)