C++ STL의 map find() 함수
그만큼 지도::찾기() 맵에서 키가 존재하는 위치를 참조하는 반복자 또는 상수 반복자를 반환하는 C++ STL의 내장 함수입니다. 키가 맵 컨테이너에 없으면 반복자 또는 다음을 참조하는 상수 반복자를 반환합니다. 지도.끝()
.
통사론:
iterator=map_name.find(key) or constant iterator=map_name.find(key)
매개변수: 이 함수는 하나의 필수 매개변수를 허용합니다. 열쇠, 이는 맵 컨테이너에서 검색할 키를 지정합니다.
반환 값: 이 함수는 맵에서 키가 존재하는 위치를 참조하는 반복자 또는 상수 반복자를 반환합니다. 키가 맵 컨테이너에 없으면 map.end()를 참조하는 반복자 또는 상수 반복자를 반환합니다.
요소 검색의 시간 복잡도:
요소 검색의 시간 복잡도 표준::지도 O(log n)입니다. 최악의 경우에도 요소는 내부적으로 BST(Balanced Binary Search Tree)로 저장되므로 O(log n)이 됩니다. 표준::순서가 없는_맵 검색에 대한 최상의 경우 및 평균 경우의 시간 복잡도는 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(로그 n)
보조 공간 : 에)
아래 코드는 요소를 찾은 후 모든 요소를 인쇄하는 프로그램입니다.
CPP
// C++ program for illustration> // of map::find() function> #include> using> namespace> std;> int> main()> {> > // Initialize container> > map <> int> ,> int> >mp;> > // Insert elements in random order> > mp.insert({ 2, 30 });> > mp.insert({ 1, 40 });> > mp.insert({ 3, 20 });> > mp.insert({ 4, 50 });> > cout < <> 'Elements from position of 3 in the map are :
'> ;> > 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(로그 n)
보조 공간: 에)
