Как объединить две карты в STL и применить функцию для конфликтов? - PullRequest
Новая
       8

Как объединить две карты в STL и применить функцию для конфликтов?

0 голосов
/ 08 ноября 2018

Я прочитал вопрос Слияние двух карт STL , и хотя он близок, я искал функциональность, подобную описанной здесь .

Короче говоря, я хотел бы объединить два std::map экземпляра (с одинаковым ключом и типом значения) в один, с оговоркой, что я хотел бы добавить значения вместе, если объект существует на обеих картах.

Существует ли существующая функция boost , range-v3 или std , которая может сделать это? А если нет, то как лучше всего это сделать?

Пример кода: 

double mergePredicate(double lhs, double rhs)
{
    return lhs + rhs;
}

int main()
{
    std::map<int, double> mapA = { {0, 1.0}, {1, 2.0} };
    std::map<int, double> mapB = { {1, 1.5}, {2, 2.5} };

    // Merge maps in some way...
    merge(mapA, mapB, mergePredicate);

    // result: mapA == { {0, 1.0}, {1, 3.5}, {2, 2.5} }
    for (const auto& p : mapA) {
        std::cout << p.first << " " << p.second << std::endl;
    }
}

Ответы [ 3 ]

0 голосов
/ 08 ноября 2018

Я не знаю ни одной существующей функции для этого, но вы можете использовать функцию std::map merge ( живой пример ): 

template<typename K, typename V, typename F>
void mergeWithConflicts(std::map<K, V>& base, std::map<K, V> toMerge, F combine) {
    base.merge(toMerge);

    // All that's left in toMerge is conflicting keys
    for (const auto& [k, v] : toMerge) { 
        base[k] = combine(base[k], toMerge[k]);
    }
}

В качестве бонуса, реализация merge довольно эффективна по сравнению с тем, что вы можете сделать вручную, если вы не переопределите ее, используя extract. Вместо копирования или перемещения элементов он настраивает внутренние указатели для перемещения узлов с одной карты на другую. Однако это означает, что он изменяет другую карту. Как и предполагалось, параметр берется по значению, поэтому другую карту можно переместить, если она больше не нужна, и скопировать в противном случае.

0 голосов
/ 08 ноября 2018

Я не знаю ни одной существующей функции для этого, но вы можете свернуть свою собственную из чего-то похожего на реализацию std :: merge , чтобы иметь линейную сложность: 

template<class Map, class Merger>
void merge(Map& dest, const Map& source, Merger merger)
{
    auto it1 = dest.begin();
    auto it2 = source.begin();
    auto&& comp = dest.value_comp();

    for (; it1 != dest.end() && it2 != source.end(); ) {
        if (comp(*it1, *it2)) {
            ++it1;
        } else if (comp(*it2, *it1)) {
            dest.insert(it1, *it2); // with hint to have correct complexity
            ++it2;
        } else { // equivalent
            it1->second = merger(it1->second, it2->second);
            ++it1;
            ++it2;
        }
    }
    dest.insert(it2, source.end());
}

Демо

0 голосов
/ 08 ноября 2018

Для этого конкретного случая, поскольку operator[] создает ключ, если он не существует, вы можете использовать простой цикл для добавления двух значений: 

for (const auto& pair : mapB) {
    mapA[pair.first] += pair.second;
}

И когда вы хотите использовать функцию, но допустимо использовать значение, инициализированное по умолчанию, где нет ключа: 

for (const auto& pair : mapB) {
    mapA[pair.first] = mergePredicate(mapA[pair.first], pair.second);
}
...