<p>Roman numerals are represented by seven different symbols:&nbsp;<code>I</code>, <code>V</code>, <code>X</code>, <code>L</code>, <code>C</code>, <code>D</code> and <code>M</code>.</p>

<pre>
<strong>Symbol</strong>       <strong>Value</strong>
I             1
V             5
X             10
L             50
C             100
D             500
M             1000</pre>

<p>For example,&nbsp;<code>2</code> is written as <code>II</code>&nbsp;in Roman numeral, just two ones added together. <code>12</code> is written as&nbsp;<code>XII</code>, which is simply <code>X + II</code>. The number <code>27</code> is written as <code>XXVII</code>, which is <code>XX + V + II</code>.</p>

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

<ul>
	<li><code>I</code> can be placed before <code>V</code> (5) and <code>X</code> (10) to make 4 and 9.&nbsp;</li>
	<li><code>X</code> can be placed before <code>L</code> (50) and <code>C</code> (100) to make 40 and 90.&nbsp;</li>
	<li><code>C</code> can be placed before <code>D</code> (500) and <code>M</code> (1000) to make 400 and 900.</li>
</ul>

<p>Given a roman numeral, convert it to an integer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;III&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> III = 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;LVIII&quot;
<strong>Output:</strong> 58
<strong>Explanation:</strong> L = 50, V= 5, III = 3.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;MCMXCIV&quot;
<strong>Output:</strong> 1994
<strong>Explanation:</strong> M = 1000, CM = 900, XC = 90 and IV = 4.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 15</code></li>
	<li><code>s</code> contains only&nbsp;the characters <code>(&#39;I&#39;, &#39;V&#39;, &#39;X&#39;, &#39;L&#39;, &#39;C&#39;, &#39;D&#39;, &#39;M&#39;)</code>.</li>
	<li>It is <strong>guaranteed</strong>&nbsp;that <code>s</code> is a valid roman numeral in the range <code>[1, 3999]</code>.</li>
</ul>

typedef std::pair<std::string, int> pairs;
std::vector<pairs> map_roman = {{"I",1},{"IV",4},{"V",5},{"IX",9},
                                {"X",10},{"XL",40},{"L",50},{"XC",90},
                                {"C",100}, {"CD",400},{"D",500},{"CM",900},
                                {"M",1000}};
class Solution {
public:
    
    int romanToInt(std::string s) {
        std::vector<int> vec;
        auto it = map_roman.rbegin();
        int i = 0;
        while (true)
        {
            if (i == s.length())
                    break;
            if (it->first.length()==1){
                if (s[i] == it->first.c_str()[0])
                {
                    vec.push_back(it->second);
                    // std::cout << "1 " << vec.back() << std::endl;
                    i++;
                }
                else
                {
                    it++;
                    if (it == map_roman.rend())
                        break;
                }
                
            }
            else
            {
                if ( i < s.length() - 1 && s[i] == it->first.c_str()[0] && s[i+1] == it->first.c_str()[1])
                {
                    vec.push_back(it->second);
                    it++;
                    i+=2;
                }
                else{
                    it++;
                }
            }
        }
        int vec_sum = 0;
        for (auto it = vec.begin(); it!=vec.end(); ++it)
        {
            vec_sum+=*it;
        }
        return vec_sum;
    }
};
11500