Pregunta cómo verificar fácilmente si un std :: map y std :: unordered_map contienen los mismos elementos


Estoy escribiendo una prueba de unidad de prueba de Google, y quiero verificar si el contenido de un unordered_map<std::string, std::string> es lo mismo que std::map<std::string, std::string>

No creo std::equal funcionará, como elementos en el std::map se ordenan según un criterio El orden no es importante.


11
2017-08-28 12:05


origen


Respuestas:


No creo que haya una manera más agradable que revisar todos los elementos de un mapa y verificar si están presentes en el otro mapa. Si también verifica que la cantidad de elementos sea la misma, sabrá si los mapas son completamente iguales.

Por ejemplo:

template<typename K, typename E>
bool maps_equal(const std::map<K, E> &map, const std::unordered_map<K, E> &unordered_map) {
    return
        map.size() == unordered_map.size() &&
        std::all_of(map.cbegin(), map.cend(), [&](const std::pair<const K, E> &item) {
            auto iter = unordered_map.find(item.first);
            return iter != unordered_map.end() && iter->second == item.second;
        });
}

14
2017-08-28 12:21



Puedes crear un unordered_map con un mapy luego compara dos unordered_map. Y viceversa.

std::unordered_map<std::string, std::string> m1;
std::map<std::string, std::string> m2;
std::unordered_map<std::string, std::string> m3(m2.begin(), m2.end());
if (m1 == m3) {}

9
2017-08-28 12:22



Haré una pregunta obvia, pero realmente cambia todo:

Es la noción de igualdad en el map compatible con la noción de igualdad en el unordered_map?

Como ejemplo de definiciones incompatibles:

struct Point3D { std::int32_t x, y, z };

struct MapLess {
    bool operator()(Point3D const& left, Point3D const& right) const {
       return std::tie(left.x, left.y) < std::tie(right.x, right.y);
    }
};

bool operator==(Point3D const& left, Point3D const& right) {
    return std::tie( left.x,  left.z)
        == std::tie(right.x, right.z);
}

En este caso (artificial), podríamos tener:

  • map: (1, 2, 3) y (1, 3, 3)
  • unordered_map: (1, 2, 3) y (1, 2, 4)

y una búsqueda ingenua informaría que el map está incluido en el unordered_map que dado que ambos tienen el mismo tamaño conducirían a la conclusión errónea de que son iguales.


La solución si existe una noción canónica de igualdad es verificar, después de cada búsqueda, que el resultado de búsqueda es efectivamente el mismo que el original.

template <typename M1, typename M2>
bool equal(M1 const& left, M2 const& right) {
    if (left.size() != right.size()) { return false; }

    for (auto const& e: left) {
        auto const it = right.find(e.first);

        if (it == right.end()) { return false; }
        if (it->first != e.first) { return false; }
        if (it->second != e.second) { return false; }
    }

    return true;
}

Nota: esto podría ser reescrito con std::all y una única expresión booleana; es una cuestión de gusto, prefiero descomponerlo.

Si no existe una noción canónica de igualdad, una búsqueda inversa puede reemplazar la verificación de igualdad:

template <typename M1, typename M2>
bool equal(M1 const& left, M2 const& right) {
    if (left.size() != right.size()) { return false; }

    for (auto e = left.begin(), end = left.end(); e != end; ++e) {
        auto const it = right.find(e->first);

        if (it != right.end()) { return false; }
        if (left.find(it->first) != e) { return false; }
        if (it->second != e->second) { return false; }
    }

    return true;
}

Esto es, por supuesto, un poco más caro.


1
2017-08-28 23:09