C++ STL のマップ find() 関数
の マップ::検索() は、マップ内でキーが存在する位置を参照するイテレータまたは定数イテレータを返す C++ STL の組み込み関数です。キーがマップ コンテナーに存在しない場合は、以下を参照するイテレータまたは定数イテレータを返します。 マップ.end()
。
構文：
iterator=map_name.find(key) or constant iterator=map_name.find(key)
パラメーター： この関数は 1 つの必須パラメータを受け入れます 鍵、 マップコンテナ内で検索するキーを指定します。
戻り値: この関数は、マップ内でキーが存在する位置を参照する反復子または定数反復子を返します。キーがマップ コンテナーに存在しない場合は、map.end() を参照するイテレータまたは定数イテレータを返します。
要素検索の時間計算量:
要素を検索するための時間計算量 std::マップ は O(log n) です。要素は内部的に平衡二分探索木 (BST) として保存されるため、最悪の場合でも O(log n) になります。 std::unowned_map 要素がハッシュ テーブルに格納されるため、順序なしマップでの検索中にキーがインデックスとして機能するため、検索の最適な場合と平均的な場合の時間計算量は O(1) になります。ただし、検索の最悪の場合の時間計算量は O(N) です。
以下は上記の関数の図です。
C++
// C++ program for illustration> // of map::find() function> #include> using> namespace> std;> int> main()> {> > // Initialize container> > map <> int> ,> int> >m;>> > // Insert elements in random order> > m.insert({ 2, 30 });> > m.insert({ 1, 40 });> > m.insert({ 3, 20 });> > m.insert({ 4, 50 });> > int> s1=2;> //element1 to find (exist in the map)> > int> s2=5;> //element2 to find (does not exist in the map)> > > cout < <> 'Element '> < if(m.find(s1)!=m.end()){ //if the element is found before the end of the map cout < <' : found : Value : ' < //if the element is present then you can access it using the index } else cout < <' : Not found' < cout < < 'Element ' < if(m.find(s2)!=m.end()){ //if the element is found before the end of the map cout < <' : found : Value : ' < //if the element is present then you can access it using the index } else cout < <' : Not found' < return 0; }> |
出力
Element 2 : found : Value : 30 Element 5 : Not found
時間計算量 : O(log n)
補助スペース ： の上）
以下のコードは、要素を見つけた後にすべての要素を出力するプログラムです。
CPP
// C++ program for illustration> // of map::find() function> #include> using> namespace> std;> int> main()> {> > // Initialize container> > map <> int> ,> int> >mp;>> ;> > cout < <> 'KEY ELEMENT
'> ;> > // find() function finds the position> > // at which 3 is present> > for> (> auto> itr = mp.find(3); itr != mp.end(); itr++) {> > > cout ' ' '
'; } return 0; }> |
出力
Elements from position of 3 in the map are : KEY ELEMENT 3 20 4 50
時間計算量: O(log n)
補助スペース: の上）
