implicit transformation while calling std::adjacent_difference()

Question

I wanted to get a vector of distances between adjacent points in a vector:

struct Point { double x, y, z; } 

vector<double> adjacent_distances( vector<Point> points ) {
    ...
}

I thought that stl::adjacent_difference() would do the trick for me if I simply provided a function that finds the distance between 2 points:

double point_distance( Point a, Point b ) {
     return magnitude(a-b);  // implementation details are unimportant 
}

Thus, I was hoping that this would work,

vector<double> adjacent_distances( vector<Point> points ) 
{
    vector<double> distances;

    std::adjacent_difference( points.begin(), points.end(), 
                        std::back_inserter(distances), 
                        ptr_fun( point_distance ) );
    return distances; 
}

only to find that input and output vectors had to be of (practically) the same type because adjacent_difference() calls

 output[0] = input[0];            // forces input and output to be of same value_type 
 output[1] = op( input[1], input[0] ); 
 output[2] = op( input[2], input[1] ); 
 ....

which, sadly, is inconsistent with respect to how std::adjacent_find() works.

So, I had to convert my code to

double magnitude( Point pt );
Point  difference( Point a, Point b ); // implements b-a

vector<double> adjacent_distances( vector<Point> points ) 
{
    vector<Point> differences;

    std::adjacent_difference( points.begin(), points.end(), 
                        std::back_inserter(differences), 
                        ptr_fun( point_difference ) ); 


    vector<double> distances;

    std::transform( differences.begin(), differences.end(),
                        std::back_inserter(distances), 
                        ptr_fun( magnitude ) );

    return distances; 
}

NB: the first element of differences had to be removed for the function to behave correctly, but I skipped the implementation details, for brevity.

Question: is there a way I could achieve some transformation implicitly, so that I don't have to create the extra vector, and achieve a call to adjacent_difference() with input_iterator and output_iterator of different value_types ?

Answer 1

Probably this isn't so neat though, in this specific case, std::transform with 2 input sequences might meet the purpose. For example:

vector<double> adjacent_distances( vector<Point> points ) {
    if ( points.empty() ) return vector<double>();

    vector<double> distances(
      1, point_distance( *points.begin(), *points.begin() ) );

    std::transform( points.begin(), points.end() - 1,
                    points.begin() + 1,
                    std::back_inserter(distances), 
                    ptr_fun( point_distance ) );
    return distances; 
}

Hope this helps

Answer 2

