Почему в std :: map есть механизм сортировки?

Question

Я хочу использовать std::map в качестве пары ключ / значение и хочу сохранить порядок, в котором эти пары ключ / значение были вставлены.Когда я печатаю свои значения, порядок переставляется как-то.Ниже мой код

string removeDuplicates(string& s)
{
    // string& s = "asdasdasd"
    map<char, int> duplicates;
    for (int i = 0; i < s.length(); i++) {
        duplicates[s[i]]++;
    }
    map<char, int>::iterator itr = duplicates.begin();
    string result;
    while (itr != duplicates.end())
    {
        result += itr->first;
        itr++;
    }
    return result;
}

Я вставил "asdasd", и я ожидал "asd", но результат был "ads"

Answer 1

Это особенность, а не ошибка.Это способ создания std::map - обход красно-черного дерева, на котором основана карта, всегда в порядке ключа карты.

Возможно, вы захотите попробовать std::unordered_map, но вы не получите желаемых результатов.Это будет проходить в порядке, который вы могли бы также назвать «случайным».

Если вы хотите сохранить исходный порядок символов, появляющихся в строке, вам придется сделать это самостоятельно.Но вы можете сделать это и построить строку результата одновременно:

string removeDuplicatesKeepingOriginalOrder(string const& s)
{
    // string& s = "asdasdasd"
    string result;
    std::map<char, int> index;
    auto si = s.begin();
    auto se =s.end();
    while (si!=se)
    {
       auto f = index.find (*si);
       if (f==index.end())
       {
          ++index[*si];
          result.push_back(*si);
          ++si;
       }
    }
    return result;
}

Answer 2

После прохождения обновленного ответа Спенсера я не думаю, что нам вообще нужна карта, при условии, что наша цель - только удалить дубликаты из строки.Вот мое решение только с std :: string

string removeDuplicatesKeepingOriginalOrder(string const& s)
{
    string result;
    for(std::size_t i=0;i<s.size();i++)
    {
        if(result.find(s[i]) == std::string::npos)
        {
            result.push_back(s[i]);
        }
    }
    return result;
}