How do I get index of element in std::deque

Question

I have a deque and I have an object that belongs to the deque.

std::deque<Item> items;
// full deque with objects
// ...
Item &item = items[5];

Now I want to get index of that element in the deque:

size_t index = &item - &*m_items.begin();

I expect index to be equal to 5, but I get something bigger than deque's size.

Of course, I can run through the deque looking for my object, but is it possible to get index of element in O(1)?

Answer 1

You can't compute the index of an element in a std::deque<T> based on its address as the elements in a std::deque<T> are not store in contiguous memory. At best, you could use an iterator and subtract the begin() iterator from the location. Note, however, that adding or removing elements to a std::deque<T> invalidates all iterator even though pointers or references to objects are not invalidated.

Answer 2

This depends on there having been no reference invalidations, but you can use std::find_if to find the element by address, then use std::distance to get the index.

Item &item = items[5];
Item* p = &item;
auto it = std::find_if(items.begin(),
                       items.end(),
                       [p](const Item& i) {return p == &i;});

auto idx = std::distance(items.begin(), it);

The easier option would be to keep an iterator instead of a reference.