Equivalent of C++ map.lower_bound in Java

Question

My question is very basic, but I couldn't find the solution myself.

I am used to writing algorithms in C++. There I very often use the std::map structure, together with all the auxiliary methods it provides.

This method returns iterator to the first element of the map with key >= to the key given as parameter. Example:

map<int, string> m;
// m = { 4 => "foo", 6 => "bar", 10 => "abracadabra" }
m.lower_bound(2); // returns iterator pointing to <4, "foo">
m.lower_bound(4); // returns iterator pointing to <4, "foo">
m.lower_bound(5); // returns iterator pointing to <6, "bar">

The cool thing is that the C++ map is based on red-black trees and so the query is logarithmic (O(log n)).

Now I need to implement a certain algorithm in Java. I need similar functionality as the one I just described. I know I can use TreeMap which is implemented in ordered tree. However I don't seem to find equivalent of the method lower_bound. Is there such?

Thank you very much for your help.

Clayton

Answer 1

I guess that you're looking for TreeMap. Take a look at ceilingKey/Entry methods.

Runabout

Thanks I should have looked more carefully, but I somehow thought it should be a method declared directly in TreeMap. – Clayton

I think ceilingEntry method is an exact equivalent of std::lower_bound, while lowerEntry is very similar but still different. – Eringo

Answer 2

I hope this works for you?

SortedMap tail = <Sorted Map Object>.tailMap(target);
if (!tail.isEmpty())
{
    upper = tail.firstKey();
}

Depredate

This seems more resource-consuming and harder to use than the suggestion of @Nikola – Clayton

Actually it turned out you were the one to actually help me, because I am developing for android and the above mentioned method ('lowerEntry`) is not available there. – Clayton

Answer 3

This is a test case that shows behaviour:

@Test
public void testPrefixMatch() {

    treeMap.put("1.2.3", "bar");
    treeMap.put("1.2.3.4", "bar");
    treeMap.put("1.2.3.5.6", "bar");


    assertEquals("1.2.3.5.6", treeMap.ceilingKey("1.2.3.4.5.6.7"));
    assertEquals("1.2.3.4", treeMap.floorKey("1.2.3.4.8.6"));
    assertEquals("1.2.3.5.6", treeMap.ceilingKey("1.2.3.4.8.6"));
}

Ingeborg

In what sense you mean his suggestion is not working correctly? I think he suggests exactly the same as you did. – Clayton

the suggestion is to use ceilingkey. floorKey is the right to use. – Ingeborg

I think you are wrong into the understanding how lower_bound works in C++. It actually fetches the first key that is >= of the given key. – Clayton

Ah i see. You are right redacted the answer.thanks for pointing – Ingeborg

Answer 4

kind of similar:

In C++

vector   lower_bound  return the index

In Java

TreeSet  higher       return the Key

James