-1

Let's say you have a vector of ints, unsorted and with multiple repeating items, like so:

vector<int> myVec{1, 0, 0, 0, 1, 1, 0, 1,0,0}

What is the fastest way to get the last index of 1 which is 8 for this example, other than looping through it from its end?

Would this be different if the vector would contain other items than 0 and 1?

What is the fastest way to do this in C++? L.E. I have seen the duplicate topic suggestions but even it dolves partially what I am looking for this has nothing to do with the minimum element in vector so I keep the question maybe it will help someone else too.

YoYoYo
  • 439
  • 2
  • 11
  • 10
    `What is the fastest way to get the last index of 1 which is 8 for this example, other than looping through it from its end?` There is no other way. – tkausl Mar 20 '22 at 10:38
  • 2
    this should help you: https://stackoverflow.com/a/39165645/8294653 – jdfa Mar 20 '22 at 10:42
  • 1
    If you're only storing 1s and 0s and aren't too worried about what data structure you're using, you may be able to check multiple values at a time; e.g. if you store this as a bitwise combinations of numbers with exactly 1 bit set; you may be able to check multiple values at a time, but are you sure you aren't optimizing prematurely here? This will take `O(n)` time, if you don't have any additional information available, regardless of how you implement it... – fabian Mar 20 '22 at 10:50
  • 1
    *What is the fastest way to get the last index of 1 which is 8 for this example...* The last index of value 1 is `myVec[7]` in this example. C++ uses 0-based indexing, so the index is a *cardinal offset*. In other languages that use 1-based indexing, like Pascal, the index is an *ordinal index*, which would be `8`. – Eljay Mar 20 '22 at 12:23
  • Without looping, you have to map some computational resources to each index and run them once. For example, each cuda thread checks one index. When they find something, they increment an atomic variable and write to an index with that variable as index. This way you can know all matched indices then sort the indices (sorting can be done without looping too) – huseyin tugrul buyukisik Aug 07 '23 at 19:55

3 Answers3

3

Depends on if you are stuck with vector<int>. If you could store the bits with bitset or unsigned int, then you can find the right most set bit through bitwise operations: Efficient bitwise operations for counting bits or find the right|left most ones

Ranoiaetep
  • 5,872
  • 1
  • 14
  • 39
2

The only faster way i can think of would be to save the last index as you populate the vector... It would add extra time to insertion but it would be faster to access.

If that is acceptable for your use case you might also want to consider the number of unique values in your vector, in your example this is feasible, if most values are unique you would quickly increase your memory usage.

You might want to inherit std::vector and implement your own insert as well as constructor if you want to go this way.

xception
  • 4,241
  • 1
  • 17
  • 27
1

Use std::max_element and reverse iterators. And that is looping through the vector. If it is unsorted, there is no faster way.

Mohammed Li
  • 823
  • 2
  • 7
  • 22