这里有一个不同的镜头，它只需要一个新的容器，并且只复制一个列表。

#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。第二个列表被迭代并搜索Map（O（1））。如果没有找到，我们可以立即返回。如果找到，键被设置为false。然后我们必须搜索unordered_map，看看是否有任何元素处于true状态。
我还没有运行任何基准测试，所以需要测试来看看这个解决方案是否更有效。理论上，两者都是O（3N），但是平均运行时间需要测试。
但是，尽管运行时效率的提高是模糊的，但这种方法确实提供了明显的空间效率优势。您当前的算法目前需要约2N个空间，而我的算法更接近N。

为完整起见：你也可以尝试使用std算法。假设你不想修改你的输入，你需要拷贝。（对于只有一个拷贝的解决方案，见@sweenish answer。）

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

我使用了大量的测试数据，这些数据使用了大小为4到128个字符的std::string密钥和0到32个元素的密钥集，对带有小突变的密钥集进行了200'000次比较，得到了以下结果：
| 执行情况|每次呼叫的平均时间|平均时间（如果相等）|速度增益|
| - ------|- ------|- ------|- ------|
| 原始的|0.005232毫秒|0.005444毫秒|1×|
| 卡巴|0.004337毫秒|0.004275毫秒|1.21倍|
| 瑞典的|0.002796毫秒|0.003919毫秒|1.87倍|
| 该解决方案|0.000566毫秒|0.001305毫秒|9.24倍|
该算法还具有最低的内存使用率。