Equivalente di C++ map.lower_bound in Java

La mia domanda è molto semplice, ma non sono riuscito a trovare la soluzione da solo.Equivalente di C++ map.lower_bound in Java

Sono abituato a scrivere algoritmi in C++. Lì utilizzo molto spesso la struttura std::map, insieme a tutti i metodi ausiliari che fornisce.

Questo metodo restituisce iteratore al primo elemento della mappa con chiave> = alla chiave fornita come parametro. Esempio:

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

La cosa interessante è che la mappa C++ si basa su alberi rosso-nero e così la query è logaritmica (O(log n)).

Ora ho bisogno di implementare un determinato algoritmo in Java. Ho bisogno di funzionalità simili a quella che ho appena descritto. So che posso usare TreeMap che è implementato nell'albero ordinato. Tuttavia, non riesco a trovare l'equivalente del metodo lower_bound. Esiste?

Grazie mille per il vostro aiuto.

fonte

2012-03-07 Boris Strandjev

Immagino che stiate cercando TreeMap. Dai un'occhiata ai metodi ceilingKey/Entry.

fonte

2012-03-07 09:30:22

Grazie avrei dovuto guardare più attentamente, ma in qualche modo ho pensato che dovrebbe essere un metodo dichiarato direttamente in 'TreeMap'. –

Penso che il metodo 'ceilingEntry' sia un equivalente esatto di' std :: lower_bound', mentre 'lowerEntry' è molto simile ma ancora diverso. – stgatilov

Penso che tu abbia ragione, modificherò la mia risposta. –

Spero che questo funzioni per voi?

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

fonte

2012-03-07 09:29:04

Questo sembra più profilo delle risorse consumare e più difficile da usare rispetto al suggerimento di @ Nikola –

In realtà si è scoperto che tu eri quello che effettivamente mi aiuti, perché sto sviluppando per Android e il metodo sopra menzionato ('lowerEntry') non è disponibile lì. –

Questo è un test che mostra un comportamento:

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

fonte

2018-01-16 11:58:07 Alex

In che senso intendi che il suo suggerimento non funziona correttamente? Penso che suggerisca esattamente la stessa cosa che hai fatto tu. –

il suggerimento è di usare ceilingkey. floorKey è il diritto di usare. – Alex

Penso che tu abbia torto nella comprensione di come 'lower_bound' funzioni in C++. In realtà recupera la prima chiave che è> = della chiave data. –

natura simile:

In C++

vector lower_bound return the index

In Java

TreeSet higher  return the Key

fonte

2018-02-04 20:54:54

Equivalente di C++ map.lower_bound in Java

risposta

Problemi correlati