9.1 map µ¥ÀÌÅÍ Ãß»ó(data abstraction) [Image] Map ´ë½Å »ç¿ëµÇ´Â ´Ù¸¥ ¸íĪµé vector³ª deque¿Í ¸¶Âù°¡Áö·Î mapµµ À妽ÌÀÌ °¡´ÉÇÏ´Ù. ±×·¯³ª, mapÀº µÎ°¡ÁöÁ¡¿¡¼­ À̵é°ú Â÷ÀÌ°¡ ³­´Ù. ù°·Î, map¿¡¼­´Â À妽º °ª(Å°°ª)ÀÌ ¹Ýµå½Ã Á¤¼öÀÏ ÇÊ¿ä´Â ¾ø°í, ordered µ¥ÀÌÅÍ Å¸ÀÔÀÌ¸é °¡´ÉÇÏ´Ù. ¿¹¸¦ µé¾î, ½Ç¼ö³ª stringÀ¸·Î À妽ÌÀÌ °¡´ÉÇÏ´Ù. ºñ±³¿¬»êÀÚ¸¦ °¡Áö°í ÀÖ´Â µ¥ÀÌÅÍ Å¸ÀÔÀ̸é Å°·Î¼­ »ç¿ëÀÌ °¡´ÉÇÏ´Ù. vector³ª deque¿¡¼­Ã³·³, ÷ÀÚ ¿¬»êÀÚ·Î ¿ø¼ÒµéÀ» Á¢±ÙÇÒ ¼ö ÀÖ°í, ¹°·Ð ´Ù¸¥ ¹æ¹ýµµ ÀÖ´Ù. µÎ¹ø° Â÷ÀÌÁ¡Àº mapÀº ordered µ¥ÀÌÅÍ ±¸Á¶¶õ Á¡ÀÌ´Ù. ÀÌ´Â ¿ø¼ÒµéÀÌ Å°°ª¿¡ µû¶ó ¼ø¼­°¡ Á¤ÇØÁ®¼­ °ü¸®µÈ´Ù´Â ¸»ÀÌ´Ù. °ªµéÀ» ¼ø¼­¸¦ ¸Å°Ü °ü¸®Çϱ⠶§¹®¿¡, ÁÖ¾îÁø Å°¿¡ ÇØ´çÇÏ´Â ¿ø¼Ò¸¦ ¾ÆÁÖ »¡¸® ã¾Æ³¾ ¼ö ÀÖ´Ù(°Ë»ö ½Ã°£Àº log ½Ã°£). list¿Í ¸¶Âù°¡Áö·Î, mapµµ »çÀÌÁî¿¡ Á¦ÇÑÀÌ ¾øÁö¸¸, »õ ¿ø¼ÒµéÀÌ Ãß°¡µÇ°Å³ª »èÁ¦µÉ ¶§, È®ÀåÇϰųª Ãà¼ÒÇÑ´Ù. ´ëºÎºÐÀÇ °æ¿ì, mapÀº pair¸¦ °ü¸®ÇÏ´Â setÀ¸·Î ºÁµµ ¹«¹æÇÏ´Ù. Ç¥ÁØ ¶óÀ̺귯¸®°¡ Á¦°øÇÏ´Â map¿¡´Â µÎ°¡Áö Á¾·ù°¡ ÀÖ´Ù. mapÀº Å°°¡ ¹Ýµå½Ã À¯ÀÏÇØ¾ß ÇÑ´Ù. Áï, Å°¿Í ±×¿¡ ´ëÀÀµÇ´Â °ªÀÌ ¼­·Î ÀÏ´ëÀÏ´ëÀÀÀÌ µÇ¾î¾ß ÇÑ´Ù´Â °ÍÀÌ´Ù. map¿¡¼­´Â ÀÌ¹Ì Á¸ÀçÇÏ´Â Å°°ªÀ» °¡Áö´Â ¿ø¼Ò¸¦ »ðÀÔÇÒ ¶§ ÀÌ´Â ¹«½ÃµÈ´Ù. ÇÑÆíÀ¸·Î multimapÀº °°Àº Å°·Î Àε¦½ÌµÇ´Â ¿©·¯°³ÀÇ ¼­·Î ´Ù¸¥ ¿ø¼ÒµéÀ» Çã¿ëÇÑ´Ù. ÀÌ µÎ°¡Áö´Â ¸ðµÎ »ðÀÔ, »èÁ¦, Á¢±Ù ¿¬»êÀÌ »ó´ëÀûÀ¸·Î ºü¸£´Ù.(log ½Ã°£) [Image] Pairs 9.1.1 Include È­ÀÏ mapÀ̳ª multimapÀ» »ç¿ëÇÒ ¶§´Â map Çì´õÈ­ÀÏÀ» Æ÷ÇÔÇØ¾ß ÇÑ´Ù. #include 9.2 map°ú multimap ¿¬»ê map°ú multimap µ¥ÀÌÅÍ Å¸ÀÔÀÌ Á¦°øÇÏ´Â ¸â¹ö ÇÔ¼ö¿¡ °üÇØ ÀÚ¼¼È÷ »ìÆ캻´Ù. ¸â¹ö ÇÔ¼öµéÀÌ ±âÃÊÀûÀÎ ¿¬»êµéÀ» Á¦°øÇÏ´Â ¹Ý¸é¿¡, 13Àý°ú 14Àý¿¡ ¼³¸íÇÏ°í ÀÖ´Â generic ¾Ë°í¸®µëÀ» »ç¿ëÇÔÀ¸·Î½á µ¥ÀÌÅÍ ±¸Á¶¸¦ º¸´Ù À¯¿ëÇÏ°Ô »ç¿ëÇÒ ¼ö ÀÖ°Ô µÈ´Ù. 9.2.1 mapÀÇ ¼±¾ð°ú ÃʱâÈ­ mapÀÇ ¼±¾ðÀº Ç¥ÁØ ¶óÀ̺귯¸®¿¡¼­ ÀÚÁÖ º¸¾Æ¿Ô´ø ¹æ½ÄÀ» µû¸¥´Ù. mapÀº ÅÛÇø´ µ¥ÀÌÅÍ ±¸Á¶À̸ç, ÅÛÇø´ÀÇ ÀÎÀÚ·Î Å°ÀÇ Å¸ÀÔ, Å°¿¡ ´ëÀÀµÇ´Â °ªÀÇ Å¸ÀÔ, Å°¸¦ ºñ±³Çϴµ¥ »ç¿ëµÉ ºñ±³ ¿¬»êÀÚ¸¦ ÁöÁ¤ÇØ¾ß ÇÑ´Ù. ¸¸¾à¿¡ ÄÄÆÄÀÏ·¯°¡ µðÆúÆ® ÅÛÇø´ ÀÎÀÚ(¾ÆÁ÷Àº ¸¹Àº ȸ»ç¿¡¼­ Áö¿øÇÏÁö ¾Ê´Â C++ÀÇ »õƯ¡)¸¦ Áö¿øÇϸé, ¹æ±Ý ¾ð±ÞÇÑ ÅÛÇø´ ÀÎÀÚ Áß ¼¼¹ø° °ÍÀº »ý·«ÀÌ °¡´ÉÇÏ°í, »ý·«µÇ´Â °æ¿ì¿¡´Â Å°ÀÇ Å¸ÀÔ¿¡ Á¤ÀǵǾî ÀÖ´Â less-than ¿¬»êÀÚ·Î ÁöÁ¤µÈ´Ù. mapÀº ÃʱⰪ¾øÀÌ ¼±¾ðµÉ ¼ö ÀÖ°í, ÇѽÖÀÇ ¹Ýº¹ÀÚ¸¦ »ç¿ëÇÏ¿© ´Ù¸¥ ÄÁÅ×À̳ʿ¡ ´ã±ä °ªµé·Î ÃʱâÈ­ µÉ ¼öµµ ÀÖ´Ù. ÈÄÀÚÀÇ °æ¿ì¿¡, ¹Ýº¹ÀÚ´Â pair ŸÀÔÀÇ °ªÀ» °¡¸®Å°°í ÀÖ¾î¾ß Çϸç, À̶§ ù¹ø° Çʵå´Â Å°(key)·Î °£Áֵǰí, µÎ¹ø° Çʵå´Â °ª(value)À¸·Î °£ÁֵǴ °ÍÀÌ´Ù. º¹»ç »ý¼ºÀÚ¸¦ »ç¿ëÇÏ¿© ´Ù¸¥ mapÀÇ º¹»çº»À» ¸¸µé¾î ³½´Ù. // map indexed by doubles containing strings map > map_one; // map indexed by integers, containing integers map map_two(aContainer.begin(), aContainer.end()); // create a new map, initializing it from map two map map_three(map_two); // copy constructor mapÀ» ´Ù¸¥ map¿¡ ´ëÀÔÇÒ ¼ö ÀÖÀ¸¸ç, swap() ¿¬»êÀ» »ç¿ëÇÏ¿© µÎ map°£¿¡ °ªÀ» ¼­·Î ±³È¯ÇÒ ¼ö ÀÖ´Ù. 9.2.2 ŸÀÔ Á¤ÀÇ map°ú multimapÀº ¸¹Àº ŸÀÔ Á¤ÀǵéÀ» Æ÷ÇÔÇÏ°í ÀÖÀ¸¸ç, À̵éÀº ÁÖ·Î ¼±¾ð¹®¿¡¼­ ¸¹ÀÌ »ç¿ëµÈ´Ù. ¿¹¸¦ µé¾î, stringÀ» Á¤¼ö·Î ¸ÅÇÎÇÏ´Â map¿¡ »ç¿ëµÇ´Â ¹Ýº¹ÀÚ´Â ´ÙÀ½°ú °°ÀÌ ¼±¾ðµÈ´Ù. map::iterator location; 'iterator' »Ó¸¸ ¾Æ´Ï¶ó, ´ÙÀ½°ú °°Àº ŸÀÔµéÀÌ Á¤ÀǵǾî ÀÖ´Ù. key_type The type associated with the keys used to index the map. value_type The type held by the container, a key/value pair. const_iterator An iterator that does not allow modification of the underlying sequence. reverse_iterator An iterator that moves in a backward direction. const_reverse_iterator A combination constant and reverse iterator. reference A reference to an underlying value. const_reference A reference to an underlying value that will not permit the element to be modified. size_type An unsigned integer type, used to refer to the size of containers. key_compare A function object that can be used to compare two keys. value_compare A function object that can be used to compare two elements. difference_type A signed integer type, used to describe the distances between iterators. allocator_type An allocator used by the container for all storage management. 9.2.3 »ðÀÔ°ú Á¢±Ù insert() ¿¬»êÀ» »ç¿ëÇÏ¿© mapÀ̳ª multimap¿¡ °ªµéÀ» »ðÀÔÇÑ´Ù. À̶§ ÀÎÀÚ´Â ¹Ýµå½Ã Å°¿Í °ªÀÇ pairÀ̾î¾ß ÇÑ´Ù. À̶§ »ç¿ëµÇ´Â pair´Â map¿¡ Á¤ÀǵǾî ÀÖ´Â value_type À̶ó´Â µ¥ÀÌÅÍ Å¸ÀÔÀ» »ç¿ëÇÏ¿© ¸¸µç´Ù. map_three.insert (map::value_type(5, 7)); ÇѽÖÀÇ ¹Ýº¹ÀÚ¸¦ »ç¿ëÇÏ¿© »ðÀÔÀ» ¼öÇàÇÒ ¼öµµ Àִµ¥, ´ÙÀ½°ú °°ÀÌ ´Ù¸¥ ÄÁÅ×À̳ʷκÎÅÍ °ªÀ» °¡Á®¿Ã ¼ö ÀÖ´Ù. map_two.insert (map_three.begin(), map_three.end()); map(multimapÀº Á¦¿Ü)¿¡¼­´Â ÷ÀÚ ¿¬»êÀ» ÅëÇØ °ªÀ» Á¢±ÙÇϰųª »ðÀÔÇÒ ¼ö ÀÖ´Ù. ´Ü¼øÈ÷ Å°¸¦ ÷ÀÚ·Î »ç¿ëÇϸé ÇØ´ç °ªÀ» Á¢±ÙÇÒ ¼ö ÀÖ°í, ÷ÀÚ ¿¬»êÀÇ °á°ú¿¡ ´ëÀÔÀ» ÇÔÀ¸·Î½á Å°¿¡ ´ëÀÀµÇ´Â °ªÀ» º¯È­½Ãų ¼ö ÀÖ´Ù. cout << "Index value 7 is " << map_three[7] << endl; // now change the associated value map_three[7] = 5; cout << "Index value 7 is " << map_three[7] << endl; 9.2.4 »èÁ¦ Å°°ªÀ» °¡Áö°í map°ú multimapÀ¸·ÎºÎÅÍ °ªµéÀ» »èÁ¦ÇÒ ¼ö ÀÖ´Ù. multimap¿¡¼­´Â Å°¿Í ¿¬°üµÈ ¸ðµç ¿ø¼Ò¸¦ »èÁ¦ÇÑ´Ù. »èÁ¦µÉ ¿ø¼Ò¸¦ ¹Ýº¹ÀÚ·Î ÁöÁ¤ÇÒ ¼öµµ ÀÖ´Ù. ¿¹¸¦ µé¸é, find() ¿¬»êÀÇ °á°ú·Î ¾òÀº ¹Ýº¹ÀÚ¸¦ »ç¿ëÇÒ ¼öµµ ÀÖ´Ù. ÇѽÖÀÇ ¹Ýº¹ÀÚ¸¦ »ç¿ëÇÏ¿© ÁöÁ¤ÇÑ range³»ÀÇ ¿ø¼ÒµéÀ» ¸ðµÎ Áö¿ì´Â °Íµµ °¡´ÉÇÏ´Ù. // erase the 4th element 4 map_three.erase(4); // erase the 5th element mtesttype::iterator five = map_three.find(5); map_three.erase(five); // erase all values between the 7th and 11th elements mtesttype::iterator seven = map_three.find(7); mtesttype::iterator eleven = map_three.find(11); map_three.erase(seven, eleven); ¿ø¼ÒŸÀÔÀÌ ¼Ò¸êÀÚ¸¦ Á¤ÀÇÇÏ°í ÀÖ´Ù¸é, ÄÝ·º¼ÇÀ¸·ÎºÎÅÍ Å°¿Í °ªÀ» Á¦°ÅÇϱâ Àü¿¡ ÀÌ ¼Ò¸êÀÚ°¡ È£ÃâµÉ °ÍÀÌ´Ù. 9.2.5 ¹Ýº¹ÀÚ [Image] No Iterator Invalidation begin()°ú end() ¸â¹ö ÇÔ¼ö´Â map°ú multimap ¸ðµÎ¸¦ À§ÇÑ ¾ç¹æÇ⠹ݺ¹ÀÚ¸¦ »ý¼ºÇÑ´Ù. mapÀ̳ª multimap¿¡ »ç¿ëµÇ´Â ¹Ýº¹ÀÚ¸¦ ÂüÁ¶Çϸé Å°/°ªÀÇ pair¸¦ ¾ò°Ô µÈ´Ù. Çʵå¸íÀ¸·Î first¿Í second¸¦ »ç¿ëÇÔÀ¸·Î½á °¢ Çʵ带 Á¢±ÙÇÒ ¼ö ÀÖ´Ù. ù¹ø° Çʵå´Â »ó¼ö¶ó¼­ º¯°æÇÒ ¼ö ¾øÁö¸¸, µÎ¹ø° Çʵå´Â ÁÖ¾îÁø Å°¿Í ¿¬°áµÈ °ªÀ» º¯È­½ÃÅ°´Âµ¥ »ç¿ëµÈ´Ù. ¿ø¼ÒµéÀº Å° ÇʵåÀÇ ¼ø¼­¿¡ µû¶ó Á¢±ÙµÈ´Ù(?). rbegin()°ú rend() ¸â¹ö ÇÔ¼ö´Â ¿ª¹æÇâÀ¸·Î ¿ø¼ÒµéÀ» »ý¼ºÇÏ´Â ¹Ýº¹ÀÚµéÀ» ¹ÝȯÇÑ´Ù. 9.2.6 °Ë»ö°ú Ä«¿îÆà size() ¸â¹ö ÇÔ¼ö´Â ÄÁÅ×À̳ʰ¡ °¡Áö°í ÀÖ´Â ¿ø¼ÒÀÇ °¹¼ö¸¦ ¸®ÅÏÇÑ´Ù. empty() ¸â¹ö ÇÔ¼ö´Â ÄÁÅ×À̳ʰ¡ ºñ¾úÀ» ¶§, true¸¦ ¸®ÅÏÇÏ°í, size()¸¦ zero¿Í ºñ±³ÇÏ´Â °Íº¸´Ù ´ëü·Î ºü¸£´Ù. find() ¸â¹öÇÔ¼ö´Â Å°¸¦ ÀÎÀÚ·Î ÃëÇؼ­, Å°/°ª pair¸¦ °¡¸®Å°´Â ¹Ýº¹ÀÚ¸¦ ¸®ÅÏÇÑ´Ù. multimapÀÇ °æ¿ì¿¡´Â, °¡Àå ¸ÕÀú ÀÏÄ¡ÇÏ´Â °ªÀ» ¸®ÅÏÇÑ´Ù. µÎ°æ¿ì ¸ðµÎ, ¿øÇÏ´Â °ªÀ» ãÁö ¸øÇÒ ¶§´Â, past-the-end ¹Ýº¹ÀÚ¸¦ ¸®ÅÏÇÑ´Ù. if (map_one.find(4) != map_one.end()) cout << "contains a 4th element" << endl; lower_bound() ¸â¹ö ÇÔ¼ö´Â ÀÎÀÚ·Î ÁÖ¾îÁø Å°¿Í ÀÏÄ¡Çϴ ù¹ø° ¿ø¼Ò¸¦ ¸®ÅÏÇÏ°í, upper_bound() ¸â¹ö ÇÔ¼ö´Â ÀÎÀÚ·Î ÁÖ¾îÁø Å°¿Í ÀÏÄ¡ÇÏ´Â ¸¶Áö¸· ¿ø¼Ò ¹Ù·Î Á÷ÈÄÀÇ ¿ø¼Ò¸¦ ¸®ÅÏÇÑ´Ù. ¸¶Áö¸·À¸·Î, equal_range() ÇÔ¼ö´Â lower bound¿Í upper bound¸¦ ´ã°í ÀÖ´Â ¹Ýº¹ÀÚÀÇ pair¸¦ ¸®ÅÏÇÑ´Ù. ÀÌµé ¿¬»êÀ» »ç¿ëÇÏ´Â ¿¹´Â ÀÌ ÀýÀÇ ¸¶Áö¸·¿¡ ÁÖ¾îÁø´Ù. count() ¸â¹ö ÇÔ¼ö´Â ÀÎÀÚ·Î ÁÖ¾îÁø Å°°ª°ú ÀÏÄ¡ÇÏ´Â ¿ø¼ÒÀÇ °¹¼ö¸¦ ¸®ÅÏÇÑ´Ù. mapÀÇ °æ¿ì¿¡´Â °á°ú°ªÀÌ Ç×»ó 0 ¶Ç´Â 1ÀÎ ¹Ý¸é¿¡, multimapÀÇ °æ¿ì¿¡´Â À½¼ö°¡ ¾Æ´Ñ °ªÀÌ¸é °á°ú°ªÀÌ µÉ ¼ö ÀÖ´Ù. ´Ü¼øÈ÷ ÄÝ·º¼ÇÀÌ ÁÖ¾îÁø Å°·Î Àε¦½ÌµÇ´Â ¿ø¼Ò¸¦ Æ÷ÇÔÇÏ´ÂÁöÀÇ ¿©ºÎ¸¸À» È®ÀÎÇÏ°í ½ÍÀ» ¶§´Â find()ÀÇ °á°ú°ªÀ» end-of-sequence ¹Ýº¹ÀÚ¿Í ºñ±³ÇÏ´Â °Íº¸´Ù´Â count()¸¦ »ç¿ëÇÏ´Â °ÍÀÌ ½¬¿ï ¶§°¡ ´õ ¸¹´Ù. if (map_one.count(4)) cout << "contains a 4th element" << endl; 9.2.7 ¿ø¼Ò ºñ±³ ÀÎÀÚ°¡ ÇÊ¿ä¾ø´Â key_comp()¿Í value_comp() ¸â¹öÇÔ¼ö´Â °¢°¢ key ŸÀÔ ¶Ç´Â value ŸÀÔÀÇ ¿ø¼Ò¸¦ ºñ±³ÇÒ ¶§ »ç¿ëµÇ´Â ÇÔ¼ö °´Ã¼¸¦ ¹ÝȯÇÑ´Ù. ºñ±³ÇÒ¶§ »ç¿ëµÇ´Â °ªµéÀÌ ÄÝ·º¼ÇÀÌ Æ÷ÇԵǾî ÀÖÀ» ÇÊ¿ä´Â ¾øÀ¸¸ç, ÀÌ ÇÔ¼öµéÀº ÄÁÅ×À̳ʿ¡ ¾Æ¹«·± ¿µÇâÀ» ¹ÌÄ¡Áö ¾Ê´Â´Ù. if (map_two.key_comp (i, j)) // map_two.key_comp()(i, j) ? cout << "element i is less than j" << endl; 9.2.8 ±âŸ map ¿¬»ê map°ú multimapÀº ordered ÄÝ·º¼ÇÀÌ°í, map¿¡ ´ëÇÑ ¹Ýº¹ÀÚ´Â pair¸¦ ¹ÝȯÇϱ⠶§¹®¿¡, 13Àý°ú 14Àý¿¡¼­ ¼³¸íÇÏ´Â ÇÔ¼öµéÀÌ »ç¿ëÇϱ⿡ ¹«ÀÇÇϰųª °ï¶õÇÑ °ÍµéÀÌ ¸¹´Ù. ±×·¯³ª, for_each(), adjacent_find(), accumulate()µé °¢°¢Àº ³ª¸§´ë·Î ¾µ¸ð°¡ ÀÖ´Ù. ÇÏÁö¸¸, ÀÎÀÚ·Î Á¦°øµÇ´Â ÇÔ¼öµéÀº Å°/°ª pair¸¦ ÀÎÀÚ·Î ÃëÇÏ´Â °ÍÀ̶ó¾ß ÇÑ´Ù´Â °ÍÀ» ¹Ýµå½Ã ±â¾ïÇØ¾ß ÇÑ´Ù. 9.3 ¿¹Á¦ ÇÁ·Î±×·¥ We present three example programs that illustrate the use of maps and multimaps. These are a telephone database, graphs, and a concordance. 9.3.1 ÀüÈ­ µ¥ÀÌÅͺ£À̽º A maintenance program for a simple telephone database is a good application for a map. The database is simply an indexed structure, where the name of the person or business (a string) is the key value, and the telephone number (a long) is the associated entry. We might write such a class as follows: typedef map > friendMap; typedef friendMap::value_type entry_type; class telephoneDirectory { public: void addEntry (string name, long number) // add new entry to // database { database[name] = number; } void remove (string name) // remove entry from database { database.erase(name); } void update (string name, long number) // update entry { remove(name); addEntry(name, number); } void displayDatabase() // display entire database { for_each(database.begin(), database.end(), printEntry); } void displayPrefix(int); // display entries that match prefix void displayByPrefix(); // display database sorted by prefix private: friendMap database; }; Simple operations on our database are directly implemented by map commands. Adding an element to the database is simply an insert, removing an element is an erase, and updating is a combination of the two. To print all the entries in the database we can use the for_each() algorithm, and apply the following simple utility routine to each entry: void printEntry(const entry_type & entry) { cout << entry.first << ":" << entry.second << endl; } We will use a pair of slightly more complex operations to illustrate how a few of the algorithms described in Section 13 can be used with maps. Suppose we wanted to display all the phone numbers with a certain three digit initial prefix[1] . We will use the find_if() function (which is different from the find() member function in class map) to locate the first entry. Starting from this location, subsequent calls on find_if() will uncover each successive entry. void telephoneDirectory::displayPrefix(int prefix) { cout << "Listing for prefix " << prefix << endl; friendMap::iterator where; where = find_if (database.begin(), database.end(), checkPrefix(prefix)); while (where != database.end()) { printEntry(*where); where = find_if (++where, database.end(), checkPrefix(prefix)); } cout << "end of prefix listing" << endl; } For the predicate to this operation, we require a boolean function that takes only a single argument (the pair representing a database entry), and tells us whether or not it is in the given prefix. There is no obvious candidate function, and in any case the test prefix is not being passed as an argument to the comparison function. The solution to this problem is to employ a technique that is commonly used with the standard library, defining the predicate function as an instance of a class, and storing the test predicate as an instance variable in the class, initialized when the class is constructed. The desired function is then defined as the function call operator for the class: int prefix(const entry_type & entry) { return entry.second / 10000; } class checkPrefix { public: checkPrefix (int p) : testPrefix(p) { } int testPrefix; bool operator () (const entry_type & entry) { return prefix(entry) == testPrefix; } }; Our final example will be to display the directory sorted by prefix. It is not possible to alter the order of the maps themselves. So instead, we create a new map with the element types reversed, then copy the values into the new map, which will order the values by prefix. Once the new map is created, it is then printed. typedef map > sortedMap; typedef sortedMap::value_type sorted_entry_type; void telephoneDirectory::displayByPrefix() { cout << "Display by prefix" << endl; sortedMap sortedData; friendMap::iterator itr; for (itr = database.begin(); itr != database.end(); itr++) sortedData.insert(sortedMap::value_type((*itr).second, (*itr).first)); for_each(sortedData.begin(), sortedData.end(), printSortedEntry); } The function used to print the sorted entries is the following: void printSortedEntry (const sorted_entry_type & entry) { cout << entry.first << ":" << entry.second << endl; } 9.3.2 ±×·¡ÇÁ A map whose elements are themselves maps are a natural representation for a directed graph. For example, suppose we use strings to encode the names of cities, and we wish to construct a map where the value associated with an edge is the distance between two connected cities. We could create such a graph as follows: typedef map stringVector; typedef map graph; const string pendleton("Pendleton"); // define strings for // city names const string pensacola("Pensacola"); const string peoria("Peoria"); const string phoenix("Phoenix"); const string pierre("Pierre"); const string pittsburgh("Pittsburgh"); const string princeton("Princeton"); const string pueblo("Pueblo"); graph cityMap; // declare the graph that holds the map cityMap[pendleton][phoenix] = 4; // add edges to the graph cityMap[pendleton][pueblo] = 8; cityMap[pensacola][phoenix] = 5; cityMap[peoria][pittsburgh] = 5; cityMap[peoria][pueblo] = 3; cityMap[phoenix][peoria] = 4; cityMap[phoenix][pittsburgh] = 10; cityMap[phoenix][pueblo] = 3; cityMap[pierre][pendleton] = 2; cityMap[pittsburgh][pensacola] = 4; cityMap[princeton][pittsburgh] = 2; cityMap[pueblo][pierre] = 3; The type stringVector is a map of integers indexed by strings. The type graph is, in effect, a two-dimensional sparse array, indexed by strings and holding integer values. A sequence of assignment statements initializes the graph. A number of classic algorithms can be used to manipulate graphs represented in this form. One example is Dijkstra's shortest-path algorithm. Dijkstra's algorithm begins from a specific city given as an initial location. A priority_queue of distance/city pairs is then constructed, and initialized with the distance from the starting city to itself (namely, zero). The definition for the distance pair data type is as follows: struct DistancePair { unsigned int first; string second; DistancePair() : first(0) { } DistancePair(unsigned int f, const string & s) : first(f), second(s) { } }; bool operator < (const DistancePair & lhs, const DistancePair & rhs) { return lhs.first < rhs.first; } In the algorithm that follows, note how the conditional test is reversed on the priority queue, because at each step we wish to pull the smallest, and not the largest, value from the collection. On each iteration around the loop we pull a city from the queue. If we have not yet found a shorter path to the city, the current distance is recorded, and by examining the graph we can compute the distance from this city to each of its adjacent cities. This process continues until the priority queue becomes exhausted. void shortestDistance(graph & cityMap, const string & start, stringVector & distances) { // process a priority queue of distances to cities priority_queue, greater > que; que.push(DistancePair(0, start)); while (! que.empty()) { // pull nearest city from queue int distance = que.top().first; string city = que.top().second; que.pop(); // if we haven't seen it already, process it if (0 == distances.count(city)) { // then add it to shortest distance map distances[city] = distance; // and put values into queue const stringVector & cities = cityMap[city]; stringVector::const_iterator start = cities.begin(); stringVector::const_iterator stop = cities.end(); for (; start != stop; ++start) que.push(DistancePair(distance + (*start).second, (*start).first)); } } } Notice that this relatively simple algorithm makes use of vectors, maps, strings and priority_queues. priority_queues are described in greater detail in Section 11. 9.3.3 A Concordance A concordance is an alphabetical listing of words in a text, that shows the line numbers on which each word occurs. We develop a concordance to illustrate the use of the map and multimap container classes. The data values will be maintained in the concordance by a multimap, indexed by strings (the words) and will hold integers (the line numbers). A multimap is employed because the same word will often appear on multiple different lines; indeed, discovering such connections is one of the primary purposes of a concordance. Another possibility would have been to use a map and use a set of integer elements as the associated values. class concordance { typedef multimap > wordDictType; public: void addWord (string, int); void readText (istream &); void printConcordance (ostream &); private: wordDictType wordMap; }; The creation of the concordance is divided into two steps: first the program generates the concordance (by reading lines from an input stream), and then the program prints the result on the output stream. This is reflected in the two member functions readText() and printConcordance(). The first of these, readText(), is written as follows: void concordance::readText (istream & in) { string line; for (int i = 1; getline(in, line, '\n'); i++) { allLower(line); list words; split (line, " ,.;:", words); list::iterator wptr; for (wptr = words.begin(); wptr != words.end(); ++wptr) addWord(*wptr, i); } } Lines are read from the input stream one by one. The text of the line is first converted into lower case, then the line is split into words, using the function split() described in Section 12.3. Each word is then entered into the concordance. The method used to enter a value into the concordance is as follows: void concordance::addWord (string word, int line) { // see if word occurs in list // first get range of entries with same key wordDictType::iterator low = wordMap.lower_bound(word); wordDictType::iterator high = wordMap.upper_bound(word); // loop over entries, see if any match current line for ( ; low != high; ++low) if ((*low).second == line) return; // didn't occur, add now wordMap.insert(wordDictType::value_type(word, line)); } The major portion of addWord() is concerned with ensuring values are not duplicated in the word map if the same word occurs twice on the same line. To assure this, the range of values matching the key is examined, each value is tested, and if any match the line number then no insertion is performed. It is only if the loop terminates without discovering the line number that the new word/line number pair is inserted. The final step is to print the concordance. This is performed in the following fashion: void concordance::printConcordance (ostream & out) { string lastword(""); wordDictType::iterator pairPtr; wordDictType::iterator stop = wordMap.end(); for (pairPtr = wordMap.begin(); pairPtr != stop; ++pairPtr) // if word is same as previous, just print line number if (lastword == (*pairPtr).first) out << " " << (*pairPtr).second; else { // first entry of word lastword = (*pairPtr).first; cout << endl << lastword << ": " << (*pairPtr).second; } cout << endl; // terminate last line } An iterator loop is used to cycle over the elements being maintained by the word list. Each new word generates a new line of output - thereafter line numbers appear separated by spaces. If, for example, the input was the text: It was the best of times, it was the worst of times. The output, from best to worst, would be: best: 1 it: 1 2 of: 1 2 the: 1 2 times: 1 2 was: 1 2 worst: 1