C++地圖開始搜索

使用找到一個std ::地圖上得到一個迭代器指向所需的元素對後，是否有可能重新使用在隨後的發現，迭代器（）的利用是否知道即將查找的元素接近第一個找到的元素？喜歡的東西：

std::map<key, value> map_elements; 
std::map<key, value>::iterator it; 

it = map_elements.find(some_key); 
it = it.find(a_close_key)

預先感謝您

來源

2013-07-21 Gallium Nitride

你的問題是不完整的多遠Item1（由map :: find找到）可以遠離Item2。在某些情況下，更有效地製作新的map::find;在某些情況下，您可以迭代迭代器來查找第二個項目的位置。只使用搜索map::find這將是O（log n）的複雜性，它可以大約10-20步。所以，如果你知道你的Item2不是目前爲止，你可以迭代it迭代器來找出它。這裏最重要的是如何檢查你必須停止搜索。 std::map默認使用std::less<T>來排列項目，所以它可以用來找出容器根本不包含Item2。事情是這樣的（未測試）：

std::map<key, value> map_elements; 
std::map<key, value>::iterator it, it2; 

it2 = it = map_elements.find(some_key); 
bool found=false; 
while(it2!=map_elements.end() && !(a_close_key < it2->first)) { 
    if(!(a_close_key < it2->first) && !(it2->first < a_close_key)) { 
     //Equivalency is not ==, but its what used in std::map 
     found=true; 
     break; 
    } 
    it2++; 
} 
if(found) { 
    //.... use it2 
}

裏面if(found)阻止你的迭代it2值應該是一樣的，如果你叫map_elements.lower_bound(a_close_key)

來源

2013-07-21 04:56:09 PSIAlt

它的一個pitty C++沒有提供map :: find（）的優雅方法來開始給定的迭代器...它看起來像我會採取你的建議和interate我自己在地圖上。謝謝！ –

對不起，還是一個SO新手;）警告！ –

如果你確定這是真的附近，您可以使用（而不是map::find）std::find做該項目的線性搜索。如果它位於當前位置的大約log（N）項內，這很可能是一個勝利（其中N是地圖中的項目數）。

另外請注意，你必須搞清楚你是否想在當前位置之前或之後進行搜索，並指定current，end()如果是後，並begin(), current如果它之前。如果是以前，你會想要做一個反向搜索（find_end，如果內存服務），因爲目標大概接近該範圍的末尾。

來源

2013-07-21 04:35:05

這是一個完美的解決方案......只是難過不採取優勢列表被排序，因此，在「無限列表」中，如果沒有找到元素，它將迭代所有項目...這比map :: find更糟糕。豎起大拇指，因爲它可以對別人有用，謝謝！ PS：對不起，我沒有投票的聲望... –

C++地圖開始搜索

回答

相關問題