std::map find distance with iterators, program does not terminate

Question

As I compile ( g++ -std=c++14 map.cpp ) and run this program, it doesn't seem to terminate. Can any one explain Why? However as I do find('a') instead of 'c' it gives a zero.

#include <iostream>
#include <string>
#include <vector>
#include <map> 
#include <algorithm>
using namespace std; 



int main()
{
    map<char, float> m;
    m['a'] = 3.4;
    m['b'] = 5.3;
    m['c'] = 33.3;
    m['d'] = 43.;

    auto it = m.find( 'c' );
    cout << "distance : " << std::distance( it , m.begin() ) << endl;

}

About [using namespace std](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice)... — Aconcagua, Nov 05 '19 at 14:29

Vlad from Moscow · Accepted Answer · 2019-11-05T13:10:02.330

6

Use

std::distance( m.begin(), it  )

Otherwise the call

std::distance( it , m.begin() )

has undefined behavior because there is used an invalid range. Ranges in C++ are specified like [first, last ) where first precedes or equal to last. In the last case when first is equal to last the range is empty.

From the C++ Standard (27.4.3 Iterator operations)

4 Effects: If InputIterator meets the requirements of random access iterator, returns (last - first); otherwise, returns the number of increments needed to get from first to last.

edited Nov 05 '19 at 13:10

answered Nov 05 '19 at 12:53

Vlad from Moscow

301,070
26
186
335

Could you clarify *why* it's an invalid range? – Borgleader Nov 05 '19 at 12:56

score 3 · Answer 2 · answered Nov 05 '19 at 12:56

3

std::distance(first,last) starts running from first and advances the iterator until it reaches the last. In your case this will never happen because it is most likely found after m.begin() so it'll loop forever. change the order of parameters given to std::distance

std::distance reference:

The behavior is undefined if last is not reachable from first by (possibly repeatedly) incrementing first.

answered Nov 05 '19 at 12:56

Shloim

5,281
21
36

Hm... Most likely (unless we crash instead), at some point the pointer value will overflow, and we restart from null pointer onwards again (all this undefined behaviour, of course), then finally reach at some point the begin() iterator again. So we indeed *would* stop at some point. Provided difference type is not larger than type of pointer, we'd even get negative value of desired distance due to overflow (well, UB again, if difference type is signed)... – Not criticism, just mentioning a funny issue ;) – Aconcagua Nov 05 '19 at 14:26

std::map find distance with iterators, program does not terminate

2 Answers2