Объединить записи в карте, если значение равно ключу - PullRequest
Новая
       19

Объединить записи в карте, если значение равно ключу

1 голос
/ 11 апреля 2019

У меня есть std :: map со следующими значениями:

2 31
4 36
5 29
6 24
24 49
2583
29 63
36 42
42 79

Теперь я хочу "объединить" значения, если для значения существует ключ.Таким образом, желаемый результат (структура данных не имеет значения) будет:

2 31
4 36 42 79
5 29 63
6 24 49
25 83

Я пробовал перебирать карту и использовать std :: find для каждого значения.Но у меня проблемы с размерами векторов больше 3, и это кажется очень медленным для больших карт.Вот небольшой пример, не дающий желаемого результата: 

int main(int argc, char** argv)
{   
    std::map<int, int> my_map = { {2, 31}, {4, 36}, {5, 29}, {6, 24}, {24, 49}, {25, 83}, {29, 63}, {36, 42}, {42, 79} };

    std::vector<int> temp_vec;
    std::vector<std::vector<int>> destination_vec;

    for (auto it = my_map.begin(); it != my_map.end(); ++it) {

        std::map<int, int>::iterator map_iterator = my_map.find(it->second);
        if (map_iterator == my_map.end()) {
            temp_vec.push_back(it->first);
            temp_vec.push_back(it->second);
        }
        else {
            temp_vec.push_back(it->first);
            temp_vec.push_back(it->second);
            temp_vec.push_back(map_iterator->second);
            // I stopped here because I could try another if loop here or a while loop for the whole process but it seems very inefficient
        }
        destination_vec.push_back(temp_vec);
        temp_vec.clear();
    }
}

1 Ответ

3 голосов
/ 11 апреля 2019

Если ваша карта не может связать меньшие значения (как {{1, 42},{2, 1}}).

Вы можете использовать: 

std::map<int, std::vector<int>> foo(std::map<int, int> m)
{
    std::map<int, std::vector<int>> res;

    while (!m.empty())
    {
        auto it = m.begin();
        const auto key = it->first;
        auto& v = res[key];

        while (it != m.end()) {
            auto value = it->second;
            v.push_back(value);
            m.erase(it);
            it = m.find(value);
        }
    }
    return res;
}

Демо

сложностьO(n log n).

...