Tương đương với C++ map.lower_bound trong Java

Question

Câu hỏi của tôi rất cơ bản, nhưng tôi không thể tự tìm ra giải pháp.

Tôi đã quen với việc viết các thuật toán trong C++. Ở đó tôi thường sử dụng cấu trúc std::map, cùng với tất cả các phương thức phụ trợ mà nó cung cấp.

Phương thức này trả về trình vòng lặp cho phần tử đầu tiên của bản đồ bằng khóa> = đến khóa được cho làm tham số. Ví dụ:

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"> 

Điều thú vị là bản đồ C++ dựa trên cây đỏ đen và do đó truy vấn là logarit (O(log n)).

Bây giờ tôi cần triển khai một thuật toán nhất định trong Java. Tôi cần chức năng tương tự như chức năng tôi vừa mô tả. Tôi biết tôi có thể sử dụng TreeMap được triển khai trong cây có thứ tự. Tuy nhiên tôi dường như không tìm thấy tương đương với phương thức lower_bound. Có cái đó không?

Cảm ơn bạn rất nhiều vì sự giúp đỡ của bạn.

Answer 1

Tôi đoán bạn đang tìm kiếm TreeMap. Hãy xem xét các phương pháp trần/nhập.

Answer 2

Tôi hy vọng điều này phù hợp với bạn?

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

Answer 3

Đây là một trường hợp thử nghiệm cho thấy hành vi:

@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")); 
} 

Answer 4

loại tương tự:

Trong C++

vector lower_bound return the index 

Trong Java

TreeSet higher  return the Key