2012-03-07 24 views
6

私の質問は非常に基本的ですが、自分で解決策を見つけることができませんでした。JavaのC++ map.lower_boundに相当します。

私はC++でアルゴリズムを書くのに慣れています。ここでは、多くの場合、std::map構造体と、それが提供するすべての補助メソッドを使用します。

このメソッドは、キー> =を持つマップの最初の要素にパラメータとして与えられたキーを返します。例:

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

クールなことは、C++マップは赤黒木に基づくので、クエリは(O(log n))対数であることです。

私はJavaで特定のアルゴリズムを実装する必要があります。私は今説明したのと同じ機能が必要です。私はTreeMapを使用することができ、順序付けられたツリーで実装されていることを知っています。しかし、私は方法lower_boundと同等のものを見つけることはできないようです。そんなことはありますか?

ありがとうございました。

答えて

6

私はあなたがTreeMapを探していると思います。 ceilingKey/Entryメソッドを見てください。

+0

私はもっと慎重に見ていたはずですが、どういうわけか、それは 'TreeMap'で直接宣言されたメソッドでなければならないと思っていました。 –

+1

'ceilingEntry'メソッドは' std :: lower_bound'と全く同じだと思いますが、 'lowerEntry'は非常に似ていますが、それでも違いはあります。 – stgatilov

+0

私はあなたが正しいと思う、私は私の答えを編集します。 –

1

私はこれがうまくいきたいですか?

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

これは、より多くの資源です消費者はより多くの@Nikola –

+0

実際には、私はアンドロイドのために開発しており、上記の方法( 'lowerEntry')が利用できないため、あなたが実際に私を助けてくれたことが判明しました。 –

0

これは挙動を示しているテストケースである:類似したの

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

どのような意味で彼の提案が正しく機能していないということですか?私は彼があなたとまったく同じことを示唆していると思う。 –

+0

提案はceilingkeyを使用することです。 floorKeyは使用する権利です。 – Alex

+1

私は 'lower_bound'がC++でどのように動作するのか理解していないと思います。実際には、指定されたキーの> =である最初のキーをフェッチします。 –

0

種類:C++で

vector lower_bound return the index 
のJava

TreeSet higher  return the Key 
関連する問題