How to implement a "InterpolatedVector"?

Question

I have a std::vector<double> and I need to interpolate its values. For example with only 1 intermediate value and given a vector filled with

1 / 2 / 3 / 4

I want to access the following values

1 / 1.5 / 2 / 2.5 / 3 / 3.5 / 4

Of course I do not have to store this intermediate values (simple linear interpolation and I do not have to read them too often), so I wrote this simple class:

typedef std::vector<double> DVector;
class InterpolatedVector {
public:
    InterpolatedVector(const DVector& v,int steps) : v(v),steps(steps){}
    double at(int i){
        int j = i%steps;
        int k = (int)i/steps;
        if (i==0){return v[0];}
        else if (i==v.size()*steps){return v.back();}
        else {return  ((steps-j)*v[k] + j*v[k+1])/steps;}
    }
    int size(){return steps*(v.size()-1) + 1;}
private:
    DVector v;
    int steps;
};

It works fine and I get (almost) what I want. However, this "container" I cannot use with the std::algorithms and I do not have iterators for it. (Of course, I cannot write the intermediate values, but at least when it is about reading, I would like to use the algorithms.) I should mention that I am still lacking a bit of understanding on iterators and the like.

How should I implement this "InterpolatedVector", so that I can do things like

std::accumulate(/* passing Interpolated iterators? */ );

?

Jerry Coffin · Accepted Answer · 2015-04-01T13:49:08.813

Given that you already have the code to handle the indexing itself, wrapping that as an iterator is pretty easy. If you'll forgive me, I'm also going to make it a bit more generic.

#include <vector>
#include <iterator>

template <class T>
class InterpolatedVector {
    typedef std::vector<T> DVector;
public:
    InterpolatedVector(const DVector& v,int steps) : v(v),steps(steps){}
    T at(int i){
        int j = i%steps;
        int k = (int)i/steps;
        if (i==0){return v[0];}
        else if (i==v.size()*steps){return v.back();}
        else {return  ((steps-j)*v[k] + j*v[k+1])/steps;}
    }
    int size(){return steps*(v.size()-1) + 1;}

    class iterator : public std::iterator < std::random_access_iterator_tag, T > {
        InterpolatedVector *vec;
        int index;
    public:
        iterator(InterpolatedVector &d, int index) : vec(&d), index(index) {}
        iterator &operator++() { ++index; return *this; }
        iterator operator++(int) { iterator tmp{ *vec, index }; ++index; return tmp; }
        iterator operator+(int off) { return iterator(*vec, index + off); }
        iterator operator-(int off) { return iterator(*vec, index - off); }
        value_type operator*() { return (*vec).at(index);   }
        bool operator!=(iterator const &other) { return index != other.index; }
        bool operator<(iterator const &other) { return index < other.index; }
    };

    iterator begin() { return iterator(*this, 0); }
    iterator end() { return iterator(*this, size()); }
private:

    DVector v;
    int steps;
};

...and a quick bit of demo code to test it out:

#include <iostream>

int main() {
    std::vector<double> d{ 1, 2, 3, 4 };
    InterpolatedVector<double> id(d, 2);

    std::copy(id.begin(), id.end(), std::ostream_iterator<double>(std::cout, "\t"));
    std::cout << "\n";

    std::vector<int> i{ 0, 5 };
    InterpolatedVector<int> ii(i, 5);

    std::copy(ii.begin(), ii.end(), std::ostream_iterator<int>(std::cout, "\t"));
}

Output:

1       1.5     2       2.5     3       3.5     4
0       1       2       3       4       5

Of course, some algorithms still won't be able to do much with this sort of "collection". Trying to feed an interpolated collection to std::sort wouldn't make much sense (you'd clearly need to sort the underlying container). As long as the algorithm only needs to read the data, this should be fine though.

Thanks for your quite complete solution. It really helped me a lot. I just have one comment: I had to change `tmp{*vec,index}` to `tmp(*vec,index)` because I cannot use C++11. Forgot to mention that in the question. (And actually now I wonder if there is any difference other than the brackets). And one question: In the same method (overload of ++) I get a warning for returning a reference to a local variable `tmp`. Is this a problem here? Isnt `tmp` destroyed when the method returns? — 463035818_is_not_an_ai, Apr 01 '15 at 13:46
@tobi303: Oops--yes, the postfix ++ (i.e., `operator++(int)` ) should return a value not a reference. Thanks for pointing it out. — Jerry Coffin, Apr 01 '15 at 13:51
I did some reading and finally I understand, why loops with iterators usually read `for(Iterator it=......;++it)` and not `...it++)`. So eventually I could learn something from your mistake :) — 463035818_is_not_an_ai, Apr 01 '15 at 14:11

score 1 · Answer 2 · answered Mar 20 '15 at 16:07

1

If you want to use it with algorithms, fill a vector with the intermediate values. This will be much simpler.

answered Mar 20 '15 at 16:07

chmike

20,922
21
83
106

Yes. I was going to suggest. std::transform or similar. – Robinson Mar 20 '15 at 16:08
hm.. thanks for the fast answer. If this is the easiest way, I will do it like that. However, to get a better understanding of iterators, I would like to see a solution without filling a new vector, or at least some good reasons why this would be not a good idea. – 463035818_is_not_an_ai Mar 20 '15 at 16:14

How to implement a "InterpolatedVector"?

2 Answers2

Linked