10

Let's say I have a std::vector and I get by some means the address of the n-th element. Is there a simple way (faster than iterating through the vector) to get the index at which the element appears, given the base address of my std::vector? Let's assume I'm sure the element is in the vector.

Alex Bravo
  • 1,601
  • 2
  • 24
  • 40
lezebulon
  • 7,607
  • 11
  • 42
  • 73

4 Answers4

18

Since you know the element is within the vector, and vector guarantees that its storage is contiguous, you could do:

index = element_pointer - vector.data();

or

index = element_pointer - &vector[0];

Note that technically the contiguous guarantee was introduced in C++03, but I haven't heard of a C++98 implementation that doesn't happen to follow it.

K-ballo
  • 80,396
  • 20
  • 159
  • 169
  • Note this only works on C++03/C++11`std::vector`s, and C++11`std::string`s – Mooing Duck Nov 16 '11 at 21:40
  • 2
    @Adrian, C++98 doesn't quite guarantee that all a vector's elements will reside in contiguous memory. Practically speaking, it's safe in all C++ versions, but it's only guaranteed by later revisions of the standard. – Rob Kennedy Nov 16 '11 at 21:44
  • That's true, I will add that. – K-ballo Nov 16 '11 at 21:52
  • 1
    Excluding vector - in 23.1.1.12 where operational semantics of a[n] are described - it says its the same as *(a.begin() + n) for vector and deque - this must guarantee contiguous memory for both - does it not? (although its not exactly plain English :-) – Adrian Cornish Nov 16 '11 at 21:56
  • @Adrian Cornish: The C++03 specialized `vector` is not a container, it does not fulfil the concept. Since C++11 `vector` is a regular unpacked container. – K-ballo Nov 16 '11 at 21:59
  • Agree it will not work on vector. vector was such a great idea ;-) – Adrian Cornish Nov 16 '11 at 22:02
  • @MooingDuck: Not that you're wrong, but seeing as it's the end of the year 2011, is it really relevant anymore? The 2003 standard was eight years ago. – GManNickG Nov 16 '11 at 22:05
  • @GMan: Has MS implemented value initialization yet (http://stackoverflow.com/questions/3931312/value-initialization-and-non-pod-types)? That's an example of a compiler exhibiting C++98 behavior instead of C++03, although of course it's also an example of MS's commitment to not implementing C++ properly. – Steve Jessop Nov 17 '11 at 00:50
  • @SteveJessop: That would be worthwhile to mention *because* a compiler gets it wrong. No mainstream compiler gets this aspect wrong, so why mention its ancestry? (Admittedly I made it sound like age is the only factor; I meant it should be factored in.) – GManNickG Nov 17 '11 at 01:11
  • @GMan: I just meant it as an example to show that age of the standard doesn't have much to do with it, because once a compiler decides it's not going to bother with new-fangled nonsense like C++03 or C99, then that decision can result in old-fangled compiler behavior for a very long time. But as an example of that, it does have the weakness that it's difficult to tell the difference whether MS deliberately conforms to the old standard, or just does something and finds out later what (if anything) it conforms to. – Steve Jessop Nov 17 '11 at 01:15
  • That is, I agree that everyone has contiguous vectors. I don't agree that the fact they've been standard for 8 years has anything to do with it -- I'd be pretty surprised if there was any "important" compiler that had non-contiguous vectors at the time the committee voted to include the requirement in C++03. The important factor is that the addition was uncontroversial, not that it was done a long time ago. – Steve Jessop Nov 17 '11 at 01:21
  • @SteveJessop: I see what you mean, though I still feel it's being done long ago (for whatever reason) is enough to make mentioning it only serve to confuse and introduce unnecessary information. – GManNickG Nov 17 '11 at 01:26
5

distance( xxx.begin(), theIterator);

The above will only work for a vector::iterator. If you only have a raw pointer to an element, you must use it this way:

distance(&v[0], theElementPtr);

Wayne Tanner
  • 1,346
  • 11
  • 18
  • 1
    He doesn't have an iterator, he has a memory address. There is no guarantee than vector iterators are raw pointers, and in fact there are several implementations in which they aren't. – K-ballo Nov 16 '11 at 21:38
  • 3
    There's a difference between a pointer and an iterator, and he specified an iterator. This is a good suggestion though if he can refactor. – Mooing Duck Nov 16 '11 at 21:39
  • For a vector, iterator and pointer are mostly interchangeable. The distance function should work if you pass an element pointer instead of an iterator. – Wayne Tanner Nov 16 '11 at 21:40
  • -1 An element address is not a vector iterator (in general, it may be in a certain implementation though) – Peter G. Nov 16 '11 at 21:41
  • The address of an element is not technically an iterator by type, however a pointer into a vector has the correct behavior to fulfill a random access iterator. The correct use of distance in this case would be distance(&v[0], theElementPtr) which will fall through to a subtraction as per the answer below. – Wayne Tanner Nov 16 '11 at 21:49
1

Yes - because a vector guarantees all elements are in a contiguous block of memory you can use pointer arithmetic to find it like so

#include <iostream>
#include <vector>

int main(int argc, char *argv[])
{
   std::vector<int> vec;

   for(int i=0; i<10; ++i)
   {
      vec.push_back(i);
   }

   int *ptr=&vec[5];
   int *front=&vec[0];

   std::cout << "Your index=" << ptr-front << std::endl;
   return 0;
}
Adrian Cornish
  • 23,227
  • 13
  • 61
  • 77
0

On the way of learning, I have taken the following notes:

#include <iostream>
#include <vector>

int main() {
    std::vector<std::string> words={"This","is","just","a","trial!"};
    size_t i; //using the contiguous property of a vector:
    for (auto const& elem : words) {
        i = &elem - &*words.begin();// or
        i = &elem - &words.front();// or 
        i = &elem - words.data();// or
        i = std::addressof(elem) - std::addressof(words[0]); 
        if(std::addressof(elem) == &words.front())
          std::cout << elem <<" (at"<<&elem<<") relative to ("<< &words[0] << ") takes position @#"<<i<< std::endl;
        else std::cout << elem <<" (at"<<&elem<< ") takes position @#"<<i<< std::endl;
    }
    return 0;
}

Test run here. It is open to further study (or learn from masters) which one is the most secured/safe and/or most efficient approach.

MathArt
  • 159
  • 7