Determine if one string is a permutation of the another Can anyone give me some feedback if I'm using std::unordered_multimap optimally? I don't know the ins-and-outs of the std::unordered_multimap implementation.

I'm wondering if comparing two maps iterates through each of the elements in the map, making the algorithm \$O(N^2)\$ or if it just compares the hash of the map or something making the algorithm \$O(N)\$. Or would it just be better to use an array if I'm given this question in an interview?

bool is_permutation(const std::string&amp; s1, const std::string&amp; s2)
{
    assert(s1.size() &amp;&amp; s2.size());

    if(s1.length() != s2.length())
        return false;

    std::unordered_multimap&lt;int, char&gt; m1, m2;

    for(int i = 0; i &lt; s1.length(); ++i)
    {
        m1.insert({s1[i], s1[i]});
        m2.insert({s2[i], s2[i]});
    }

    if(m1 == m2)
        return true;

    return false;
}
I would say yes, use an array. 

Arrays afford very good memory locality, which is good for cache performance. They essentially are the most basic and efficient hash map if the key is the index. 

You only need one array with 256 elements: first count up the number of times each character appears in the first string, and then count down for the number of times each character appears in the second string. Precisely if the two strings are permutations, the array will finish with all zeroes. 

As a further hint at relative complexity, according to godbolt.org, your code produces 849 lines of assembly when compiled on the most recent GCC with -O3 optimisation.
The following code produces 53 lines. 

bool is_permutation(const std::string&amp; s1, const std::string&amp; s2)
{
    if(s1.length() != s2.length())
        return false;

    // There are usually 256 possible characters but on rare architectures may be more.
    constexpr possible_char_count = std::numeric_limits&lt;unsigned char&gt;::max()+1;
    std::array&lt;size_t, possible_char_count &gt; m1 = {}; // Zero initialized all places

    for(char c : s1) { // Count up for each character in the first string
        m1[static_cast&lt;unsigned char&gt;(c)]++; 
    }
    for(char c : s2) { // Count down for each character in the second string
        m1[static_cast&lt;unsigned char&gt;(c)]--; 
    }

    for (size_t t : m1) { 
        // If any character appears a net nonzero number of times,
        // the two strings are not anagrams.
        if (t != 0) { 
            return false;
        }
    }
    return true;
}


Lines of code are not, of themselves, a perfect indicator of what is the most efficient algorithm. After all, you can implement a nice short version of bubble sort! Nevertheless when the underlying approach is the same (that of counting characters) it is a fairly good indicator that one implementation is doing unnecessary work. 

One reason to prefer a map to an array is that when the input strings are very short or very homogenous, then the map is likely to be more memory efficient. This may translate into speed improvements by avoiding allocation and inialisation overhead. As always, the only reliable way to decide is to profile with your real world inputs.