C++映射，找到第一個小於鍵的元素

Question

我正在尋找一個類似於C++映射的數據結構。

我正在尋找一個函數，可以返回第一個元素，立即少於一定數量。例如：

map<int,int> m; 
m[1] ++; 
m[2] ++; 
m[4] ++; 
m[5] ++; 

find_first_element_less_than(3) ----> return 2; 
m.upper_bound(3) ---> return 4; 

我看了一下lower_bound函數。但是，它表示它返回的第一個元素不小於關鍵字。在這種情況下，lower_bound（3）返回4.這不是我想要的。

我想知道是否有任何數據結構在C++中可以爲我做這個？

---

更新：

我可以做auto it = m.lower_bound(3); if (it != m.begin()) it--;？

Answer 1

你可以找到下界，然後如果迭代器沒有指向地圖的開始，則迭代器減1。

Answer 2

我想你可以通過顛倒你的地圖的順序（map<int,int, std::greater<int> > m;），然後使用upper_bound找到第一項「更大」（但確實更少，因爲你倒置謂詞）比請求的項目。如果您需要按升序進行迭代，則必須使用反向迭代器，這可能會對維護人員（包括您自己）產生一些困惑。仔細考慮您對這個可能的解決方案的需求。