Re: Non-container Iterators

Discussion in 'C++' started by Leslie Sanford, Jul 25, 2008.

  1. "Daniel T." wrote:
    > "Leslie Sanford" wrote:
    >
    >> My area of programming is DSP. I write things like filters, oscillators,
    >> envelopes, etc. I've been looking at STL iterators, and what's struck me
    >> is that if I can find ways to model my code using STL's iterator
    >> conventions, I could possibly make my code more economic while
    >> probably losing little to no efficiency.

    >
    > Then you might find this interesting:
    >
    > class fibonacci: public std::iterator< std::forward_iterator_tag, int >


    <snip>

    Yes, indeed. That is very interesting.

    <snip>

    >> I need to keep track of the phase. The phase is state that needs to
    >> persist across iterations. This means that I need to give the iterator a
    >> pointer to the phase variable when I create it so that as it's iterating,
    >> it's also modifying the phase variable. Something like:
    >>
    >> // Inside my Oscillator class somewhere:
    >> it = PhaseIterator it(&phase, increment);
    >>
    >> // Inside the PhaseIterator class:
    >> PhaseIterator &operator++()
    >> {
    >> *phase += increment;
    >>
    >> if(phase >= 1.0f)
    >> {
    >> phase -= 1.0f;
    >> }
    >>
    >> return *this;
    >> }
    >>
    >>
    >> This works, but it means that I can only use one phase iterator at a
    >> time.

    >
    > Not if you put 'phase' inside the iterator. Then you can give two
    > iterators the same phase and increment and advance each of them a
    > different amount, and they will each be at a different spot in the
    > "container".


    Understood.

    > The key is to provide a sentinel iterator. In your case, the sentinel
    > can be a PhaseIterator that has an increment of 0.


    In this case, there is no sentinel iterator as an oscillator, which a phase
    accumulator drives, can cycle indefinitely, a kind of circular buffer, I
    suppose.

    Is it acceptable for an iterator to never reach an "end"? I would have
    another way for testing for the end of the loop, specifically the end of the
    buffer that I'm filling. I should be able to increment the phase iterator
    indefinitely.

    while(first != last)
    {
    *first = *phase;

    phase++;
    first++;
    }

    Since (triple) posting, I've been giving this approach some thought, and I
    was wondering if a Generator would be a more appropriate model than an
    Iterator to represent a phase accumulator.

    http://www.sgi.com/tech/stl/Generator.html

    class PhaseAccumulator
    {
    public:
    typedef float result_type;

    private:
    float phase;
    float increment;

    public:
    PhaseAccumulator(float phase, float increment)
    {
    this->phase = phase;
    this->increment = increment;
    }

    result_type operator()()
    {
    phase += increment;

    if(phase >= 1.0f)
    {
    phase -= 1.0f;
    }

    return phase;
    }
    };

    I can have a Square waveform represented as a unary function:

    typedef std::unary_function<float, float> WaveShapeBase;

    struct Square : public WaveShapeBase
    {
    result_type operator()(argument_type phase) const
    {
    assert(phase >= 0.0f && phase < 1.0f);

    return phase < 0.5f ? -1.0f : 1.0f;
    }
    };

    And use both in a loop to fill a buffer:

    class Oscillator
    {
    PhaseAccumulator phase;
    Square wave;

    public:
    // Stuff...

    void Process(float *first, float *last)
    {
    while(first != last)
    {
    *first = wave(phase());

    first++;
    }
    }
    }

    Maybe this is a more appropriate approach given the concepts involved?
    Leslie Sanford, Jul 25, 2008
    #1
    1. Advertising

  2. Leslie Sanford

    mlimber Guest

    On Jul 24, 11:18 pm, "Leslie Sanford" <>
    wrote:
    > In this case, there is no sentinel iterator as an oscillator, which a phase
    > accumulator drives, can cycle indefinitely, a kind of circular buffer, I
    > suppose.
    >
    > Is it acceptable for an iterator to never reach an "end"? I would have
    > another way for testing for the end of the loop, specifically the end of the
    > buffer that I'm filling. I should be able to increment the phase iterator
    > indefinitely.
    >
    > while(first != last)
    > {
    >     *first = *phase;
    >
    >     phase++;
    >     first++;
    >
    > }
    >
    > Since (triple) posting, I've been giving this approach some thought, and I
    > was wondering if a Generator would be a more appropriate model than an
    > Iterator to represent a phase accumulator.
    >
    > http://www.sgi.com/tech/stl/Generator.html
    >
    > class PhaseAccumulator
    > {
    > public:
    >     typedef float result_type;
    >
    > private:
    >     float phase;
    >     float increment;
    >
    > public:
    >     PhaseAccumulator(float phase, float increment)
    >     {
    >         this->phase = phase;
    >         this->increment = increment;
    >     }
    >
    >     result_type operator()()
    >     {
    >         phase += increment;
    >
    >         if(phase >= 1.0f)
    >         {
    >             phase -= 1.0f;
    >         }
    >
    >         return phase;
    >     }
    >
    > };
    >
    > I can have a Square waveform represented as a unary function:
    >
    > typedef std::unary_function<float, float> WaveShapeBase;
    >
    > struct Square : public WaveShapeBase
    > {
    >     result_type operator()(argument_type phase) const
    >     {
    >         assert(phase >= 0.0f && phase < 1.0f);
    >
    >         return phase < 0.5f ? -1.0f : 1.0f;
    >     }
    >
    > };
    >
    > And use both in a loop to fill a buffer:
    >
    > class Oscillator
    > {
    >     PhaseAccumulator phase;
    >     Square wave;
    >
    >     public:
    >         // Stuff...
    >
    >     void Process(float *first, float *last)
    >     {
    >         while(first != last)
    >         {
    >             *first = wave(phase());
    >
    >             first++;
    >         }
    >     }
    >
    > }
    >
    > Maybe this is a more appropriate approach given the concepts involved?


    Since the phase can't "end" in any meaningful sense, a generator may
    be a more appropriate design pattern. Pseudo-random number generators
    (eventually) loop, too, and they're commonly used as generator
    functors. That being said, there certainly are generator-style
    iterators out there, e.g. boost::counting_iterator:

    http://www.boost.org/doc/libs/1_35_0/libs/iterator/doc/counting_iterator.html

    Using something like that approach, your oscillator class might look
    like:

    void Oscillator::process(float *begin, float *end)
    {
    // Generate
    std::transform(
    phase.begin(),
    phase.end( std::distance(begin,end) ),
    begin,
    Square );
    }

    I assume the phase has been given counting_iterator-like support,
    where the end() function takes a parameter telling it how many times
    to increment. Note also that you could convert your square wave
    functor to an ordinary function with the signature float Square(float)
    since it doesn't take any constructor parameters or maintain mutable
    state. The member variable for that functor is overkill.

    The down-side to this approach is that the use of std::transform()
    with a generator-style iterator to generate is takes some thinking,
    and one of our goals for code is (or, should be) to make it readable.
    The names of the standard functions are intended to communicate your
    meaning rather than obscure it (cf. http://www.ddj.com/cpp/184401446),
    but generator-style iterators cut against the grain in a circumstance
    like this.

    A generator approach: Using functional composition [let's call ours
    my_compose(f,g) = f(g())], whose implementation is relatively
    straightforward and similar to the common extension to the STL (e.g.,
    http://www.sgi.com/tech/stl/unary_compose.html), one can make this
    clearer on first reading:

    std::generate( begin, end, my_compose( Square, phase ) );

    Now fewer tricks are being played, and its meaning should be clearer
    to someone reading your code down the line (which could be you).

    Cheers! --M
    mlimber, Jul 25, 2008
    #2
    1. Advertising

  3. Leslie Sanford

    Daniel T. Guest

    On Jul 24, 11:18 pm, "Leslie Sanford" <>
    wrote:
    > "Daniel T." wrote:
    > > "Leslie Sanford" wrote:

    >
    > >> My area of programming is DSP. I write things like filters, oscillators,
    > >> envelopes, etc. I've been looking at STL iterators, and what's struck me
    > >> is that if I can find ways to model my code using STL's iterator
    > >> conventions, I could possibly make my code more economic while
    > >> probably losing little to no efficiency.

    >
    > > Then you might find this interesting:

    >
    > > class fibonacci: public std::iterator< std::forward_iterator_tag, int >

    >
    > <snip>
    >
    > Yes, indeed. That is very interesting.
    >
    > <snip>
    >
    >
    >
    >
    >
    > >> I need to keep track of the phase. The phase is state that needs to
    > >> persist across iterations. This means that I need to give the iterator a
    > >> pointer to the phase variable when I create it so that as it's iterating,
    > >> it's also modifying the phase variable. Something like:

    >
    > >> // Inside my Oscillator class somewhere:
    > >> it = PhaseIterator it(&phase, increment);

    >
    > >> // Inside the PhaseIterator class:
    > >> PhaseIterator &operator++()
    > >> {
    > >>     *phase += increment;

    >
    > >>      if(phase >= 1.0f)
    > >>     {
    > >>         phase -= 1.0f;
    > >>     }

    >
    > >>     return *this;
    > >> }

    >
    > >> This works, but it means that I can only use one phase iterator at a
    > >> time.

    >
    > > Not if you put 'phase' inside the iterator. Then you can give two
    > > iterators the same phase and increment and advance each of them a
    > > different amount, and they will each be at a different spot in the
    > > "container".

    >
    > Understood.
    >
    > > The key is to provide a sentinel iterator. In your case, the sentinel
    > > can be a PhaseIterator that has an increment of 0.

    >
    > In this case, there is no sentinel iterator as an oscillator, which a phase
    > accumulator drives, can cycle indefinitely, a kind of circular buffer, I
    > suppose.
    >
    > Is it acceptable for an iterator to never reach an "end"? I would have
    > another way for testing for the end of the loop, specifically the end of the
    > buffer that I'm filling. I should be able to increment the phase iterator
    > indefinitely.
    >
    > while(first != last)
    > {
    >     *first = *phase;
    >
    >     phase++;
    >     first++;
    >
    > }
    >
    > Since (triple) posting, I've been giving this approach some thought, and I
    > was wondering if a Generator would be a more appropriate model than an
    > Iterator to represent a phase accumulator.
    >
    > http://www.sgi.com/tech/stl/Generator.html
    >
    > class PhaseAccumulator
    > {
    > public:
    >     typedef float result_type;
    >
    > private:
    >     float phase;
    >     float increment;
    >
    > public:
    >     PhaseAccumulator(float phase, float increment)
    >     {
    >         this->phase = phase;
    >         this->increment = increment;
    >     }
    >
    >     result_type operator()()
    >     {
    >         phase += increment;
    >
    >         if(phase >= 1.0f)
    >         {
    >             phase -= 1.0f;
    >         }
    >
    >         return phase;
    >     }
    >
    > };
    >
    > I can have a Square waveform represented as a unary function:
    >
    > typedef std::unary_function<float, float> WaveShapeBase;
    >
    > struct Square : public WaveShapeBase
    > {
    >     result_type operator()(argument_type phase) const
    >     {
    >         assert(phase >= 0.0f && phase < 1.0f);
    >
    >         return phase < 0.5f ? -1.0f : 1.0f;
    >     }
    >
    > };
    >
    > And use both in a loop to fill a buffer:
    >
    > class Oscillator
    > {
    >     PhaseAccumulator phase;
    >     Square wave;
    >
    >     public:
    >         // Stuff...
    >
    >     void Process(float *first, float *last)
    >     {
    >         while(first != last)
    >         {
    >             *first = wave(phase());
    >
    >             first++;
    >         }
    >     }
    >
    > }
    >
    > Maybe this is a more appropriate approach given the concepts involved?


    That sounds like it would work. Then your process function can be
    replaced by the generate algorithm.

    float arr[20];
    generate( arr, arr + 20, PhaseAccumulator(0, 0.3) );

    or better:

    vector< float > arr;
    generate_n( back_inserter( arr ), 20, PhaseAccumulator(0, 0.3) );

    But if you make a powerful enough PhaseAccumulator iterator, you won't
    *need* to fill the array with values, you can use the iterator
    directly over the calculated container.
    Daniel T., Jul 25, 2008
    #3
  4. "mlimber" wrote:
    >
    > A generator approach: Using functional composition [let's call ours
    > my_compose(f,g) = f(g())], whose implementation is relatively
    > straightforward and similar to the common extension to the STL (e.g.,
    > http://www.sgi.com/tech/stl/unary_compose.html), one can make this
    > clearer on first reading:
    >
    > std::generate( begin, end, my_compose( Square, phase ) );


    I like this approach; the idea of function composition is appealing. The
    problem is handling state. The waveform function object is stateless, a true
    function. However, the phase accumulator has state, specifically the value
    of its phase. Say I have the following:

    void Oscillator::process(float *begin, float *end)
    {
    // Assumes a phase member variable.
    std::generate(begin, end, my_compose(Square(), phase);
    }

    Each time Process is called the phase needs to pick up from where it left
    off with the previous call. However, 'phase' is passed in by value, so the
    phase accumulator that's actually getting advanced by generate is a copy of
    the original. The end result is that each time Process is called, phase
    starts at the same place.

    I see a couple of ways around this. Design the phase accumulator so that it
    takes a pointer to the actual phase variable:

    // Inside the Oscillator class..

    // Member variable.
    float phase;

    //...

    void Oscillator::process(float *begin, float *end)
    {
    std::generate(begin, end, my_compose(Square(),
    PhaseAccumulator(&phase));
    }

    This ensures that the phase value that's getting incremented persists
    between calls since the PhaseAccumulator is incrementing the pointer
    variable.

    I suppose this solution is ok.

    Another approach is to somehow update the phase accumulator after generate
    has done its job:

    void Oscillator::process(float *begin, float *end)
    {
    MyCompose<Square, PhaseAccumulator> mc(Square(), phase);

    std::generate(begin, end, mc);

    // Assumes our custom compose template exposes the generator function
    object.
    phase = mc.generator;
    }

    This works as well. Another way is to explicitely tell the generate function
    to treat the phase accumulator object as a reference, but then I'm pretty
    sure I'd lose inlining in that case. Things would start to look ugly at that
    point anyway.

    Also, we can forego the convenience of using generate and simply write the
    loop ourselves using the same member variables:

    void Oscillator::process(float *first, float *last)
    {
    while(first != last)
    {
    // Assumes phase and wave are member variables.
    *first = wave(phase());

    first++;
    }
    }
    Leslie Sanford, Jul 25, 2008
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. moggous phar
    Replies:
    1
    Views:
    374
    Gianni Mariani
    Oct 15, 2004
  2. Marcin Kaliciñski

    Iterators and reverse iterators

    Marcin Kaliciñski, May 8, 2005, in forum: C++
    Replies:
    1
    Views:
    475
    Kai-Uwe Bux
    May 8, 2005
  3. Patrick Kowalzick

    Iterators over nested STL container

    Patrick Kowalzick, Aug 3, 2005, in forum: C++
    Replies:
    2
    Views:
    371
    Chris Theis
    Aug 3, 2005
  4. Leslie Sanford

    Non-container Iterators

    Leslie Sanford, Jul 24, 2008, in forum: C++
    Replies:
    0
    Views:
    264
    Leslie Sanford
    Jul 24, 2008
  5. , India
    Replies:
    10
    Views:
    1,055
    James Kanze
    Aug 8, 2009
Loading...

Share This Page