Indeed that adjacent_difference algorithm is logically broken (why should be the difference of the same time of the elements? Why is the first output element equal to the first one instead of getting an output sequence one item shorter than the input one (way more logical)?

Anyway I don't understand why you are punishing yourself by using a functional approach with C++ where clearly the code is going to be harder to write, harder to read, slower to compile and not faster to execute. Oh.. and let's not talk about the kind of joke error message you are going to face if there is any error in what you type.

What is the bad part of

std::vector<double> distances;
for (int i=1,n=points.size(); i<n; i++)
    distances.push_back(magnitude(points[i] - points[i-1]));

?

This is shorter, more readable, faster to compile and may be even faster to execute.

EDIT

I wanted to check my subjective "shorter, more readable, faster to compile and may be faster to execute". Here the results:

~/x$ time for i in {1..10}
>   do
>     g++ -Wall -O2 -o algtest algtest.cpp
>   done

real    0m2.001s
user    0m1.680s
sys 0m0.150s
~/x$ time ./algtest

real    0m1.121s
user    0m1.100s
sys 0m0.010s
~/x$ time for i in {1..10}
>   do
>     g++ -Wall -O2 -o algtest2 algtest2.cpp
>   done

real    0m1.651s
user    0m1.230s
sys 0m0.190s
~/x$ time ./algtest2

real    0m0.941s
user    0m0.930s
sys 0m0.000s
~/x$ ls -latr algtest*.cpp
-rw-r--r-- 1 agriffini agriffini  932 2011-11-25 21:44 algtest2.cpp
-rw-r--r-- 1 agriffini agriffini 1231 2011-11-25 21:45 algtest.cpp
~/x$ 

The following is the accepted solution (I fixed what is clearly a brainfart of passing the vector of points by value).

// ---------------- algtest.cpp -------------
#include <stdio.h>
#include <math.h>
#include <functional>
#include <algorithm>
#include <vector>

using std::vector;
using std::ptr_fun;

struct Point
{
    double x, y;
    Point(double x, double y) : x(x), y(y)
    {
    }

    Point operator-(const Point& other) const
    {
        return Point(x - other.x, y - other.y);
    }
};

double magnitude(const Point& a)
{
    return sqrt(a.x*a.x + a.y*a.y);
}

double point_distance(const Point& a, const Point& b)
{
    return magnitude(b - a);
}

vector<double> adjacent_distances( const vector<Point>& points ) {
    if ( points.empty() ) return vector<double>();

    vector<double> distances(
      1, point_distance( *points.begin(), *points.begin() ) );

    std::transform( points.begin(), points.end() - 1,
                    points.begin() + 1,
                    std::back_inserter(distances),
                    ptr_fun( point_distance ) );
    return distances;
}

int main()
{
    std::vector<Point> points;
    for (int i=0; i<1000; i++)
        points.push_back(Point(100*cos(i*2*3.141592654/1000),
                               100*sin(i*2*3.141592654/1000)));

    for (int i=0; i<100000; i++)
    {
        adjacent_distances(points);
    }

    return 0;
}

Here is instead the explicit loop solution; it requires two include less, one function definition less and the function body is also shorter.

// ----------------------- algtest2.cpp -----------------------
#include <stdio.h>
#include <math.h>

#include <vector>

struct Point
{
    double x, y;
    Point(double x, double y) : x(x), y(y)
    {
    }

    Point operator-(const Point& other) const
    {
        return Point(x - other.x, y - other.y);
    }
};

double magnitude(const Point& a)
{
    return sqrt(a.x*a.x + a.y*a.y);
}

std::vector<double> adjacent_distances(const std::vector<Point>& points)
{
    std::vector<double> distances;
    if (points.size()) distances.reserve(points.size()-1);
    for (int i=1,n=points.size(); i<n; i++)
        distances.push_back(magnitude(points[i] - points[i-1]));
    return distances;
}

int main()
{
    std::vector<Point> points;
    for (int i=0; i<1000; i++)
        points.push_back(Point(100*cos(i*2*3.141592654/1000),
                               100*sin(i*2*3.141592654/1000)));

    for (int i=0; i<100000; i++)
    {
        adjacent_distances(points);
    }

    return 0;
}

Summary:

1. code size is shorter (algtest2.cpp is less than 76% of algtest.cpp)
2. compile time is better (algtest2.cpp requires less than 83% of algtest.cpp)
3. execution time is better (algtest2.cpp runs in less than 85% of algtest.cpp)

So apparently on my system (not hand-picked) I was right on all points except execution speed (the one with "maybe") where to get from slightly slower to substantially faster I had to call reserve on the result array. Even with this optimization the code is of course shorter.

I also think that the fact that this version is more readable is also objective and not an opinion... but I'd be happy to be proven wrong by meeting someone that can understand what the functional thing is doing and that cannot understand what the explicit one is doing instead.

Answer 3

Yes, this can be done, but not easily. I don't think it's worth the effort, unless you really need to avoid the copy.

If you really want to do this, you can try creating your own iterator that iterates over the vector<Point> and a wrapper around Point.

The iterator class will dereference to an instance of the wrapper class. The wrapper class should support operator - or your distance function, and it should store the distance. You should then implement an operator for implicit conversion to double, which will be invoked when adjacent_difference attempts to assign the wrapper to the vector<double>.

I don't have time to go into detail, so if anything is unclear, I'll check back later or someone else can try to explain better. Below is an example of a wrapper that does this.

 struct Foo { 
     Foo(double value) { d = value; } 
     operator double() { return d; } 
     double d; 
 };

 Foo sub(const Foo& a, const Foo& b) {
     return Foo(a.d - b.d);
 }

 vector<Foo> values = {1, 2, 3, 5, 8}; 
 vector<double> dist; 
 adjacent_difference(values.begin(), values.end(), back_inserter(dist), sub);

 // dist = {1, 1, 1, 2, 3}

Answer 4

This is maybe a bit dirty, but you could simply add

struct Point {
    double x,y,z;
    operator double() { return 0.0; }
};

or perhaps

struct Point {
    double x,y,z;
    operator double() { return sqrt(x*x + y*y + z*z); } // or whatever metric you are using
};

The effect being to set the first distance to 0, or the distance of the first point from the origin. However, I could imagine that you wouldn't want to pollute your Point struct with a rather arbitrary definition for conversion to double - in which case dauphic's wrapper is a cleaner solution.