Search code examples
c++deque

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

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)?

Solution

  • 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.