By Fred Finkle


2012-06-09 15:37:33 8 Comments

Assume I have the following code:

vector<int> list;
for(auto& elem:list) {
    int i = elem;
}

Can I find the position of elem in the vector without maintaining a separate iterator?

11 comments

@Peleg Harel 2019-08-27 13:39:25

If you want to avoid having to write an auxiliary function while having the index variable local to the loop, you can use a lambda with a mutable variable.:

int main() {
    std::vector<char> values = {'a', 'b', 'c'};
    std::for_each(begin(values), end(values), [i = size_t{}] (auto x) mutable {
        std::cout << i << ' ' << x << '\n';
        ++i;
    });
}

@M. Ahnen 2019-02-14 09:11:05

Tobias Widlund wrote a nice MIT licensed Python style header only enumerate (C++17 though):

GitHub

Blog Post

Really nice to use:

std::vector<int> my_vector {1,3,3,7};

for(auto [i, my_element] : en::enumerate(my_vector))
{
    // do stuff
}

@Forrest Voight 2019-01-12 03:53:00

Here's a macro-based solution that probably beats most others on simplicity, compile time, and code generation quality:

#include <iostream>

#define fori(i, ...) if(size_t i = -1) for(__VA_ARGS__) if(i++, true)

int main() {
    fori(i, auto const & x : {"hello", "world", "!"}) {
        std::cout << i << " " << x << std::endl;
    }
}

Result:

$ g++ -o enumerate enumerate.cpp -std=c++11 && ./enumerate 
0 hello
1 world
2 !

@Flamefire 2018-07-20 08:44:03

Based on the answer from @Matthieu there is a very elegant solution using the mentioned boost::adaptors::indexed:

std::vector<std::string> strings{10, "Hello"};
int main(){
    strings[5] = "World";
    for(auto const& el: strings| boost::adaptors::indexed(0))
      std::cout << el.index() << ": " << el.value() << std::endl;
}

You can try it

This works pretty much like the "ideal world solution" mentioned, has pretty syntax and is concise. Note that the type of el in this case is something like boost::foobar<const std::string&, int>, so it handles the reference there and no copying is performed. It is even incredibly efficient: https://godbolt.org/g/e4LMnJ (The code is equivalent to keeping an own counter variable which is as good as it gets)

For completeness the alternatives:

size_t i = 0;
for(auto const& el: strings) {
  std::cout << i << ": " << el << std::endl;
  ++i;
}

Or using the contiguous property of a vector:

for(auto const& el: strings) {
  size_t i = &el - &strings.front();
  std::cout << i << ": " << el << std::endl;
}

The first generates the same code as the boost adapter version (optimal) and the last is 1 instruction longer: https://godbolt.org/g/nEG8f9

Note: If you only want to know, if you have the last element you can use:

for(auto const& el: strings) {
  bool isLast = &el == &strings.back();
  std::cout << isLast << ": " << el << std::endl;
}

This works for every standard container but auto&/auto const& must be used (same as above) but that is recommended anyway. Depending on the input this might also be pretty fast (especially when the compiler knows the size of your vector)

Replace the &foo by std::addressof(foo) to be on the safe side for generic code.

@Matthieu M. 2018-07-20 08:52:40

That's elegant indeed!

@Flamefire 2018-07-20 12:16:54

I added the 2 alternatives with godbolt comparison of the generated code for completeness and also addressed the need of the OP (in the comments) for detecting the last element

@PulseJet 2017-04-15 07:06:20

There is a surprisingly simple way to do this

vector<int> list;
for(auto& elem:list) {
    int i = (&elem-&*(list.begin()));
}

where i will be your required index.

This takes advantage of the fact that C++ vectors are always contiguous.

@Jens Winslow 2016-08-17 15:21:24

If you insist on using range based for, and to know index, it is pretty trivial to maintain index as shown below. I do not think there is a cleaner / simpler solution for range based for loops. But really why not use a standard for(;;)? That probably would make your intent and code the clearest.

vector<int> list;
int idx = 0;
for(auto& elem:list) {
    int i = elem;
    //TODO whatever made you want the idx
    ++idx;
}

@user66081 2016-12-11 20:19:43

(idx amounts to "maintaining a separate iterator")

@Frédéric Terrazzoni 2012-06-09 16:01:54

jrok is right : range-based for loops are not designed for that purpose.

However, in your case it is possible to compute it using pointer arithmetic since vector stores its elements contiguously (*)

vector<int> list;
for(auto& elem:list) { 
    int i = elem;
    int pos = &elem-&list[0]; // pos contains the position in the vector 

    // also a &-operator overload proof alternative (thanks to ildjarn) :
    // int pos = addressof(elem)-addressof(list[0]); 

}

But this is clearly a bad practice since it obfuscates the code & makes it more fragile (it easily breaks if someone changes the container type, overload the & operator or replace 'auto&' by 'auto'. good luck to debug that!)

NOTE: Contiguity is guaranteed for vector in C++03, and array and string in C++11 standard.

@Nicol Bolas 2012-06-09 16:02:47

Yes it is stated in the standard. Contiguity is guaranteed for vector in C++03, and array and string in C++11.

@ildjarn 2012-06-09 18:28:49

"it easily breaks if someone ... overload the & operator" That's what std::addressof is for. :-]

@Frédéric Terrazzoni 2012-06-09 19:10:47

You're right. So the &-overload proof version would be : int pos = addressof(elem)- addressof(list[0]); .... Matthieu M.'s iterator wrapper is way better :)

@Fred Finkle 2012-06-09 19:27:41

Didn't know that contiguity was guaranteed. Wouldn't want to use it here, but good to know.

@Michael van der Westhuizen 2013-07-18 00:17:49

Why not use std::distance to figure out the position?

@alfC 2013-11-13 03:13:02

I read from your comments that one reason you want to know the index is to know if the element is the first/last in the sequence. If so, you can do

for(auto& elem:list) {
//  loop code ...
    if(&elem == &*std::begin(list)){ ... special code for first element ... }
    if(&elem == &*std::prev(std::end(list))){ ... special code for last element ... }
//  if(&elem == &*std::rbegin(list)){... (C++14 only) special code for last element ...}
//  loop code ... 
}

EDIT: For example, this prints a container skipping a separator in the last element. Works for most containers I can imagine (including arrays), (online demo http://coliru.stacked-crooked.com/a/9bdce059abd87f91):

#include <iostream>
#include <vector>
#include <list>
#include <set>
using namespace std;

template<class Container>
void print(Container const& c){
  for(auto& x:c){
    std::cout << x; 
    if(&x != &*std::prev(std::end(c))) std::cout << ", "; // special code for last element
  }
  std::cout << std::endl;
}

int main() {
  std::vector<double> v{1.,2.,3.};
  print(v); // prints 1,2,3
  std::list<double> l{1.,2.,3.};
  print(l); // prints 1,2,3
  std::initializer_list<double> i{1.,2.,3.};
  print(i); // prints 1,2,3
  std::set<double> s{1.,2.,3.};
  print(s); // print 1,2,3
  double a[3] = {1.,2.,3.}; // works for C-arrays as well
  print(a); // print 1,2,3
}

@alfC 2014-08-04 09:00:45

Please note (before unjustified downvoting) that the author of the question is asking this in the context of detecting the last element in a for-ranged loop for a container. For that I see no reason why comparing &elem and &*std::prev(std::end(list)) will not work or be practical. I agree with the other answer that an iterator-based for is more appropriate for this, but still.

@Marc Glisse 2014-11-08 20:03:56

It seems easier to declare int i=c.size(); before the loop and test if(--i==0).

@alfC 2014-11-08 20:09:19

@MarcGlisse, the int i code was just an example. I will remove it to avoid confusion. Even if you use size before the loop you will need a counter.

@Michael 2014-07-03 17:14:06

If you have a compiler with C++14 support you can do it in a functional style:

#include <iostream>
#include <string>
#include <vector>
#include <functional>

template<typename T>
void for_enum(T& container, std::function<void(int, typename T::value_type&)> op)
{
    int idx = 0;
    for(auto& value : container)
        op(idx++, value);
}

int main()
{
    std::vector<std::string> sv {"hi", "there"};
    for_enum(sv, [](auto i, auto v) {
        std::cout << i << " " << v << std::endl;
    });
}

Works with clang 3.4 and gcc 4.9 (not with 4.8); for both need to set -std=c++1y. The reason you need c++14 is because of the auto parameters in the lambda function.

@NathanOliver 2018-11-29 15:29:15

std::function uses type erasure which is expensive. Why not use template<typename T, typename Callable> void for_enum(T& container, Callable op) so you don't have to pay for type erasure?

@Matthieu M. 2012-06-09 16:20:33

Yes you can, it just take some massaging ;)

The trick is to use composition: instead of iterating over the container directly, you "zip" it with an index along the way.

Specialized zipper code:

template <typename T>
struct iterator_extractor { typedef typename T::iterator type; };

template <typename T>
struct iterator_extractor<T const> { typedef typename T::const_iterator type; };


template <typename T>
class Indexer {
public:
    class iterator {
        typedef typename iterator_extractor<T>::type inner_iterator;

        typedef typename std::iterator_traits<inner_iterator>::reference inner_reference;
    public:
        typedef std::pair<size_t, inner_reference> reference;

        iterator(inner_iterator it): _pos(0), _it(it) {}

        reference operator*() const { return reference(_pos, *_it); }

        iterator& operator++() { ++_pos; ++_it; return *this; }
        iterator operator++(int) { iterator tmp(*this); ++*this; return tmp; }

        bool operator==(iterator const& it) const { return _it == it._it; }
        bool operator!=(iterator const& it) const { return !(*this == it); }

    private:
        size_t _pos;
        inner_iterator _it;
    };

    Indexer(T& t): _container(t) {}

    iterator begin() const { return iterator(_container.begin()); }
    iterator end() const { return iterator(_container.end()); }

private:
    T& _container;
}; // class Indexer

template <typename T>
Indexer<T> index(T& t) { return Indexer<T>(t); }

And using it:

#include <iostream>
#include <iterator>
#include <limits>
#include <vector>

// Zipper code here

int main() {
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9};

    for (auto p: index(v)) {
        std::cout << p.first << ": " << p.second << "\n";
    }
}

You can see it at ideone, though it lacks the for-range loop support so it's less pretty.

EDIT:

Just remembered that I should check Boost.Range more often. Unfortunately no zip range, but I did found a perl: boost::adaptors::indexed. However it requires access to the iterator to pull of the index. Shame :x

Otherwise with the counting_range and a generic zip I am sure it could be possible to do something interesting...

In the ideal world I would imagine:

int main() {
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9};

    for (auto tuple: zip(iota(0), v)) {
        std::cout << tuple.at<0>() << ": " << tuple.at<1>() << "\n";
    }
}

With zip automatically creating a view as a range of tuples of references and iota(0) simply creating a "false" range that starts from 0 and just counts toward infinity (or well, the maximum of its type...).

@Fred Finkle 2012-06-09 19:30:57

This provides a wealth of useful information. Thanks. I'll play around with the code. As I mentioned above, the "index" code is what I would like the language to provide.

@ildjarn 2012-06-09 19:58:18

How about counting_range (or boost::counting_iterator) + boost::zip_iterator?

@Matthieu M. 2012-06-10 10:00:45

@ildjarn: Yes, Boost.Iterators has the building blocks (it seems), however there is no corresponding range, which is annoying.

