我有一個（C 14）地圖
using MyTuple = tuple<A, B, C> 。
map<MyTuple, MyData>
其中MyTuple具有明顯的operator<()，首先比較A，然后比較B，然后比較C。
我想做一個O(ln N)的搜索，尋找與某個常數(a, b)匹配的鍵。 很明顯，如果有的話，它們將是連續的。 所以基本上我想
map<MyTuple, MyData> my_map = GetMyData();
tuple<A, B> my_key = make_tuple（a, b）。
auto iter = my_map.lower_bound_if([my_key](const MyTuple& key) {
if (get< 0> (my_key) == get<0>（key）&&。
get<1>(my_key) == get<1>(key) {
return true。
}
return false;
});
while( /* iter.first仍然是一個（a,b）*/) {
///對iter.做一些處理。
///增加 iter.。
}
但是沒有函式map::lower_bound_if，然而map::find和map::lower_bound需要一個完整的MyTuple。 我可以(hackishly)找到一個C的值，它比我的資料中的任何東西都低，盡管這隨著時間的推移是脆弱的。 我可以自己撰寫這個函式，盡管它很可能依賴于我當前對 std::map 的本地實作。
我是否錯過了一個明顯的解決方案？
我是否錯過了一個明顯的解決方案？
uj5u.com熱心網友回復：
在c 14中，你可以使用多載來搜索部分鍵：
struct CompareFirstTwo {
using is_transparent = void;
bool operator() const tuple< A, B, C>& lhs, const tuple<A, B, C>& rhs) const 。 ..
bool operator()(const tuple< A, B>& lhs, const tuple<A, B, C>& rhs) const 。 ..
bool operator()(const tuple< A, B, C>& lhs, const tuple<A, B>& rhs) const. ..
}。
在呼叫equal_range時使用上面的比較器來忽略元組中的第三個欄位。
uj5u.com熱心網友回復：
如果你有一個順序，使得x {xa, xb, xc}總是<比y {ya, yb, yc}當f(xa, xb)（反之為>），它變得容易。把它看成是 "先按A和B排序"。
然后你只需要知道你的最大和最小的C值。
在lower_bound(a, b, MIN_C)和upper_bound(a, b, MAX_C)之間搜索。另外，正如評論中所建議的那樣
一個元組的映射<A, B>到C的映射到MyData? - Vlad Feinstein
可以的。
uj5u.com熱心網友回復：
一種方法是將 "你喜歡的任何值 "用于C，使用 lower_bound，并注意你要找的值可能在 lower_bound 之前，也可能在之后，所以你可能需要做一些 operator--來找到第一個，就像你用 operator 來找到最后一個一樣？為了提前找到范圍而進行的運算元量并沒有改變，但是如果你想迭代它們并在運行中測驗<A,B>的結束，就會有提前的開銷。
顯然，如果該 C 是一個 "黑客 "值，將其作為可能的最低 C 進行比較，那將會很方便，但不是必須的，因為這將使后向搜索更快，但我們已經減輕了您的脆弱性風險？
另一個選擇是制作你自己的容器，它是一個地圖的地圖。外層地圖將由 <A,B> 索引，內層地圖由 < C > 索引。
然后你可以添加你自己的方法來實作整個地圖的索引和迭代，使用<A,B,C>，并使用現有的<A,B>方法來回傳索引后的內部地圖，或者回傳你的迭代器作為 lower_bound 和 upper_bound 的結果，然后可以作為所有<A,B,allC>的一個范圍。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/321869.html
標籤：