4

Consider the following piece of code:

    std::vector<int> vec(n);
    for (auto& elem : vec) {
        std::cin >> elem;
    }
    auto count = 0;
    while (!isGood(vec)) {
        auto odd_it = std::find_if(vec.begin(), vec.end(), [] (int num) { return ~(num % 2); });
        auto even_it = std::find_if(vec.begin(), vec.end(), [] (int num) { return num % 2; });
        if(odd_it != vec.end() && even_it != vec.end()) {
            std::swap(vec.at(std::distance(vec.begin(), odd_it)), vec.at(std::distance(vec.begin(), even_it)));
            count++;
        }
        else {
            count = -1;
            break;
        }
    }

(I know its not the entire code, but its enough to recreate the problem)

In this code, the line auto odd_it (and also auto even_it) will return me the first odd element in the vector. However, I wanted the std::find_if to return me an iterator pointing to the first odd element which also has an even index (which in this case coincidentally happens to also be the first odd element too.)

So, in a nutshell, the question is basically to find the index of the element currently being "worked upon" by the function (which has been passed to the predicate)

Evg
  • 25,259
  • 5
  • 41
  • 83
kesarling He-Him
  • 1,944
  • 3
  • 14
  • 39
  • 2
    You can't do it with `std::find_if` in a simple and elegant way. Technically you can (by subtracting addresses), but you'd better write your own `find_if` for this functionality. – Evg Jun 24 '20 at 09:09
  • Just use `for` instead. In Ranges TS you could've done it idiomatically. – ALX23z Jun 24 '20 at 09:11
  • 1
    Do you mean something like `auto odd_it = std::find_if(vec.begin(), vec.end(), [] (int num) { static bool isOdd = true; isOdd = !isOdd; return ~(num % 2) && isOdd; });` – Thomas Sablik Jun 24 '20 at 09:12
  • If that's not what you are looking for then the question is unclear for me. – Thomas Sablik Jun 24 '20 at 09:16
  • If I understand your question correctly, Thomas' solution is what you need. But I doubt that the standard guarantees that the predicate is invoked strictly in order. Any reasonable implementation will do it, however. – Evg Jun 24 '20 at 09:17
  • 1
    It will return whether an index is odd or even. The flag `isOdd` will be flipped each time the predicate is invoked, and thanks to `static` its value will be kept between predicate invocations. But I doubt that the standard guarantees that the predicate is invoked strictly in order. Any reasonable implementation will do it, however. Still, a special function seems to a better solution. – Evg Jun 24 '20 at 09:20
  • @d4rk4ng31 Evg already said there is no proper way to get the index. Write your own `find_if` that passes the index, if you need it. A third solution is write your own iterator and then use `std::find_if`, but that is cumbersome. – Acorn Jun 24 '20 at 09:21
  • 1
    See this [horrible example](https://godbolt.org/z/Q4hgdx). BTW, the C++ standard library is not STL. STL [has gone](https://stackoverflow.com/questions/5205491/whats-the-difference-between-stl-and-c-standard-library). – Evg Jun 24 '20 at 09:29
  • It was a code snippet to find out if I understand your question. I'm not sure it's a correct answer. As @Evg said: _"But I doubt that the standard guarantees that the predicate is invoked strictly in order."_ This code causes undefined behavior. I don't know if it's an academic (theoretical) problem or a real world problem. – Thomas Sablik Jun 24 '20 at 09:32
  • 2
    _"the predicate is invoked in order"_ Yes, on your machine, with degugging enabled, without optimization, in this situation on a Wednesday. The funny part of undefined behavior is it can seem like it works correctly. Without setting `ExecutionPolicy` it can even cause more race conditions if each condition is checked in parallel on a different CPU. – Thomas Sablik Jun 24 '20 at 09:36
  • Notice that in your example, you don't need index for swap: `std::swap(*odd_it, *even_it);` would do the job. – Jarod42 Jun 24 '20 at 12:53
  • @Jarod42, I don't need index for swapping purpose. I just needed its value to ascertain its parity – kesarling He-Him Jun 24 '20 at 12:57

2 Answers2

4

The most clear solution in C++17 and below is simply to write your own version of find_if that passes an index to the predicate. The implementation is straightforward:

template<class Input_it, class Predicate>
Input_it find_if_with_index(Input_it first, Input_it last, Predicate p) {
    for (std::size_t i = 0; first != last; ++i, ++first) {
        if (p(i, *first))
            return first;
    }
    return last;
}
Evg
  • 25,259
  • 5
  • 41
  • 83
  • Also, on a side note, in the example you [linked](https://godbolt.org/z/u2WW-2), since when does usage of `&` operator on a reference return the address of the object the reference is pointing to? I didn't quite get that... – kesarling He-Him Jun 24 '20 at 09:43
  • @d4rk4ng31, I guess from the very beginning of C++. :) – Evg Jun 24 '20 at 09:45
  • Hmm.. I surprisingly didn't know that . So the only difference between reference and pointer is prevention of memory leakage and a different syntax? :) – kesarling He-Him Jun 24 '20 at 09:47
  • There are plenty of differences, which any good book/tutorial will elucidate, as would searching here on SO. – underscore_d Jun 24 '20 at 09:48
  • 1
    @d4rk4ng31, you can leak memory with references, too: `int& i = *new int;`. – Evg Jun 24 '20 at 09:52
0

Alternatively to get index, you might create custom iterator to iterate only on odd index.

with range-v3, you might then do:

auto odd_index_even_value = vec | ranges::view::stride(2)
                                | ranges::view::filter([](int e){ return e % 2 == 0; });
auto even_index_odd_value = vec | ranges::view::drop(1) | ranges::view::stride(2)
                                | ranges::view::filter([](int e){ return e % 2 == 1; });

auto it1 = begin(odd_index_even_value);
auto it2 = begin(even_index_odd_value);

int count = 0;
while (it1 != end(odd_index_even_value) && it2 != end(even_index_odd_value)) {
    std::swap(*it1, *it2);
    ++it1;
    ++it2;
    ++count;
}
if (it1 != end(odd_index_even_value) || it2 != end(even_index_odd_value)) {
    count = -1;   
}

Demo

Jarod42
  • 203,559
  • 14
  • 181
  • 302