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 ?

Thank you!

CodePudding user response：

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.

CodePudding user response：

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

CodePudding user response：

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