CODEWITHSUNDEEP
c++dictionary
Manikandaraj Srinivasan
Manikandaraj Srinivasan

Reputation: 3647

Find upper_bound of a String Key in STL Map

Find upper_bound of a String Key in STL Map

I'm trying to find the upper_bound of String Key in STL Map , but its not giving me the exact result. If you can run this program, you will find the result as weird, both upper & lower bounds pointing to "qwerzzx"

Is there any mistake in my Code or i'm misinterpretating upper bound operation ..?

#include<iostream> 
#include<cstring>
#include <map>
using namespace std;
int main()
{
    map<string, int> testmap;
    map<string, int>::iterator poslow;
    map<string, int>::iterator posup;

    testmap.insert(make_pair<string, int>("asdfghjkliopp", 1));
    testmap.insert(make_pair<string, int>("asdfghjklioppswert", 1));
    testmap.insert(make_pair<string, int>("sdertppswert", 1));
    testmap.insert(make_pair<string, int>("sdertppswedertyuqrt", 1));
    testmap.insert(make_pair<string, int>("qwerzzx", 1));
    testmap.insert(make_pair<string, int>("qwerzzxasdf", 1));
    testmap.insert(make_pair<string, int>("qwsdfgqwerzzx", 1));
    testmap.insert(make_pair<string, int>("xcvbqwsdfgqwerzzx", 1));
    testmap.insert(make_pair<string, int>("xcvbqwsdersdfgqwerzzx", 1));
    poslow = testmap.lower_bound("qw");
    posup = testmap.upper_bound("qw");
    cout<<"Lower POS  ::: "<<poslow->first<<" UPPER POS :: "<<posup->first<<"\n";
    testmap.erase(poslow, posup);
}

Upvotes: 3

Views: 2550

Answers (2)

Ivan Vergiliev
Ivan Vergiliev

Reputation: 3841

Upper bound gives you the last position where you can insert the argument, while still keeping the sequence sorted (whereas lower_bound gives you the first such position). Since "qw" is lexicographically smaller than "qwerzzx", that's both the lower and upper bound for that word.

In other words, [lower_bound, upper_bound) is the interval of elements that are equal to the argument - and in this case, it is empty.

If your intention is to find the last word with this prefix, you can try appending some characters in the end to make sure it's lexicographically larger than the last one in the map. For example, if you only have alphabetical characters, you can lookup the character right after 'z' in the ASCII table and append it to "qw". This way you should be able to get an iterator to, in your case, "xcvbqwsdfgqwerzzx".

Upvotes: 5

Mark Ransom
Mark Ransom

Reputation: 308206

Upper bound returns the item that is greater than the search key. Lower bound returns the item that is greater than or equal. In this case they're both the same, since there's nothing in the map that's equal.

The intent is that both of them return a position where the item could be inserted prior to and still retain the sorted order. lower_bound would put it at the front of the range and upper_bound would put it at the end.

Upvotes: 2

Related Questions