How to get the index of a value in a vector in C++0x for_each algorithm and lambda expression?

Question

I have the following C++0x code (compiler- MSVC++ 10):

std::vector<float> data;
data.push_back(1.0f);
data.push_back(1.0f);
data.push_back(2.0f);

// lambda expression
std::for_each(data.begin(), data.end(), [](int value) {
     // Can I get here index of the value too?
});

What I want in the above code snippet is to get the index of the value in the data vector inside the lambda expression. It seems for_each only accepts a single parameter function. Is there any alternative to this using for_each and lambda?

Answer 1

maybe in the lambda function, pass it a int& instead of value int, so you'd have the address. & then you could use that to deduce your position from the first item

would that work? i don't know if for_each supports references

Answer 2

Something like this:

template <typename IteratorT, typename FunctionT>
FunctionT enumerate(IteratorT first, 
                    IteratorT last, 
                    typename std::iterator_traits<IteratorT>::difference_type initial,
                    FunctionT func)
{
    for (;first != last; ++first, ++initial)
        func(initial, *first);
    return func;
}

Used as:

enumerate(data.begin(), data.end(), 0, [](unsigned index, float val)
{
    std::cout << index << " " << val << std::endl;
});

Answer 3

I don't think you can capture the index, but you can use an outer variable to do the indexing, capturing it into the lambda:

int j = 0;
std::for_each(data.begin(), data.end(), [&j](float const& value) {
            j++;
});
std::cout << j << std::endl;

This prints 3, as expected, and j holds the value of the index.

If you want the actual iterator, you maybe can do it similarly:

std::vector<float>::const_iterator it = data.begin();
std::for_each(data.begin(), data.end(), [&it](float const& value) {
            // here "it" has the iterator
            ++it; 
});

Answer 4

You could also pass a struct as third argument to std::for_each and count the index in it like so:

struct myStruct {
   myStruct(void) : index(0) {};
   void operator() (float i) { cout << index << ": " << i << endl; index++; }
   int index;
};

int main()
{

   std::vector data;
   data.push_back(1.0f);
   data.push_back(4.0f);
   data.push_back(8.0f);

   // lambda expression
   std::for_each(data.begin(), data.end(), myStruct());

   return 0;
}

Answer 5

Following the standard convention for C and C++, the first element has index 0, and the last element has index size() - 1.

So you have to do the following;-

std::vector<float> data;
int index = 0;

data.push_back(1.0f);
data.push_back(1.0f);
data.push_back(2.0f);

// lambda expression
std::for_each(data.begin(), data.end(), [&index](float value) {
// Can I get here index of the value too?
   cout<<"Current Index :"<<index++; // gets the current index before increment
});

Answer 6

Roger Pate suggested in a comment to my other answer creating an iterator wrapper that performs the enumeration. Implementing it was a bit of a beating.

This iterator wrapper takes a forward iterator whose value type is T (called the "inner iterator") and transforms it into a forward iterator whose value type is a pair<int, T&>, where int is the distance type of the inner iterator.

This would be quite simple, except for two things:

• The std::pair constructor takes its arguments by const reference so we can't initialize a data member of type T&; we'll have to create our own pair type for the iterator.
• In order to support the correct semantics for the iterator, we need an lvalue (operator* needs to return a reference and operator-> needs to return a pointer), so the pair needs to be a data member of the iterator. Since it contains a reference, we'll need a way to "reset" it and we'll need it to be lazily initialized so that we can correctly handle end iterators. boost::optional<T> seems not to like it if T is not assignable, so we'll write our own simple lazy<T>.

The lazy<T> wrapper:

#include <new>
#include <type_traits>

// A trivial lazily-initialized object wrapper; does not support references
template<typename T>
class lazy
{
public:

    lazy() : initialized_(false) { }
    lazy(const T& x) : initialized_(false) { construct(x); }

    lazy(const lazy& other)
        : initialized_(false)
    {
        if (other.initialized_)
            construct(other.get());
    }

    lazy& operator=(const lazy& other)
    {
        // To the best of my knowledge, there is no clean way around the self
        // assignment check here since T may not be assignable
        if (this != &other)
            construct(other.get());
        return *this;
    }

    ~lazy() { destroy(); }

    void reset() { destroy(); }
    void reset(const T& x) { construct(x); }

          T& get()       { return reinterpret_cast<      T&>(object_); }
    const T& get() const { return reinterpret_cast<const T&>(object_); }

private:

    // Ensure lazy<T> is not instantiated with T as a reference type
    typedef typename std::enable_if<
        !std::is_reference<T>::value
    >::type ensure_t_is_not_a_reference;

    void construct(const T& x) 
    {
        destroy();
        new (&object_) T(x); 
        initialized_ = true;
    }

    void destroy() 
    { 
        if (initialized_)
            reinterpret_cast<T&>(object_).~T();
        initialized_ = false;
    }

    typedef typename std::aligned_storage<
        sizeof T, 
        std::alignment_of<T>::value
    >::type storage_type;

    storage_type object_;
    bool initialized_;
};

The enumerating_iterator:

#include <iterator>
#include <type_traits>

// An enumerating iterator that transforms an iterator with a value type of T
// into an iterator with a value type of pair<index, T&>.
template <typename IteratorT>
class enumerating_iterator
{
public:

    typedef IteratorT                              inner_iterator;
    typedef std::iterator_traits<IteratorT>        inner_traits;
    typedef typename inner_traits::difference_type inner_difference_type;
    typedef typename inner_traits::reference       inner_reference;

