5
\$\begingroup\$

I wanted something equivalent to this Java program:

TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>();
    map.put(10, 100);
    map.put(20, 200);
    map.put(30, 300);
    map.put(40, 400);
    map.put(50, 500);
    map.put(60, 600);
    map.put(70, 700);
    map.put(80, 800);

    System.out.println(map.floorKey(5));
    System.out.println(map.floorKey(9));
    System.out.println(map.floorKey(10));
    System.out.println(map.floorKey(11));
    System.out.println(map.floorKey(90));

output:

null null 10 10 80

As there is no direct API to achieve the same in C++, I wrote the following code to implement a similar floorKey() function:

template <typename key,typename value>
int floorKey(map<key, value> input, int key)
{
    auto begin = input.begin();
    if (begin->first > key)//if key is less than the first key. It must retrun -1;
        return -1;

    auto end = input.end();
    end--;
    if (end->first < key)//if key is greater than last key, it must return last key
        return end->first;

    //if key is equal to any existing key, it should return the key
    auto find = input.find(key);

    if (find != input.end())
        return key;

    //Return the floor key for the given key
    auto lower = input.lower_bound(key);

    lower--;
    return lower->first;
}

Here's the test program:

int main()
{
    map<int, int> map;
    map.insert({ 10, 100 });
    map.insert({ 20, 200 });
    map.insert({ 30, 300 });
    map.insert({ 40, 400 });
    map.insert({ 50, 500 });
    map.insert({ 60, 600 });
    map.insert({ 70, 700 });
    map.insert({ 80, 800 });


    cout << floorKey(map, 5) << endl;
    cout << floorKey(map, 9) << endl;
    cout << floorKey(map, 10) << endl;
    cout << floorKey(map, 11) << endl;
    cout << floorKey(map, 90) << endl;
    return 0;
}

output:

-1 -1 10 10 80

Is there any better way to get the same? Anything else I can improve?

\$\endgroup\$
10
\$\begingroup\$

Headers and namespaces

The function is missing a definition of map. This is probably what you want:

#include <map>

using std::map;

Similarly, the main() needs:

#include <iostream>
using std::cout;
using std::endl;

That said, there's no good reason for std::endl in this code: an ordinary newline is sufficient, and we don't need the extra flushing behaviour of std::endl.

Naming

It's an error to use the typename key as the name of a parameter here:

template <typename key,typename value>
int floorKey(map<key, value> input, int key)

It's pretty idiomatic to use PascalCase for template arguments, to distinguish them from function parameters:

template<typename Key, typename Value>
int floorKey(std::map<Key, Value> input, Key key)

(I've also corrected the function to accept the correct type for the key argument).

There's a similar problem in main(), where we have a conflict between the type map and our identifier map. This is one of the reasons I'd argue against bringing the type name into the global namespace.

Don't pass containers by value

We have a potentially large map, which we don't need to modify. That suggests that it's better passed as a reference to a const object. As we don't know the type of the key, we should probably assume that it's also better passed by reference (it could plausibly be a std::string, for example). That gives us:

template<typename Key, typename Value>
int floorKey(const std::map<Key, Value>& input, const Key& key)

It's good that we used auto for the iterators begin and end, as it means that we don't need to change the body of the function to deal with them both now being const iterators.

Think about edge cases

What happens in this code when the input argument is an empty map? We dereference input.first() without checking whether it's equal to input.end(), giving Undefined Behaviour at that point.

Algorithm

There's really no need to search for an exactly matching key if we then go on to call lower_bound() - we could just call upper_bound() instead, which will find the first key that's strictly greater than key, then decrement (if doing so is valid) to get the result:

auto it = input.upper_bound(key);

return it == input.begin()
    ? -1
    : (--it)->first;

Note that we have a problem here: if Key isn't a signed numeric type, then we can't return -1. We really need a type-dependent value for this. Better still, return a std::optional, so a defaulted value can be clearly distinguished from an actual result.


Modified code

#include <map>
#include <optional>

template<typename Key, typename Value>
std::optional<Key> floorKey(const std::map<Key,Value>& input,
                            const Key& key)
{
    if (auto it = input.upper_bound(key);  it != input.begin()) {
        return (--it)->first;
    } else {
        return std::nullopt;
    }
}
#include <iostream>

int main()
{
    std::map<int, int> map =
        {
         { 10, 100 },
         { 20, 200 },
         { 30, 300 },
         { 40, 400 },
         { 50, 500 },
         { 60, 600 },
         { 70, 700 },
         { 80, 800 },
        };


    std::cout << floorKey(map, 5).value_or(-1) << '\n'
              << floorKey(map, 9).value_or(-1) << '\n'
              << floorKey(map, 10).value_or(-1) << '\n'
              << floorKey(map, 11).value_or(-1) << '\n'
              << floorKey(map, 90).value_or(-1) << '\n';
}
\$\endgroup\$
  • \$\begingroup\$ Yes, that's a really good suggestion. \$\endgroup\$ – Toby Speight Jun 20 at 7:20
8
\$\begingroup\$

Your code is obviously wrong:

template <typename key,typename value>

This line suggests that the code works for arbitrary maps, yet you require an int key, no matter what the key type of the map is.

Returning -1 is not proper C++ style. You should return an iterator, as all other container functions do.

Passing the map by value makes an unnecessary copy of the whole map. Use a const & instead.

\$\endgroup\$
2
\$\begingroup\$

You know about lower_bound/upper_bound; why not use just once and then see if the iterator is at the beginning and where the key in the returned iterator lands compared to the given key?

template <typename key,typename value>
int floorKey(map<key, value> input, int key)
{
    auto greater = input.upper_bound(key);

    if(greater == input.begin()) 
        return -1;

    assert(greater->first > key);

    --greater;
    return greater->first;
}

upper_bound always returns an iterator that is just past the key. So decrement it to get the floor.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.