Преобразование этой строки Python в C ++?

diff = list(set(map(tuple, paths1)) - set(map(tuple, paths2)))

куда paths1 а также paths2 список списка пар.

Пример:

paths1 = [[(1,2),(2,3),(3,4)],[(1,3),(3,5)]]
paths2 = [[(5,2),(2,3),(3,4)],[(1,3),(3,5)]]
print(list(set(map(tuple, paths1)) - set(map(tuple, paths2))))

Должен выводить [((1, 2), (2, 3), (3, 4))], Внутренний список должен быть сначала преобразован в кортеж, потому что этот тип списка нельзя хешировать в набор.

В приведенном ниже коде C ++ я попытался использовать функцию set_difference из стандартной библиотеки:

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

int main () {

std::vector < std::pair < int, int >>v1 =
{ std::make_pair (1, 2), std::make_pair (2, 3), std::make_pair (3, 4) };
std::vector < std::pair < int, int >>v2 =
{ std::make_pair (5, 2), std::make_pair (2, 3), std::make_pair (3, 4) };
std::vector < std::pair < int, int >>v3 =
{ std::make_pair (1, 3), std::make_pair (3, 5) };

std::vector < std::vector < std::pair < int, int >>>V1 = { v1, v3 };
std::vector < std::vector < std::pair < int, int >>>V2 = { v2, v3 };
std::vector < std::vector < std::pair < int, int >>>diff;

std::set_difference (V1.begin (), V1.end (), V2.begin (), V2.end (),
std::inserter (diff, diff.begin ()));

std::cout << "[";
for (auto v : diff) {
std::cout << "[";
for (auto p : v)
std::cout << "(" << p.first << "," << p.second << ")";
std::cout << "]";
}
std::cout << "]\n";

}

Этот код напечатан [[(1,2)(2,3)(3,4)][(1,3)(3,5)]], Почему второй внутренний список не удаляется, когда это должно быть?

-1

Решение

Наборы Python основаны на хешировании. Таким образом, разница наборов Python работает путем итерации левого набора, поиска каждого элемента в хэш-карте правого набора и пропуска соответствующих элементов.

Наборы C ++ основаны на сортировке (фактически, бинарных деревьях поиска), а не на хешировании. Тот же алгоритм будет работать, но это займет (логарифмическое вместо линейного времени. Таким образом, они используют другой алгоритм, который делает работать в линейном времени: предполагая, что оба диапазона отсортированы, вы можете просто пройти два параллельно.

Соответственно С ++ set_difference работает только на отсортированных диапазонах:

Копирует элементы из отсортированного диапазона [first1, last1) которые не найдены в отсортированном диапазоне [first2, last2) к диапазону, начинающемуся в d_first,

Когда вы даете ему несортированные диапазоны, он не знает, что вы сделали это, и пытается пройти их параллельно, и запутывается. После того, как левый список проходит (5, 2), он уже прошел все остальные элементы, поэтому больше ничего не пропускается.

4

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector