Блог пользователя Kemal

Range-based for loop in C++
Автор Kemal, история, 8 лет назад, По-английски

Hey there!

I think everyone know what does this piece of code do:

vector <int> v = {1, 2, 3, 4};
for (int x : v)
  cout << x << " ";

prints: 1 2 3 4

Is there any way to do this in reverse order ?!

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

http://ideone.com/AS8l6J

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится 
template<class T>
struct reversed_iter {
  T & container;
  
  reversed_iter(T & container): container(container) {}
  
  auto begin() -> decltype(container.rbegin()) {
    return container.rbegin();
  }
  
  auto end() -> decltype(container.rend()) {
    return container.rend();
  }
};

template<class T>
reversed_iter<T> make_reversed(T & container) {
  return reversed_iter<T>(container); 
}

int main() {  
  vector <int> v = {1, 2, 3, 4};
  for (auto x : make_reversed(v))
    cout << x << " ";
    
  // or just
  for (auto x = v.rbegin(); x != v.rend(); ++x)
    cout << *x << " ";
}
→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    to Bassel and MrDindows

    The main point of this C++ 11 feature is not to write long code, even the traditional way is better than those options

    for (int i=v.size()-1;i>=0;i--)
  cout << v[i] << " ";
    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What advantages does the method using a struct and template have over the simple method kingofnumbers provided?

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I don't think they have any advantages, they are long code and even slower.

        however, Kemal asked for even shorter method using C++ 11, I don't know it,though. I was just saying that even the way I wrote is better than those struct and template ways

        → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      * int(v.size()) - 1 :)

      → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      That's a great way to illustrate the usefulness of reverse adapter. The bug you just made couldn't be possible in the original code. (Not to mention that the original one is shorter, clearer and works with any container.)

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        can you tell which bug are you talking about? I've just tested my code and it's working even if the vector is empty.

        and I will repeat my point, I think that Kemal actually requested something short and practical to use during the contest. for me I don't prefer to copy/paste that template every time I want to traverse a container in reversed order.

        → Ответить
        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Yeah, you're right, my mistake :) The other points still stand though:

          1. Reverse adapter is cleaner, shorter and less error prone.
          2. I don't see the words "short" or "programming competition" in the OP.
          3. Even if you do use it in a programming competition, there's no need to copy/paste anything ;)
          → Ответить
        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

          Casting UINT_MAX from unsigned to signed is implementation-defined, so it could possibly be a bug in some machine / compiler. For programming contests this is a moot point because you know the environment you're dealing with.

          → Ответить
          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            but in this case it isn't casting -1, it is unsigned zero subtract 1, and it equals to max value of unsigned(4294967295). Then it casts to int and produces undefined (not unspecified) behavior

            → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    One problem here that it won't work with temporaries, e.g

    for (auto x: make_reveresed(get_vector()){
  cout << x;
}
    → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -26 Проголосовать: не нравится

    Please, don't invent bicycle. It's already in Boost.

    #include <iostream>
#include <vector>
#include <boost/range/adaptor/reversed.hpp>
using namespace std;

int main()
{
    vector<int> v = {1, 2, 3, 4};
    for (int x : boost::adaptors::reverse(v)) {
        cout << x << " ";
    }
}
    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Such simple!

Array [1 2 3 4] will be printed in reverse order.

vector <int> v = {4, 3, 2, 1};
for (int x : v)
  cout << x << " ";
→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

There was a post: http://mirror.codeforces.com/blog/entry/10124 where using templates you can write in C++ like this:

for (auto i: range(1000))
    sum += i;
or
for (auto i: range(10, 20))
    cout << i << endl;
→ Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится 

You can use reverse function for vector.


vector <int> v = {1, 2, 3, 4};

reverse(v.begin(), v.end());

for(int i : v) {

      cout << i << " ";

}
→ Ответить
»
11 месяцев назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Using C++20:

#include <ranges>

vector v = {1, 2, 3, 4};
for (int x: v | views::reverse) 
  cout << x << ' ';

// or
for (int x: views::iota(1, 5) | views::reverse) 
  cout << x << ' ';
→ Ответить
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Any effect on time complete?

    → Ответить
    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      I did a few experiments running a loop for $$$10^9$$$ iterations, looks like performance depends on compiler optimizations. If no optimizations used at all, then ranges perform quite slow, however if you turn on some optimizations, then the difference with regular loop becomes really insignificant.

      No optimizations (-O0):

      for loop regular: 2023ms
for loop views::iota: 6070ms
for loop views::iota | views::reverse: 18875ms

      Using -O2 optimizations:

      for loop regular: 449ms
for loop views::iota: 451ms
for loop views::iota | views::reverse: 468ms

      Using -O3 optimizations:

      for loop regular: 247ms
for loop views::iota: 246ms
for loop views::iota | views::reverse: 299ms
      → Ответить