    // A stripped-down version of std::pair to serve as a value type since
    // std::pair does not like having a reference type as a member.
    struct value_type
    {
        value_type(inner_difference_type f, inner_reference s)
            : first(f), second(s) { }

        inner_difference_type first;
        inner_reference       second;
    };

    typedef std::forward_iterator_tag iterator_category;
    typedef inner_difference_type     difference_type;
    typedef value_type&               reference;
    typedef value_type*               pointer;

    explicit enumerating_iterator(inner_iterator it = inner_iterator(), 
                                  difference_type index = 0) 
        : it_(it), index_(index) { }

    enumerating_iterator& operator++() 
    {
        ++index_;
        ++it_;
        return *this;
    }

    enumerating_iterator operator++(int)
    {
        enumerating_iterator old_this(*this);
        ++*this;
        return old_this;
    }

    const value_type& operator*() const 
    { 
        value_.reset(value_type(index_, *it_));
        return value_.get();
    }

    const value_type* operator->() const { return &**this; }

    friend bool operator==(const enumerating_iterator& lhs,
                           const enumerating_iterator& rhs)
    {
        return lhs.it_ == rhs.it_;
    }

    friend bool operator!=(const enumerating_iterator& lhs,
                           const enumerating_iterator& rhs)
    {
        return !(lhs == rhs);
    }

private:

    // Ensure that the template argument passed to IteratorT is a forward
    // iterator; if template instantiation fails on this line, IteratorT is
    // not a valid forward iterator:
    typedef typename std::enable_if<
        std::is_base_of<
            std::forward_iterator_tag,
            typename std::iterator_traits<IteratorT>::iterator_category
        >::value
    >::type ensure_iterator_t_is_a_forward_iterator;

    inner_iterator it_;              //< The current iterator
    difference_type index_;          //< The index at the current iterator
    mutable lazy<value_type> value_; //< Pair to return from op* and op->
};

// enumerating_iterator<T> construction type deduction helpers
template <typename IteratorT>
enumerating_iterator<IteratorT> make_enumerator(IteratorT it)
{
    return enumerating_iterator<IteratorT>(it);
}

template <typename IteratorT, typename DifferenceT>
enumerating_iterator<IteratorT> make_enumerator(IteratorT it, DifferenceT idx)
{
    return enumerating_iterator<IteratorT>(it, idx);
}

A test stub:

#include <algorithm>
#include <array>
#include <iostream>

struct print_pair
{
    template <typename PairT> 
    void operator()(const PairT& p)
    {
        std::cout << p.first << ": " << p.second << std::endl;
    }
};

int main()
{
    std::array<float, 5> data = { 1, 3, 5, 7, 9 };

    std::for_each(make_enumerator(data.begin()), 
                  make_enumerator(data.end()), 
                  print_pair());
}

This has been minimally tested; Comeau and g++ 4.1 both accept it if I remove the C++0x type traits and aligned_storage (I don't have a newer version of g++ on this laptop to test with). Please let me know if you find any bugs.

I'm very interested in suggestions about how to improve this. Specifically, I'd love to know if there is a way around having to use lazy<T>, either by using something from Boost or by modifying the iterator itself. I hope I'm just being dumb and that there's actually a really easy way to implement this more cleanly.

Answer 7

Another way to wrap iterators for enumerate:

Required headers:

#include <algorithm>
#include <iterator>
#include <utility>

Wrapping iterator:

template<class Iter, class Offset=int>
struct EnumerateIterator : std::iterator<std::input_iterator_tag, void, void, void, void> {
  Iter base;
  Offset n;

  EnumerateIterator(Iter base, Offset n = Offset()) : base (base), n (n) {}

  EnumerateIterator& operator++() { ++base; ++n; return *this; }
  EnumerateIterator operator++(int) { auto copy = *this; ++*this; return copy; }

  friend bool operator==(EnumerateIterator const& a, EnumerateIterator const& b) {
    return a.base == b.base;
  }
  friend bool operator!=(EnumerateIterator const& a, EnumerateIterator const& b) {
    return !(a == b);
  }

  struct Pair {
    Offset first;
    typename std::iterator_traits<Iter>::reference second;

    Pair(Offset n, Iter iter) : first (n), second(*iter) {}

    Pair* operator->() { return this; }
  };

  Pair operator*() { return Pair(n, base); }
  Pair operator->() { return Pair(n, base); }
};

Enumerate overloads:

template<class Iter, class Func>
Func enumerate(Iter begin, Iter end, Func func) {
  typedef EnumerateIterator<Iter> EI;
  return std::for_each(EI(begin), EI(end), func);
}
template<class T, int N, class Func>
Func enumerate(T (&a)[N], Func func) {
  return enumerate(a, a + N, func);
}
template<class C, class Func>
Func enumerate(C& c, Func func) {
  using std::begin;
  using std::end;
  return enumerate(begin(c), end(c), func);
}

Copied test from James:

#include <array>
#include <iostream>

struct print_pair {
  template<class Pair>
  void operator()(Pair const& p) {
    std::cout << p.first << ": " << p.second << "\n";
  }
};

int main() {
  std::array<float, 5> data = {1, 3, 5, 7, 9};
  enumerate(data, print_pair());
  return 0;
}

I don't include providing an offset here; though it's fully ready in EnumerateIterator to start at otherwise than 0. The choice left is what type to make the offset and whether to add overloads for the extra parameter or use a default value. (No reason the offset has to be the iterator's difference type, e.g. what if you made it some date related type, with each iteration corresponding to the next day?)