conditional iterator over two arrays with STL

Question

I have two arrays. The typs are int and bool. The bool array indicates if an element is already deleted or not. Now I want a function that returns an iterator which only iterates over not deleted elements. Important is that the function should not allocate new memory (like for copying the element in a new vector). Is there a way to do this with standard STL?

    std::array<int,5>  element={ 1   , 2   , 4    , 8    , 10   };
    std::array<bool,5> deleted={ true, true, false, false, true };
    std::vector<int>::iterator getNotDeleted(){
             ...
    }

Example:

   deleted= { true, true, false, false, true };
   element= { 1   , 2   , 4    , 8    , 10   };
   getNotDeleted should return a std::vector<int>::iterator that Iterates over 
   {4,8}

Answer 1

You could roll your own like this:

#include <array>
#include <iostream>
#include <functional>

template <class T>
struct no_op : std::unary_function <T,bool>
{
    bool operator() (const T& x) const
    {
        return x;
    }
};

template <class ItSource,
          class ItPredicate,
          class PredMod = no_op<bool> >
class ConditionalIterator
{
    ItSource _srcBegin;
    ItSource _srcEnd;

    ItPredicate _predBegin;
    ItPredicate _predEnd;

    void MoveNext()
    {
        while (_predBegin != _predEnd &&
               _srcBegin != _srcEnd &&
               PredMod()(!*_predBegin))
        {
            ++_predBegin;
            ++_srcBegin;
        }
    }
public:
    typedef ConditionalIterator & Reference;
    typedef typename std::iterator_traits<ItSource>::value_type ValueType;

    ConditionalIterator(ItSource srcBegin, ItSource srcEnd,
                        ItPredicate predBegin, ItPredicate predEnd)
                        : _srcBegin(srcBegin)
                        , _srcEnd(srcEnd)
                        , _predBegin(predBegin)
                        , _predEnd(predEnd)
    {
        MoveNext();
    }

    ConditionalIterator(ConditionalIterator const &other)
        : _srcBegin(other._srcBegin)
        , _srcEnd(other._srcEnd)
        , _predBegin(other._predBegin)
        , _predEnd(other._predEnd)
    {

    }

    ConditionalIterator &operator=(ConditionalIterator const &other)
    {
        if (this != &other)
        {
            _srcBegin = other._srcBegin;
            _srcEnd = other._srcEnd;
            _predBegin = other._predBegin;
            _predEnd = other._predEnd;
        }
        return (*this);
    }

    Reference operator++()
    {
        ++_predBegin;
        ++_srcBegin;
        MoveNext();
        return (*this);
    }

    ConditionalIterator operator++(int)
    {
        ConditionalIterator cit = *this;
        operator++();
        return (cit);
    }

    operator bool() const
    {
        return (_srcBegin != _srcEnd &&
                _predBegin != _predEnd);
    }

    ValueType operator*()
    {
        return (*_srcBegin);
    }
};

template <class PredMod, class ItSource, class ItPred> 
ConditionalIterator<ItSource, ItPred, PredMod> MakeConditionalIterator(ItSource srcBegin, ItSource srcEnd,
                                                              ItPred predBegin, ItPred predEnd)
{
    return (ConditionalIterator<ItSource, ItPred, PredMod>(srcBegin, srcEnd, predBegin, predEnd));
}

This code is far from complete, but it should get you started. Then you use it like so:

int main()
{
    std::array<int,5>  element={ 1   , 2   , 4    , 8    , 10   };
    std::array<bool,5> deleted={ false, true, false, false, true };

    auto cit_valid = MakeConditionalIterator<std::logical_not<bool> >(element.begin(), element.end(),
                                                                      deleted.begin(), deleted.end());

    auto cit_delete = MakeConditionalIterator<no_op<bool> >(element.begin(), element.end(),
                                                            deleted.begin(), deleted.end());

    while (cit_delete)
    {
        std::cout << *cit_delete++ << std::endl;
    }

    while (cit_valid)
    {
        std::cout << *cit_valid++ << std::endl;
    }

    return (0);
}

Answer 2

You can write an iterator for this, simply construct an iterator that knows about both vectors, and it's current position in both vectors. Then, when advancing the iterator, skip any elements that are flagged as deleted.

template<class T>
struct maybe_deleted_iterator {      
    typedef int difference_type;
    typedef T value_type;
    typedef T& reference;
    typedef T* pointer;
    typedef std::forward_iterator_tag iterator_category;

    maybe_deleted_iterator();
    maybe_deleted_iterator(std::vector<T>& e, std::vector<bool>& d, bool is_beginning);
    maybe_deleted_iterator& operator++();
    reference operator*() const;
    pointer operator->() const;
    bool operator==(const maybe_deleted_iterator& rhs);
    bool operator!=(const maybe_deleted_iterator& rhs);
private:
    std::vector<T>* elements;
    std::vector<bool>* deleted;
    typename std::vector<T>::iterator e_iter;
    std::vector<bool>::iterator d_iter;
};

Then, simply iterate!

int main() {
    std::vector<int>   element = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
    std::vector<bool>  deleted = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1};
    maybe_deleted_iterator<int> it(element, deleted, true);
    maybe_deleted_iterator<int> end(element, deleted, false);
    for(; it!=end; ++it) {
        std::cout << *it << ' ';
    }
}

http://coliru.stacked-crooked.com/view?id=40e4d1a54f71643ee9f885f82d71fb46-50d9cfc8a1d350e7409e81e87c2653ba

LeSnip3R suggested having the members be begin/end pairs so that way it would work on any two containers, but I figured this was easier to understand for learning. In real code I'd expect to see it done without mentioning a specific container like vector.

Answer 3

So, as Mooing Duck shows in the comment, you can define an iterator on arbitrary elements of an array. I stand corrected, but I still suggest you think of less cumbersome solutions; you could either (and these are just the two solutions that popped my mind, there are so many more):

• sort the array keeping the valid entries in front, and iterate only from the first element to the n-th valid element
• use a container such as std::vector or std::list and actually erase the elements from your array, so you can iterate on them with a normal iterator (variant of this: copy the elements of your original array in an std::vector on which you can perform deletion, keeping your original vector safe)