std :: map

Question

içerisinde en yakın veya tam anahtarı bulmak Bir süreyi bir zaman aralığına bağlayan bir arama tablosu oluşturmam gerekiyor (ikisi de veri türü çiftidir). Anahtarlar, eklendikçe doğrusal olarak artar, bu yüzden zaten sıralanacaktır (belki de bir unordered_map daha iyi olur mu?).

Aradığım şey, zaman değerini elde etmek için sağlanan geçerli uzunlukla en iyi eşleşen bir anahtarı bulmanın veya daha uzun olanı çevreleyen iki anahtarın (verilen anahtar aralarında) bulunmasını sağlamaktır. iki zaman değeri arasındaki enterpolasyonlu değeri bulabilir.

Ayrıca gerçek zamanlı olarak çağrılacağı için mümkün olan en iyi performansa ihtiyacım var.

DÜZENLEME: Aşağıdakine aşağıdaki ilk yanıtın bir yorumu vardı, ancak formatın okunması zor.

ben aşağıdakileri yapmaya çalıştım ama aynı yineleyici (5.6) dönmek gibi görünüyor:

std::map<double, double> map; 
map.insert(std::pair<double, double>(0.123, 0.1)); 
map.insert(std::pair<double, double>(2.5, 0.4)); 
map.insert(std::pair<double, double>(5.6, 0.8)); 

std::map<double, double>::iterator low, high; 
double pos = 3.0; 
low = map.lower_bound(pos); 
high = map.upper_bound(pos); 

kullandığım anahtarın daha < olan son öğeye işaret edecek 'düşük' alacağı nasıl aramak?

DÜZENLEME 2: Aptal ben, 'düşük--' ilk öğeyi sağlamayan, bunu yapacaktır.

Ulaşım :)

Answer 1

Bunun için, ya std::map::lower_bound

tuşunun az olmadığı ilk elemana işaret bir yineleyici döndürür kullanabilirsiniz.

veya std::map::equal_range kap içinde verilen anahtar ile tüm elemanları ihtiva eden bir dizi döner. Bunun için en yakın giriş isterseniz durumda

---

, daha önce iade girişi ve bir hem kontrol ve farklılıkları karşılaştırmak gerekir. Böyle bir şey

std::map<double, double>::iterator low, prev; 
double pos = 3.0; 
low = map.lower_bound(pos); 
if (low == map.end()) { 
    // nothing found, maybe use rbegin() 
} else if (low == map.begin()) { 
    std::cout << "low=" << low->first << '\n'; 
} else { 
    prev = std::prev(low); 
    if ((pos - prev->first) < (low->first - pos)) 
     std::cout << "prev=" << prev->first << '\n'; 
    else 
     std::cout << "low=" << low->first << '\n'; 
} 

Answer 2

Yapabilirsin yürütmesinde logaritmik olan kurs kullanım LOWER_BOUND ve UPPER_BOUND ait. Ve istediklerini yapmalılar.

std::map<double,double>::iterator close_low; 
//... your_map ... 
close_low=your_map.lower_bound (current_length); 

Bu, anahtar < akım uzunluğu ilk harita elemana bir yineleyici vermelidir. Aynı şekilde upper_bound ile yapın ve zamanınızı kuşattırabilirsiniz.

Answer 3

fonksiyonlarını std::lower_bound() işe yarayabilecek ve std::upper_bound() burada faydalı olacaktır.

lower_bound(), aradığınız değere >= olan ilk öğeyi verir; upper_bound(), bu değerden > olan ilk öğeyi verir.upper_bound() beşinci elemanı dönmek ise lower_bound() döner üçüncü eleman kullanılarak {1,3,5,5,6} , aşağıdaki listede değeri 5 aramaya Örneğin

. İki işlev aynı şeyi x döndürürse, aradığınız değer listede yok. x-1'dan hemen önceki değer ve x'dan sonraki değer.

_{gibi genellikle yinelenen unsurları içermeyen bir yorumun, haritalar istedi Söz, içinde Tony D tarafından işaret etti. İki örneği göstermek için bu örneği saklıyorum.}

Answer 4

"en iyi performansı sağlamak" - Daha iyi önbellek kullanımı alırsınız veri bitişik adrese dolu olacak çünkü - Bir std::vector içine push_back/emplace_back bunları daha sonra std::lower_bound kullanabilirsiniz, size artan sırayla öğeler eklemek verilen alanı.