자료구조 C++ STL map에 대한 정리

알고리즘을 풀기 위해 Chapter 21에 있는 Associative container에 대한 정리

P869

Data structures similar to map and unordered_map are known under many names, such as associative arrays, hash tables, and red-black trees.
Popular and useful concepts always seem to have many names. In the standard library, we collectively call all such data structures associative containers.

The standard library provides eight associative containers:

map - an ordered container of (key, value) pairs
set - an ordered container of keys
unordered_map - an unordered container of (key,value) pairs
unordered_set - an unordered container of keys
multimap - a map where a key can occur multiple times
multiset - a set where a key can occur multiple times
unordered_multimap - an unordered_map where a key can occur multiple times
unordered-multiset - an unordered_set where a key can occur multiple times

These containers are found in <map>, <set>, <unordered_map>, and <unordered_set>.

int main()
{

map<string,int> words;  // keep (word,frequency) pairs
for(string s; cin >> s;)
++words[s];     // note: word is subscripted by a string

for(const auto& p : words )
cout << p.first << ": " << p.second << '\n';
}

If we have not seen the string "sultan" before, "sultan" will be entered into words with the default value for an int, which is 0. Now, words has an entry

("sultan", 0). It follows that if we haven't seen "sultan" before, ++words["sultan"] will associate the value 1 with the string "sultan". In detail: the map will discover that "sultan" wasn't found, insert a ("sultan", 0) pair, and then ++ will increment that value, yielding 1.

 Now look again at the program: ++words[s] takes every "word" we get from input and increases its value by one.
-- Now all we have to do is to produce the output. We can iterate through a map, just like any other STL container. The elements of a map<string,int> 
are of type pair<string,int>. The first member of a pair is called first and the second member second, so the output loop becomes


for(const auto& p : words)
cout << p.first << ": " << p.second << '\n';


*Page 872
So what is a map? There is a variety of ways of implementing maps, but the STL map implementations tend to be balanced binary search tress; more specifically,
they are red-black trees. We will not go into the details, but now you know the technical terms, so you can look them up in the literature or on the web, should you want to know more.

 A tree is built up from nodes (in a way similar to a list being built from links;  see 20.4 ). A node holds a key, its corresponding value, and pointers to two descendant Nodes.


Map node : Key first
              Value second
              Node* left
              Node* right
... 


트리에 관한 설명이여서 여기까지.

c++ reference

map::erase에 대한 예제

// erasing from map
#include <iostream>
#include <map>

int main ()
{
  std::map<char,int> mymap;
  std::map<char,int>::iterator it;

  // insert some values:
  mymap['a']=10;
  mymap['b']=20;
  mymap['c']=30;
  mymap['d']=40;
  mymap['e']=50;
  mymap['f']=60;

  it=mymap.find('b');
  mymap.erase (it);                   // erasing by iterator

  mymap.erase ('c');                  // erasing by key

  it=mymap.find ('e');
  mymap.erase ( it, mymap.end() );    // erasing by range

  // show content:
  for (it=mymap.begin(); it!=mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';

  return 0;
}

output

a => 10
d => 40