测试两个 std：：lists 是否包含相同的唯一元素的最省资源的方法是什么？

这是一个不同的看法。它只需要一个新容器，并且只复制一个列表。

#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;
}

第一个列表将复制到 中，并且每个键都设置为 。第二个列表将迭代并搜索地图 （O（1））。如果没有找到，我们可以立即返回。如果找到，则将密钥设置为 。然后，我们必须搜索 以查看是否有任何元素留在状态中。std::unordered_maptruefalseunordered_maptrue

我没有运行任何基准测试，因此需要测试以查看此解决方案是否更有效。从理论上讲，两者都以 O（3N） 运行，但平均运行时间需要测试。

但是，虽然运行时效率的提高是模糊的，但这种方法确实提供了明显的空间效率优势。您当前的算法目前需要 ~2N 个空间，而我的空间更接近 N。

为了完整起见：您也可以尝试使用 std 算法。假设您不想修改输入，则需要副本。（对于只有一个副本的解决方案，请参阅@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;
}

就“big-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;
}

使用我广泛的测试数据，该数据使用大小从 4 到 128 个字符的键和 0 到 32 个元素的键集。对具有小突变的集合进行 200'000 次比较，我得到以下结果：std::string

该算法还具有最低的内存使用率。