수색…
비고
std::map또는std::multimap하려면 헤더 파일<map>을 포함해야합니다.std::map과std::multimap은 키의 오름차순에 따라 정렬 된 요소를 유지합니다.std::multimap의 경우 동일한 키 값에 대한 정렬이 발생하지 않습니다.기본적인 차이
std::map및std::multimap이다std::map하나가 같은 키에 대해 중복 값을 허용하지 않는std::multimap한다.지도는 이진 검색 트리로 구현됩니다. 그래서
search(),insert(),erase()는 Θ (log n) 시간을 평균으로 취합니다. 일정 시간 동안 작동하려면std::unordered_map.size()및empty()함수는 Θ (1) 시간 복잡도를 가지므로 이러한 함수가 호출 될 때마다 트리를 걷지 않도록 노드 수를 캐시합니다.
요소에 액세스하기
std::map 은 (key, value) 쌍을 입력으로 사용합니다.
std::map 초기화의 다음 예제를 고려하십시오.
std::map < std::string, int > ranking { std::make_pair("stackoverflow", 2),
std::make_pair("docs-beta", 1) };
std::map 에서 요소는 다음과 같이 삽입 할 수 있습니다.
ranking["stackoverflow"]=2;
ranking["docs-beta"]=1;
위의 예제에서 키 stackoverflow 가 이미 있으면 값은 2로 업데이트됩니다. 아직 없으면 새 항목이 만들어집니다.
std::map 에서 키를 색인으로 지정하여 요소에 직접 액세스 할 수 있습니다.
std::cout << ranking[ "stackoverflow" ] << std::endl;
지도에서 operator[] 를 사용하면 실제로 쿼리 된 키와 함께 새 값 이지도에 삽입 됩니다. 이것은 키가 이미 맵에 저장되어 있더라도 const std::map 에서 사용할 수 없다는 것을 의미합니다. 이 삽입을 방지하려면 요소가 있는지 (예 : find() 사용) 또는 at() 을 아래에 설명 된대로 사용하십시오.
std::map 요소는 at() 로 액세스 할 수 있습니다.
std::cout << ranking.at("stackoverflow") << std::endl;
컨테이너에 요청 된 요소가 포함되어 있지 않으면 at() 가 std::out_of_range 예외를 throw합니다.
컨테이너 std::map 및 std::multimap 에서 반복자를 사용하여 요소에 액세스 할 수 있습니다.
// Example using begin()
std::multimap < int, std::string > mmp { std::make_pair(2, "stackoverflow"),
std::make_pair(1, "docs-beta"),
std::make_pair(2, "stackexchange") };
auto it = mmp.begin();
std::cout << it->first << " : " << it->second << std::endl; // Output: "1 : docs-beta"
it++;
std::cout << it->first << " : " << it->second << std::endl; // Output: "2 : stackoverflow"
it++;
std::cout << it->first << " : " << it->second << std::endl; // Output: "2 : stackexchange"
// Example using rbegin()
std::map < int, std::string > mp { std::make_pair(2, "stackoverflow"),
std::make_pair(1, "docs-beta"),
std::make_pair(2, "stackexchange") };
auto it2 = mp.rbegin();
std::cout << it2->first << " : " << it2->second << std::endl; // Output: "2 : stackoverflow"
it2++;
std::cout << it2->first << " : " << it2->second << std::endl; // Output: "1 : docs-beta"
std :: map 또는 std :: multimap 초기화하기
std::map 및 std::multimap 둘 다 쉼표로 구분 된 키 - 값 쌍을 제공하여 초기화 할 수 있습니다. 키 - 값 쌍은 {key, value} 의해 제공되거나 std::make_pair(key, value) 의해 명시 적으로 생성 될 수 있습니다. std::map 은 중복 키를 허용하지 않고 쉼표 연산자가 오른쪽에서 왼쪽으로 수행하므로 오른쪽 쌍은 왼쪽에서 동일한 키가있는 쌍으로 겹쳐 쓰여집니다.
std::multimap < int, std::string > mmp { std::make_pair(2, "stackoverflow"),
std::make_pair(1, "docs-beta"),
std::make_pair(2, "stackexchange") };
// 1 docs-beta
// 2 stackoverflow
// 2 stackexchange
std::map < int, std::string > mp { std::make_pair(2, "stackoverflow"),
std::make_pair(1, "docs-beta"),
std::make_pair(2, "stackexchange") };
// 1 docs-beta
// 2 stackoverflow
둘 다 반복자로 초기화 될 수 있습니다.
// From std::map or std::multimap iterator
std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {6, 8}, {3, 4},
{6, 7} };
// {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 8}, {6, 7}, {8, 9}
auto it = mmp.begin();
std::advance(it,3); //moved cursor on first {6, 5}
std::map< int, int > mp(it, mmp.end()); // {6, 5}, {8, 9}
//From std::pair array
std::pair< int, int > arr[10];
arr[0] = {1, 3};
arr[1] = {1, 5};
arr[2] = {2, 5};
arr[3] = {0, 1};
std::map< int, int > mp(arr,arr+4); //{0 , 1}, {1, 3}, {2, 5}
//From std::vector of std::pair
std::vector< std::pair<int, int> > v{ {1, 5}, {5, 1}, {3, 6}, {3, 2} };
std::multimap< int, int > mp(v.begin(), v.end());
// {1, 5}, {3, 6}, {3, 2}, {5, 1}
요소 삭제하기
모든 요소 제거 :
std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
mmp.clear(); //empty multimap
iterator의 도움으로 어딘가에서 요소를 제거하기 :
std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
// {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
auto it = mmp.begin();
std::advance(it,3); // moved cursor on first {6, 5}
mmp.erase(it); // {1, 2}, {3, 4}, {3, 4}, {6, 7}, {8, 9}
범위의 모든 요소 제거 :
std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
// {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
auto it = mmp.begin();
auto it2 = it;
it++; //moved first cursor on first {3, 4}
std::advance(it2,3); //moved second cursor on first {6, 5}
mmp.erase(it,it2); // {1, 2}, {6, 5}, {6, 7}, {8, 9}
제공된 값을 갖는 모든 요소를 키로 제거 :
std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
// {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
mmp.erase(6); // {1, 2}, {3, 4}, {3, 4}, {8, 9}
술어 pred 를 만족하는 요소 제거 :
std::map<int,int> m;
auto it = m.begin();
while (it != m.end())
{
if (pred(*it))
it = m.erase(it);
else
++it;
}
요소 삽입하기
요소가 std::map 아직없는 경우에만 요소를 std::map 삽입 할 수 있습니다. 주어진 예를 들면 :
std::map< std::string, size_t > fruits_count;
키 - 값 쌍은
insert()멤버 함수를 통해std::map에insert()됩니다. 인수로pair필요합니다.fruits_count.insert({"grapes", 20}); fruits_count.insert(make_pair("orange", 30)); fruits_count.insert(pair<std::string, size_t>("banana", 40)); fruits_count.insert(map<std::string, size_t>::value_type("cherry", 50));insert()함수는 반복자와bool값으로 구성된pair반환합니다.- 삽입이 성공적이면 반복기는 새로 삽입 된 요소를 가리키고
bool값은true입니다. - 동일한
key가진 요소가 이미 있으면 삽입이 실패합니다. 이 경우 iterator는 충돌을 일으키는 요소를 가리키며bool은 value가false입니다.
삽입 및 검색 작업을 결합하는 데 다음 방법을 사용할 수 있습니다.
auto success = fruits_count.insert({"grapes", 20}); if (!success.second) { // we already have 'grapes' in the map success.first->second += 20; // access the iterator to update the value }- 삽입이 성공적이면 반복기는 새로 삽입 된 요소를 가리키고
편의상
std::map컨테이너는std::map요소에 액세스하고 존재하지 않는 경우 새로운 요소를 삽입 할 수 있도록 첨자 연산자를 제공합니다.fruits_count["apple"] = 10;더 간단하지만 요소가 이미 있는지 사용자가 확인하지 못하도록합니다. 요소가 누락 된 경우
std::map::operator[]암시 적으로 생성하고 기본 생성자로 초기화 한 다음 제공된 값으로 덮어 씁니다.
insert()를 사용하여 괄호로 묶은 목록을 사용하여 여러 요소를 한 번에 추가 할 수 있습니다. 이 버전의 insert ()는 void를 반환합니다.fruits_count.insert({{"apricot", 1}, {"jackfruit", 1}, {"lime", 1}, {"mango", 7}});insert()는value_type값의 시작과 끝을 나타내는 반복자를 사용하여 요소를 추가하는 데에도 사용할 수 있습니다.std::map< std::string, size_t > fruit_list{ {"lemon", 0}, {"olive", 0}, {"plum", 0}}; fruits_count.insert(fruit_list.begin(), fruit_list.end());
예:
std::map<std::string, size_t> fruits_count;
std::string fruit;
while(std::cin >> fruit){
// insert an element with 'fruit' as key and '1' as value
// (if the key is already stored in fruits_count, insert does nothing)
auto ret = fruits_count.insert({fruit, 1});
if(!ret.second){ // 'fruit' is already in the map
++ret.first->second; // increment the counter
}
}
삽입 연산의 시간 복잡도는 O (log n)입니다. 왜냐하면 std::map 은 나무로 구현되기 때문입니다.
pair 은 make_pair() 및 emplace() 사용하여 명시 적으로 구성 할 수 있습니다.
std::map< std::string , int > runs;
runs.emplace("Babe Ruth", 714);
runs.insert(make_pair("Barry Bonds", 762));
새로운 요소가 삽입 될 곳을 알면 emplace_hint() 를 사용하여 반복기 hint 를 지정할 수 있습니다. 새로운 요소가 hint 직전에 삽입 될 수 있으면 삽입은 일정한 시간에 완료 될 수 있습니다. 그렇지 않으면 emplace() 와 같은 방식으로 동작합니다.
std::map< std::string , int > runs;
auto it = runs.emplace("Barry Bonds", 762); // get iterator to the inserted element
// the next element will be before "Barry Bonds", so it is inserted before 'it'
runs.emplace_hint(it, "Babe Ruth", 714);
반복 std :: map 또는 std :: multimap
std::map 또는 std::multimap 은 다음과 같은 방법으로 통과 할 수 있습니다.
std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
//Range based loop - since C++11
for(const auto &x: mmp)
std::cout<< x.first <<":"<< x.second << std::endl;
//Forward iterator for loop: it would loop through first element to last element
//it will be a std::map< int, int >::iterator
for (auto it = mmp.begin(); it != mmp.end(); ++it)
std::cout<< it->first <<":"<< it->second << std::endl; //Do something with iterator
//Backward iterator for loop: it would loop through last element to first element
//it will be a std::map< int, int >::reverse_iterator
for (auto it = mmp.rbegin(); it != mmp.rend(); ++it)
std::cout<< it->first <<" "<< it->second << std::endl; //Do something with iterator
std::map 또는 std::multimap 반복하면서 auto 사용은 쓸모없는 암시 적 변환을 피하는 것이 좋습니다 (자세한 내용은 SO 답변 참조).
std :: map 또는 std :: multimap에서 검색
std::map 또는 std::multimap 에서 키를 검색하는 데는 여러 가지 방법이 있습니다.
키의 첫 번째 발생에 대한 반복자를 얻으려면
find()함수를 사용할 수 있습니다. 키가 존재하지 않으면end()반환합니다.std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} }; auto it = mmp.find(6); if(it!=mmp.end()) std::cout << it->first << ", " << it->second << std::endl; //prints: 6, 5 else std::cout << "Value does not exist!" << std::endl; it = mmp.find(66); if(it!=mmp.end()) std::cout << it->first << ", " << it->second << std::endl; else std::cout << "Value does not exist!" << std::endl; // This line would be executed.항목이
std::map또는std::multimap에 있는지 여부를 확인하는 또 다른 방법은count()함수를 사용하는count()함수는 주어진 키와 연관된 값의 수를 계산합니다.std::map은 각 키에 하나의 값만 연결하기 때문에count()함수는 0 (키가없는 경우) 또는 1 (있는 경우)을 반환 할 수 있습니다.std::multimap에서count()는 동일한 키와 연관된 여러 값이있을 수 있으므로 1보다 큰 값을 반환 할 수 있습니다.std::map< int , int > mp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} }; if(mp.count(3) > 0) // 3 exists as a key in map std::cout << "The key exists!" << std::endl; // This line would be executed. else std::cout << "The key does not exist!" << std::endl;어떤 요소가 있는지 여부 만 신경 쓰면,
find는 엄격하게 더 나은 것입니다 : 그것은 당신의 의도를 문서화하고,multimaps경우 첫 번째로 일치하는 요소가 발견되면 멈출 수 있습니다.std::multimap의 경우 동일한 키를 가진 여러 요소가있을 수 있습니다. 이 범위를 얻기 위해equal_range()함수가 사용되어 iterator lower bound (포함)와 upper bound (exclusive)를 각각 갖는std::pair를 반환합니다. 키가 존재하지 않으면 두 반복자 모두end()가리 킵니다.auto eqr = mmp.equal_range(6); auto st = eqr.first, en = eqr.second; for(auto it = st; it != en; ++it){ std::cout << it->first << ", " << it->second << std::endl; } // prints: 6, 5 // 6, 7
요소 수 확인
컨테이너 std::map 에는 맵이 비 었는지 여부에 따라 true 또는 false 를 반환하는 멤버 함수 empty() 가 있습니다. 멤버 함수 size() 는 std::map 컨테이너에 저장된 요소의 수를 반환합니다.
std::map<std::string , int> rank {{"facebook.com", 1} ,{"google.com", 2}, {"youtube.com", 3}};
if(!rank.empty()){
std::cout << "Number of elements in the rank map: " << rank.size() << std::endl;
}
else{
std::cout << "The rank map is empty" << std::endl;
}
지도 유형
일반지도
지도는 키 - 값 쌍을 포함하는 연관 컨테이너입니다.
#include <string>
#include <map>
std::map<std::string, size_t> fruits_count;
위의 예에서 std::string 은 키 유형이고 size_t 는 값 입니다.
키는지도의 색인 역할을합니다. 각 키는 고유해야하며 주문해야합니다.
동일한 키를 사용하여 여러 요소가 필요할 경우
multimap(multimap) 사용을 고려하십시오 (아래 설명 참조)값 유형에 주문이 지정되어 있지 않거나 기본 주문을 무시하려는 경우 다음 중 하나를 제공 할 수 있습니다.
#include <string> #include <map> #include <cstring> struct StrLess { bool operator()(const std::string& a, const std::string& b) { return strncmp(a.c_str(), b.c_str(), 8)<0; //compare only up to 8 first characters } } std::map<std::string, size_t, StrLess> fruits_count2;StrLesscomparator가 두 개의 키에 대해false를 반환하면 실제 내용이 다른 경우에도 동일한 것으로 간주됩니다.
멀티 맵
Multimap을 사용하면 동일한 키를 가진 여러 키 - 값 쌍을 맵에 저장할 수 있습니다. 그렇지 않으면 인터페이스와 생성이 일반 맵과 매우 유사합니다.
#include <string>
#include <map>
std::multimap<std::string, size_t> fruits_count;
std::multimap<std::string, size_t, StrLess> fruits_count2;
해시지도 (정렬되지 않은지도)
해시 맵은 일반 맵과 유사한 키 - 값 쌍을 저장합니다. 키에 대한 요소를 정렬하지는 않습니다. 대신 키의 해시 값을 사용하여 필요한 키 - 값 쌍에 빠르게 액세스합니다.
#include <string>
#include <unordered_map>
std::unordered_map<std::string, size_t> fruits_count;
정렬되지 않은 맵은 일반적으로 빠르지 만 요소는 예측 가능한 순서로 저장되지 않습니다. 예를 들어, unordered_map 모든 요소를 반복하면 임의의 순서로 요소가 나타납니다.
사용자 정의 유형을 키로 사용하여 std :: map 만들기
맵에서 클래스를 키로 사용할 수 있으려면 키를 필요로하는 것은 그것이 copiable 하고 assignable copiable 해야한다는 것입니다. 지도 내의 순서는 템플릿의 세 번째 인수 (및 사용되는 경우 생성자에 대한 인수)로 정의됩니다. 기본값 은 std::less<KeyType> 이며 기본값은 < 연산자이지만 기본값을 사용할 필요는 없습니다. 비교 연산자를 쓰면됩니다 (함수 객체로 선호 됨).
struct CmpMyType
{
bool operator()( MyType const& lhs, MyType const& rhs ) const
{
// ...
}
};
C ++에서 "compare"술어는 엄격한 약한 순서 여야합니다. 특히 compare(X,X) 는 모든 X 대해 false 를 반환해야합니다. 즉, CmpMyType()(a, b) 가 true를 반환하면 CmpMyType()(b, a) 는 false를 반환해야하며 둘 다 false를 반환하면 요소는 동일한 것으로 간주됩니다 (동일한 등가 클래스의 멤버).
엄격한 약한 주문
이것은 두 객체 간의 관계를 정의하는 수학 용어입니다.
정의는 다음과 같습니다.
f (x, y)와 f (y, x)가 모두 거짓이면 두 객체 x와 y가 동일합니다. 객체는 항상 그 자체와 동등한 (irreflexivity 불변 식에 의한) 것에 주목하자.
C ++의 경우, 주어진 타입의 객체가 두 개있는 경우 연산자 <와 비교할 때 다음 값을 반환해야합니다.
X a;
X b;
Condition: Test: Result
a is equivalent to b: a < b false
a is equivalent to b b < a false
a is less than b a < b true
a is less than b b < a false
b is less than a a < b false
b is less than a b < a true
동등한 / 덜 정의하는 방법은 전적으로 개체 유형에 따라 다릅니다.