[教學]C++ Map(STL)詳細用法 @ 一個小小工程師的心情抒發天地

會有這一篇的產生，是因為早上在刷 leetcode的時候，突然想說是不是好想沒有更新文章了，也好久沒有時間靜下來寫教學了，所以，乾脆就拿今天解題的方法來寫一篇文章算了。

而在找資料的同時，也發現一件有趣的事情，原來，Map的教學，我在許久前就曾經寫過一次，回頭再看看自己青澀的文章，到也挺有意思的。

這一篇我盡量不撞文，在簡單的提及基本用法後，我將直接以實際來演示如何操作，前一篇著重於在講解的部分，而這一篇我將重是使用的方法，那麼，本文即將開始，各位看官，請繫好安全帶，如果有錯，請不吝指教，謝謝。

Map

Maps are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order.

In a map, the key values are generally used to sort and uniquely identify the elements, while the mapped values store the content associated to this key. The types of key and mapped value may differ, and are grouped together in member type value_type, which is a pair type combining both:

typedef pair<const Key, T> value_type;

透過上述這段話來看，在Map裡面，並不會出現同樣的Key，也就是說，如果你第一個Key存在，當同樣的Key在Insert的時候，第二個會覆蓋掉第一個，讓我們舉一個很簡單的例子，搭配如何建構和初始化Map來看這段話吧 :

    std::map<char, int> first;

    first['a'] = 10;
    first['b'] = 50;
    first['c'] = 30;
    first['a'] = 70;
    std::map<char, int> second(first.begin(), first.end());
    std::map<char, int> third(second);
    /* 
    *    first & second & third : size = 3
        value :      key    value
                [0]: 'a'     70 
                [1]: 'b'     50
                [2]: 'c'     30
    
    __DBG__
    */
    for (auto & x : first)
    {
        cout << x.first << ":" << x.second << endl;
    }

Map總共有兩個值

x.first : 第一個稱為關鍵字(key)，在Map裡面，絕對不會重複.

x.second:第二個稱為關鍵字的值(value).

這裡的Output會是 :

而其原因則是因為，第四個的['a']是已經重複的，於是，他覆蓋了第一個了。

這樣做其實有一個好處，那就是可以確定資料的唯一性，假如說，今天你有一筆很固定的資料，你就可以透過這樣的方式，將資料存到Map裡面去，

屆時，你要修改值，你只需要透過相對應的Key，去修改，如此一來，也挺方便的，對吧。

Map 的特色

Map的內部資料結構為一顆紅黑樹(red-black tree)，因此，他理所當然就是擁有紅黑樹的特點 :
1. 內部是有排序的資料。

2. 它可以在O(log n)時間內完成尋找，插入和刪除。(n = 樹中元素的數目)

3. 可以修改Value但是不能修改Key.

4. 以模板(泛型)的方式實現，可以儲存任意類型的數據，包括自定義的.



mapmymap = {
		{ "alpha", 0 },
		{ "beta", 0 },
		{ "gamma", 0 },
	};
	mymap.at("alpha")		= 10;
	//mymap.at("beta0000")	= 99999;// exception: invalid map
	mymap.at("gamma")		= 50;
	/*
	*	mymap : size = 3
	value :    key		value
		[0]: 'alpha'     10
		[1]: 'beta'      0		// exception: invalid map 
		[2]: 'gamma'     50
	__DBG__
	for (auto & x : mymap)
	{
		cout << x.first << ":" << x.second << endl;
	}
	*/



	mapmymap_begin;
	mymap_begin['b'] = 100;
	mymap_begin['a'] = 200;
	mymap_begin['c'] = 300;

	// show content:
	for (map::iterator it = mymap_begin.begin(); it != mymap_begin.end(); ++it)
	{
		cout << it->first << "=>" << it->second << endl;
	}
	/*
		Output:
		a=>200
		b=>100
		c=>300
		sort finish!
	*/

Map使用

因為在之前已經有寫過教學了，所以我在這裡我就不多做講解，就直接上程式碼，大家可以透過程式來看一下，可以的話，自己敲幾行，應該不會到難以理解才是。



// constructing maps
#include 
#include
#include 
using namespace std;

int main()
{
	maptempMap;
	map::iterator iter;
	map::reverse_iterator iter_reverse;

	// 1.Insert element to tempMap 
	tempMap.insert(pair("Eric", "No.1"));
	tempMap["Banana"] = "No.2";
	tempMap["Apple"]  = "No.3";

	// Print information (A & B, It's same)
	/*
	A:	for (iter = tempMap.begin(); iter != tempMap.end(); iter++)
			cout << iter->first << "=>" << iter->second << endl;
	B:	for (auto temp : tempMap)
			cout << temp.first << "=>" << temp.second << endl;

		Output:
		Apple=>No.3
		Banana=>No.2
		Eric=>No.1
	-------------------------------------------------------------*/
	// 2.Traversal
	for (iter_reverse = tempMap.rbegin(); iter_reverse != tempMap.rend(); iter_reverse++)
		cout << iter_reverse->first << "=>"<second << endl;
	/*
		Output:
		Eric=>No.1
		Banana=>No.2
		Apple=>No.3
	-------------------------------------------------------------*/


 
// 3.Find and erase the element
	iter = tempMap.find("Apple");
	if (iter->first == "Apple")
	{
		cout << "Find the Key, Value : " << iter->second << endl;
		cout << "Erase iter-------------------------------------" << endl;
		tempMap.erase(iter);
		for (auto T : tempMap)
		{
			cout << T.first << "=>" << T.second << endl;
		}
	}
	else
	{
		cout << "Can't find key[Apple]"<<endl;
  }
    return 0;
}

Leet Code實際應用

Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.


 
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>

using namespace std;

int romanToInt(string s)
{
	unordered_mapT = {
		{ 'I', 1 },
		{ 'V', 5 },
		{ 'X', 10 },
		{ 'L', 50 },
		{ 'C', 100 },
		{ 'D', 500 },
		{ 'M', 1000 },
	};
	int sum = T[s.back()];
	for (int i = s.length() - 2; i >= 0; --i)
	{
		if (T[s[i]] < T[s[i + 1]])
		{
			sum -= T[s[i]];
		}
		else
		{
			sum += T[s[i]];
		}
	}
	return sum;
}


int main()
{
	string strTemp;
	while (cin >> strTemp && strTemp != "0")
	{
		cout << romanToInt(strTemp) << endl;
	}
	getchar();
}