Каков наиболее ресурсоэффективный способ проверить, содержат ли два списка std::list одинаковые уникальные элементы?

Вот другой вариант. Требуется только один новый контейнер, и копируется только один список.

#include <cassert>
#include <list>
#include <string>
#include <unordered_map>

template <typename T>
auto areListsAsSetsEqual(const std::list<T>& a, const std::list<T>& b) -> bool {
  std::unordered_map<T, bool> firstListKeys;
  for (const auto& i : a) {
    firstListKeys[i] = true;
  }

  for (const auto& i : b) {
    if (firstListKeys.find(i) != firstListKeys.end()) {
      firstListKeys[i] = false;
    } else {
      return false;
    }
  }

  for (const auto& p : firstListKeys) {
    if (p.second == true) {
      return false;
    }
  }

  return true;
}

auto main() -> int {
  auto x = std::list<std::string>{"red", "blue", "yellow", "green", "green"};
  auto y = std::list<std::string>{"blue", "green", "yellow", "red", "red"};
  auto z = std::list<std::string>{"green", "red", "yellow"};

  auto xyEqual = areListsAsSetsEqual(x, y);
  assert(xyEqual == true);
  auto xzEqual = areListsAsSetsEqual(x, z);
  assert(xzEqual == false);
  return 0;
}

Первый список копируется в std::unordered_map, и каждому ключу присваивается значение true. Второй список повторяется и ищет карту (O (1)). Если не нашли, можем сразу вернуть. Если найдено, ключ устанавливается на false. Затем нам нужно найти unordered_map, чтобы увидеть, остались ли какие-либо элементы в состоянии true.

Я не проводил никаких тестов, поэтому потребуется тестирование, чтобы увидеть, является ли это решение более эффективным. На бумаге оба работают со скоростью O(3N), но необходимо проверить среднее время выполнения.

Но хотя прирост эффективности во время выполнения невелик, этот метод дает явное преимущество в эффективности использования пространства. Ваш текущий алгоритм в настоящее время требует ~ 2N пространства, где мой ближе к N.

Для полноты: вы также можете попробовать использовать стандартные алгоритмы. Предполагая, что вы не хотите изменять свои входные данные, вам понадобятся копии. (Решение только с одной копией см. в ответе @sweenish.)

#include <list>
#include <string>
#include <cassert>
#include <algorithm>
#include <iterator>
#include <vector>

template<typename T>
auto areListsEqual(std::list<T> const &a, std::list<T> const &b) -> bool {
    std::vector<T> aVector(a.size());
    std::partial_sort_copy(a.cbegin(), a.cend(), aVector.begin(), aVector.end());
    auto aEnd = std::unique(aVector.begin(), aVector.end());
    
    std::vector<T> bVector(b.size());
    std::partial_sort_copy(b.cbegin(), b.cend(), bVector.begin(), bVector.end());
    auto bEnd = std::unique(bVector.begin(), bVector.end());

    return std::distance(aVector.begin(),aEnd) == std::distance(bVector.begin(),bEnd)
         ? std::equal(aVector.begin(), aEnd, bVector.begin())
         : false;
}

auto main() -> int {
    auto x = std::list<std::string>{"red", "blue", "yellow", "green", "green"};
    auto y = std::list<std::string>{"blue", "green", "yellow", "red", "red"};
    auto z = std::list<std::string>{"green", "red", "yellow"};
    auto w = std::list<std::string>{"green", "red", "yellow", "black"};

    auto xyEqual = areListsEqual(x, y);
    assert(xyEqual == true);
    auto xzEqual = areListsEqual(x, z);
    assert(xzEqual == false);
    auto xwEqual = areListsEqual(x, w);
    assert(xwEqual == false);
    return 0;
}

Это решение не будет быстрее с точки зрения «большого O». Но он использует последовательные контейнеры в качестве промежуточного хранилища, что может быть более эффективным с точки зрения кэширования на современном оборудовании. Как всегда с оптимизацией в наши дни, вы должны измерять с репрезентативными данными.

Для полноты этого вопроса самый быстрый алгоритм примерно основан на ответе от sweenish, но работает без копий исходных данных. Следовательно, следующий алгоритм лучше при следующих двух условиях:

• Создание копии/хэша элементов в списке дорого (например, для std::string или строк в целом.
• Последовательный поиск элементов в контейнере выполняется быстро (короткие списки, быстрое сравнение).

#include <vector>
#include <list>
#include <algorithm>
#include <string>

template<typename T>
auto areListsAsSetsEqual(const std::list<T> &a, const std::list<T> &b) -> bool {
    auto keyMap = std::vector<bool>(a.size(), false);
    const auto srcEndA = a.end();
    const auto srcEndB = b.end();
    std::size_t keyIndex = 0;
    for (auto it = a.begin(); it != srcEndA; ++it, ++keyIndex) {
        if (std::find(a.begin(), it, *it) == it) {
            keyMap[keyIndex] = true;
        }
    }
    for (const auto &element : b) {
        auto foundIt = std::find(a.begin(), a.end(), element);
        if (foundIt == a.end()) {
            return false;
        }
        keyMap[std::distance(a.begin(), foundIt)] = false;
    }
    return std::all_of(keyMap.begin(), keyMap.end(), [](bool flag) -> bool { return !flag; });
}

auto main() -> int {
    auto x = std::list<std::string>{"red", "blue", "yellow", "green", "green"};
    auto y = std::list<std::string>{"blue", "green", "yellow", "red", "red"};
    auto z = std::list<std::string>{"green", "red", "yellow"};

    auto xyEqual = areListsAsSetsEqual(x, y);
    assert(xyEqual == true);
    auto xzEqual = areListsAsSetsEqual(x, z);
    assert(xzEqual == false);
    return 0;
}

Используя мои обширные тестовые данные, в которых используются ключи std::string размером от 4 до 128 символов и наборы ключей от нуля до 32 элементов. Сделав 200 000 сравнений наборов с небольшими мутациями, я получаю такие результаты:

Алгоритм также имеет наименьшее использование памяти.