C++: getting index of an item in a container

[Barnaby W. Füi]

std::find() will return an iterator to it, but I can't seem to find anything that returns the offset of an item in a container. I made this (index_of() specifically) for the time being, but this seems like such a common thing that it would be in the STL, is it somewhere and I'm missing it?

 

[ElDonAntonio]

Say you have a vector:

std::vector<item> MyVector;

std::vector<item>::iterator it = find(...);
int index = it-MyVector.begin();

or even simpler:

int index = find(...) - MyVector.begin();

voila!

 

[Barnaby W. Füi]

Sweet! Thanks!

 

[Barnaby W. Füi]

Doh.. doesn't seem to work (with a list<> anyways)

bool WindowPool::screenNumberOfRoot(Window root, int * screennum_return) {
list<Window>::iterator found = find(roots.begin(), roots.end(), root);

if(found == roots.end())
return false;

*screennum_return = found - roots.begin();
return true;
}

I get this nasty complaint:

WindowPool.cc:97: error: no match for 'operator-' in 'found - std::list<_Tp, _Alloc>::begin() [with _Tp = Window, _Alloc = std::allocator<Window>]()'
/usr/include/c++/3.3/bits/stl_bvector.h:147: error: candidates are: ptrdiff_t std:perator-(const std::_Bit_iterator_base&, const std::_Bit_iterator_base&)

Hmmm.. it seems that iterator subtraction only needs to be supported by random access iterators, which I assume a list<>::iterator is not. Bah.. maybe I'll just use a vector instead.

 

[ElDonAntonio]

usually a vector works fine for me, just be careful of invalidation of iterators when inserting/deleting.

If you must use a list, then you can use the distance function:

http://www.sgi.com/tech/stl/distance.html

I have no idea how efficient it is though.

 

[Barnaby W. Füi]

Cool. I've been sifting through SGI's STL docs trying to absorb all of the useful looking stuff but I never saw distance(). It sounds like it would be less efficient, I would need to iterate through twice (once in find() and once in distance()) to get the offset. But actually a vector is fine for this, it'll only be holding a handful of items at the very most.

 

[glugglug]

If you aren't frequently inserting/removing stuff from the middle of the list, a vector is more efficient anyways.

 

[Barnaby W. Füi]

I thought lists were less efficient at random access?

 

[glugglug]

Random access and searching both, although searching is to a much lesser extent.

 

[Barnaby W. Füi]

I'm confused , you just said that vectors are worse at random access.

 

[glugglug]

vectors are bad at random insertions & deletions. (Insertion/deletion only works well at the end of the vector). Random access as in reading or changing the value at a given position they are great at.

 

[Barnaby W. Füi]

Originally posted by: glugglug
vectors are bad at random insertions & deletions. (Insertion/deletion only works well at the end of the vector). Random access as in reading or changing the value at a given position they are great at.

Ahh that makes more sense.