std::Partition

[CarlJSP]

Does this look right?
I'm new to c++ vectors and the code should erase only those audio files that have finished playing from the vector.

If this is right, then how come the erase uses the _audioFinishActions.end() to know where to stop? It seems as though it should be something like itr.end() instead.

auto itr = std::partition( _audioFinishActions.begin(), _audioFinishActions.end(),[&]( AudioFinishAction& action ) -> bool
{
return action._file->playing();
} );
_audioFinishActions.erase( itr, _audioFinishActions.end() );

[LB]

Why not use std::remove_if?
http://www.cplusplus.com/reference/algorithm/remove_if/

[CarlJSP]

Good one. I'll do that soon.

However, this is code that I did not write and I am having a problem I believe is related to this code (can't recreate it so I'm scouring the code for potential problems). If this code is wrong, then I'll feel like I have at least fixed something that may do it. Therefore, my questions stand.

Thanks!

[LB]

The code looks correct to me. Read the doc for std::partition:
http://www.cplusplus.com/reference/algorithm/partition/

[CarlJSP]

Yeah, I was afraid of that. Thought I was on to something. Evidently the vector elements themselves are rearranged, not just an iterator pointing to a rearranged list.

Thanks!

[JLBorges]

std::partition() and std::remove_if() are not interchangeable; they are different.

std::partition() rearranges the sequence by moving the elements for which the predicate returns true
( _file->playing() is true ) to the beginning of the sequence. After the operation, the sequence will contain every element in the original sequence, but in a possibly different order - the order of elements in the original sequence is not preserved.

std::stable_partition() works like std::partition(), but preserves the original order of elements within each partition.

std::remove_if() moves the elements which are not to be removed - elements for which the predicate returns false ( _file->playing() is false ) to the beginning of the sequence. The elements to be removed are overwritten and have unspecified values (So remove() / remove_if() is almost always followed by a call to erase the removed elements). The relative order of the elements that are not to be removed is preserved.

#include <iostream>
#include <iterator>
#include <algorithm>

int main()
{
    const auto is_odd = []( int i ) { return i%2 == 1 ; };

    {
        int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;
        for( int v : a ) std::cout << v << ' ' ;
        std::cout << '\n' ;

        auto mid = std::partition( std::begin(a), std::end(a), is_odd ) ;
        for( auto iter = std::begin(a) ; iter != mid ; ++iter )
            std::cout << *iter << ' ' ;
        std::cout << " <partition> " ;
        for( auto iter = mid ; iter != std::end(a) ; ++iter )
            std::cout << *iter << ' ' ;
        std::cout << "\n\n" ;

        // 0 1 2 3 4 5 6 7 8 9
        // 9 1 7 3 5  <partition> 4 6 2 8 0
    }

    {
        int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;
        for( int v : a ) std::cout << v << ' ' ;
        std::cout << '\n' ;

        auto mid = std::stable_partition( std::begin(a), std::end(a), is_odd ) ;
        for( auto iter = std::begin(a) ; iter != mid ; ++iter )
            std::cout << *iter << ' ' ;
        std::cout << " <stable_partition> " ;
        for( auto iter = mid ; iter != std::end(a) ; ++iter )
            std::cout << *iter << ' ' ;
        std::cout << "\n\n" ;

        // 0 1 2 3 4 5 6 7 8 9
        // 1 3 5 7 9  <stable_partition> 0 2 4 6 8
    }

    {
        int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;
        for( int v : a ) std::cout << v << ' ' ;
        std::cout << '\n' ;

        auto mid = std::remove_if( std::begin(a), std::end(a), is_odd ) ;
        for( auto iter = std::begin(a) ; iter != mid ; ++iter )
            std::cout << *iter << ' ' ;
        std::cout << " <remove_if> " ;
        for( auto iter = mid ; iter != std::end(a) ; ++iter )
            std::cout << *iter << ' ' ;
        std::cout << "\n\n" ;

        // 0 1 2 3 4 5 6 7 8 9
        // 0 2 4 6 8  <remove_if> 5 6 7 8 9
    }
}

http://ideone.com/krUXIr

[CarlJSP]

This helps a lot. Thanks.

One more iteration question related to this:

If I am iterating through a vector and in the predicate I am calling a method that adds to the vector, what happens? Does the "end()" keep the old value so the newly added element isn't processed?

[JLBorges]

> If I am iterating through a vector and in the predicate I am calling a method that adds to the vector, what happens?
> Does the "end()" keep the old value

Assuming that we have taken a copy of the original end(), and assuming that 'adding to the vector' means adding at the end ( push_back() ):

If the capacity() of the vector http://en.cppreference.com/w/cpp/container/vector/capacity
is greater than its size(), the copy of the original end() continues to be a valid iterator 'pointing' to the original end of sequence.

If not, capacity() == size(), and the current storage is inadequate for a new element to be added. Fresh storage is allocated to which the elements are moved/copied; and all previous iterators and references are invalidated.

Iterating with positions cause no problems; a position is relative:

std::vector<int> vec { 0, 1, 2, 3, 4 } ;

auto original_size = vec.size() ;
for( decltype(original_size) i = 0 ; i < original_size ; ++i )
    vec.push_back(i*i) ;

Ensuring that adequate storage is reserved, and elements will not have to be relocated also works:

std::vector<int> vec { 0, 1, 2, 3, 4 } ;

vec.reserve( vec.size() * 2 ) ;
auto original_end = vec.end() ;
for( auto iter = vec.begin() ; iter != original_end ; ++iter )
{
    // invariant: assert( vec.capacity() > vec.size() ) ;
    vec.push_back( *iter * *iter ) ;

}

[CarlJSP]

Thanks. That's how I interpreted it as well.

I've created a separate vector to queue up any changes until after the iteration. I think this could be the cause of the problems I am seeing. It could be intermittent which is what I'm seeing.

Thanks again...