Printing the index of an iterator in std::map

Question

I am using the find() method of std::map, which returns an iterator.
However I need the index of the found element; for example: 0, which corresponds to std::map::begin(), and so on.

#include <map>
#include <utility>
#include <iostream>

int main()
{
  std::map< int, int > aMap;
  aMap.insert( std::make_pair(100, 50) );
  aMap.insert( std::make_pair(200, 40) );
  aMap.insert( std::make_pair(300, 60) );

  std::map< int, int >::iterator it_map = aMap.find(300);
  if (it_map != aMap.end())
    std::cout << it_map << "\n"; // error

}

That doesn't compile and I know the reason. However, I need a way to print 2 because the index of 300 is 2.

For that simple example, you may say that map (binary tree) is not a good container. However, in the real code, there are tons of elements that I have to search and binary tree is good for that.

Any idea?

Answer 1

If you need the index, then perhaps a map is the wrong data type; you need to iterate through the map (in linear time) to find the index, losing the benefit of the logarithmic-time search.

Perhaps a sorted vector, using the lower_bound algorithm to find elements in logarithmic time, might be more suitable. Then you can subtract the resulting random-access iterator from the begin() iterator in constant time.

Nevertheless, if you do want to use a map:

std::cout << std::distance(aMap.begin(), it_map) << '\n';

Answer 2

Use std::distance, like this :

std::cout << std::distance(std::begin(aMap),it_map) << endl;

Documentation here