What is the most effective way to get the index of an iterator of an std vector

Question

I m iterating over a vector and need the index the iterator is currently pointing at  AFAIK this can be done in two ways    it - vec begin   std  distance vec begin    it    What are the pros and cons of these methods

User · Answer

If you are already restricted hardcoded your algorithm to using a std  vector  iterator and std  vector  iterator only  it doesn t really matter which method you will end up using  Your algorithm is already concretized beyond the point where choosing one of the other can make any difference  They both do exactly the same thing  It is just a matter of personal preference  I would personally use explicit subtraction   If  on the other hand  you want to retain a higher degree of generality in your algorithm  namely  to allow the possibility that some day in the future it might be applied to some other iterator type  then the best method depends on your intent  It depends on how restrictive you want to be with regard to the iterator type that can be used here    If you use the explicit subtraction  your algorithm will be restricted to a rather narrow class of iterators  random-access iterators   This is what you get now from std  vector  If you use distance  your algorithm will support a much wider class of iterators  input iterators    Of course  calculating distance for non-random-access iterators is in general case an inefficient operation  while  again  for random-access ones it is as efficient as subtraction   It is up to you to decide whether your algorithm makes sense for non-random-access iterators  efficiency-wise  It the resultant loss in efficiency is devastating to the point of making your algorithm completely useless  then you should better stick to subtraction  thus prohibiting the inefficient uses and forcing the user to seek alternative solutions for other iterator types  If the efficiency with non-random-access iterators is still in usable range  then you should use distance and document the fact that the algorithm works better with random-access iterators

User · Answer

I just discovered this  https   greek0 net boost-range boost-adaptors-indexed html     for  const auto  amp  element   str   boost  adaptors  indexed 0             std  cout  lt  lt  element index                      lt  lt   quot     quot                     lt  lt  element value                      lt  lt  std  endl

User · Answer

As UncleBens and Naveen have shown  there are good reasons for both  Which one is  better  depends on what behavior you want  Do you want to guarantee constant-time behavior  or do you want it to fall back to linear time when necessary   it - vec begin   takes constant time  but the operator - is only defined on random access iterators  so the code won t compile at all with list iterators  for example   std  distance vec begin    it  works for all iterator types  but will only be a constant-time operation if used on random access iterators   Neither one is  better   Use the one that does what you need

User · Answer

Beside int float string etc   you can put extra data to  second when using diff  types like  std  map lt unsigned long long int  glm  ivec2 gt  voxels corners  std  map lt unsigned long long int  glm  ivec2 gt   iterator it corners   or struct voxel map       int x i      std  map lt unsigned long long int  voxel map gt  voxels corners  std  map lt unsigned long long int  voxel map gt   iterator it corners   when long long unsigned int index first some key     llu in this case    int i 0  voxels corners insert std  make pair index first glm  ivec2 1 i        or long long unsigned int index first some key  int index counter 0  voxel map one  one x 1  one i index counter     voxels corners insert std  make pair index first one     with right type    structure you can put anything in the  second including a index number that is incremented when doing an insert  instead of it corners -  corners begin    or std  distance it corners begin    it corners   after it corners   voxels corners find index first bdif x x z    the index is simply  int vertice index   it corners- gt second y   when using the glm  ivec2 type or int vertice index   it corners- gt second i   in case of the structure data type

User · Answer

Here is an example to find  all  occurrences of 10 along with the index  Thought this would be of some help   void  find all test         vector lt int gt  ints      int val      while cin  gt  gt  val  ints push back val        vector lt int gt   iterator it      it   ints begin        int count   ints size        do               it   find it ints end    10    assuming 10 as search element         cout  lt  lt   it  lt  lt    found at index    lt  lt  count - ints end   - it   lt  lt  endl       while   it    ints end

User · Answer

I would prefer std  distance vec begin    it  as it will allow me to change the container without any code changes  For example  if you decide to use std  list instead of std  vector which doesn t provide a random access iterator your code will still compile  Since std  distance picks up the optimal method depending on iterator traits you ll not have any performance degradation either

User · Answer

I like this one  it - vec begin    because to me it clearly says  distance from beginning   With iterators we re used to thinking in terms of arithmetic  so the - sign is the clearest indicator here

User · Answer

According to http   www cplusplus com reference std iterator distance   since vec begin   is a random access iterator  the distance method uses the - operator   So the answer is  from a performance point of view  it is the same  but maybe using distance   is easier to understand if anybody would have to read and understand your code

User · Answer

I would prefer it - vec begin   precisely for the opposite reason given by Naveen  so it wouldn t compile if you change the vector into a list  If you do this during every iteration  you could easily end up turning an O n  algorithm into an O n 2  algorithm   Another option  if you don t jump around in the container during iteration  would be to keep the index as a second loop counter   Note  it is a common name for a container iterator std  container type  iterator it

User · Answer

I d use the - variant for std  vector only - it s pretty clear what is meant  and the simplicity of the operation  which isn t more than a pointer subtraction  is expressed by the syntax  distance  on the other side  sounds like pythagoras on the first reading  doesn t it    As UncleBen points out  - also acts as a static assertion in case vector is accidentially changed to list   Also I think it is much more common - have no numbers to prove it  though  Master argument  it - vec begin   is shorter in source code - less typing work  less space consumed  As it s clear that the right answer to your question boils down to be a matter of taste  this can also be a valid argument

[c++] What is the most effective way to get the index of an iterator of an std::vector?

Examples related to c++

Examples related to iterator

Examples related to coding-style