@Xeo 2012-07-04 12:39:04

Note that you could possible change your Indexer to also properly accept and hold rvalue arguments, by changing the type of _container to a value type if the original argument is an rvalue and std::move/std::forward the argument in.

@Xeo 2012-07-04 14:08:31

I edited the code to make it hopefully work with rvalues, sadly I can't completely test the code, but it should work. For an explanation, see here. If you don't like it or find any errors or whatever, feel free to roll back. :)

@Matthieu M. 2012-07-04 14:13:02

@Xeo: I rollbacked. Not that the idea of rvalues is not pleasant, but it seems to me that this would generate a copy of the container if it is not an rvalue, which is not desired. It might not be far from the goal though.

@Xeo 2012-07-04 17:04:32

That's wrong, in case the container is an lvalue, T will be deduced as Container cv-opt&, which then is also the type of the member _container.

@Matthieu M. 2012-07-04 17:09:20

@Xeo: Oh! (Does it show that I am not too savvy on C++11 :p ?) In this case I'll reinstate your edit! -- or I would if I knew how... I can't seem to get the list of edits :/

@Xeo 2012-07-04 18:59:35

Mind joining me in the Lounge<C++>?

@betabandido 2012-07-04 23:06:47

@Xeo Your version works fine for lvalues (indeed as you said no copies take place). For rvalues there is some problem, though. I have not spotted it yet, but I will continue to look into it tomorrow. Basically, when I use index like this for (auto x : index(std::vector<int>{2, 4, 6})) { ... } I get this error: error: no matching function for call to ‘Indexer<std::vector<int, std::allocator<int> > >::iterator::iterator(std::vector<int, std::allocator<int> >::const_iterator)’. I used g++-4.7.

@Xeo 2012-07-05 00:22:56

@betabandido: Yeah, that's why I didn't roll back yet and asked for Matthieu to join me in the Lounge, to discuss that exact problem. begin and end are const, and if the original argument is an rvalue, _container is a value type and is also const, making _container.begin() and _container.end() return const_iterators instead of the wanted iterators. One solution is to add non-const begin and end functions to the Indexer.

@Matthieu M. 2012-07-05 06:14:03

@Xeo: sorry but my hours differ slightly from yours it seems. Indeed in this case I think that removing the const from begin and end would be the right thing to do.

@Flamefire 2018-07-20 08:45:12

You were on the right track. See my answer for a full use of boost::adaptors::indexed together with a performance evaluation.

@Nicol Bolas 2012-06-09 16:00:54

No, you can't (at least, not without effort). If you need the position of an element, you shouldn't use range-based for. Remember that it's just a convenience tool for the most common case: execute some code for each element. In the less-common circumstances where you need the position of the element, you have to use the less-convenient regular for loop.

Related Questions

Sponsored Content

1 Answered Questions

[SOLVED] The Definitive C++ Book Guide and List

  • 2008-12-23 05:23:56
  • grepsedawk
  • 2407129 View
  • 4242 Score
  • 1 Answer
  • Tags:   c++ c++-faq

6 Answered Questions

8 Answered Questions

[SOLVED] How to convert an iterator to a stream?

  • 2014-07-01 13:05:15
  • gontard
  • 212394 View
  • 476 Score
  • 8 Answer
  • Tags:   java iterator java-8

79 Answered Questions

[SOLVED] How do I iterate over the words of a string?

  • 2008-10-25 08:58:21
  • Ashwin Nanjappa
  • 2188335 View
  • 3007 Score
  • 79 Answer
  • Tags:   c++ string split

20 Answered Questions

8 Answered Questions

[SOLVED] C++11 reverse range-based for-loop

24 Answered Questions

[SOLVED] Image Processing: Algorithm Improvement for &#39;Coca-Cola Can&#39; Recognition

6 Answered Questions

[SOLVED] Need iterator when using ranged-based for loops

Sponsored Content