std::map - decrement iterator gives strange result?

user_527037 0
Viewed 74

Can't seem to work this out. Simple example as follows:

#include <iostream>
#include <map>

int main() {

    std::map<uint32_t, char> m;
    
    m[1] = 'b';
    m[3] = 'd';
    m[5] = 'f';
    
    std::map<uint32_t, char>::iterator i = m.lower_bound('d');
    
    std::cout << "First: " << i->first << std::endl;
    
    // Decrement the iterator
    i--;
    
    // Expect to get 1, but get 5?
    std::cout << "Second: " << i->first << std::endl;

    return 0;
}

The output is:

First: 3
Second: 5

Why do I get 5 here? I thought decrementing the iterator would result in it pointing at key 1

undefined-behavior iterator dictionary algorithm c++
2 Answers

This call

std::map<uint32_t, char>::iterator i = m.lower_bound('d');

returns the iterator m.end(). So dereferencing the iterator

std::cout << "First: " << i->first << std::endl;

results in undefined behavior.

The member function lower_bound expects an argument that specifies a key not value.

Consider the following demonstration program.

#include <iostream>
#include <iomanip>
#include <map>
#include <cstdint>

int main()
{
    std::map<uint32_t, char> m;

    m[1] = 'b';
    m[3] = 'd';
    m[5] = 'f';

    std::map<uint32_t, char>::iterator i = m.lower_bound( 'd' );

    std::cout << "i == m.end() is " << std::boolalpha << ( i == m.end() ) << '\n';
}

The program output is

i == m.end() is true

Instead you could write for example

std::map<uint32_t, char>::iterator i = m.lower_bound( 5 );

After decrementing the iterator after this call

std::map<uint32_t, char>::iterator i = m.lower_bound('d');

it points to the last element of the map.

user_28772410

lower_bound takes as input the key, not the value. This would do as you expect:

std::map<uint32_t, char>::iterator i = m.lower_bound(3);

With the lower_bound you are using, you end up finding end() and iterating back one.

user_44742300
Related