c++ - std::sort 做了很多不必要的交换

Question

我有以下代码，我尝试对两个简单 vector 进行字典顺序比较

class ExpensiveClass {
public:
  static int increment;
  std::vector<int> bigVector;

  ExpensiveClass() {
    for (int j = 0; j < 1 + increment; ++j)
      bigVector.emplace_back(j);
    ++increment;
  }
  ExpensiveClass(const ExpensiveClass& other) {
    std::cout << "Expensive copy constructor called!" << std::endl;
    this->bigVector = other.bigVector;
  }
};

int ExpensiveClass::increment = 0;

bool sortFunc(const ExpensiveClass& a, const ExpensiveClass& b) {
  bool ret = a.bigVector < b.bigVector;
  if (ret == false)
    std::cout << "Need to swap" << std::endl;
  return ret;
}

int main()
{
  std::vector<ExpensiveClass> vectorOfVectors;
  vectorOfVectors.reserve(100);
  for (int i = 0; i < 100; ++i)
    vectorOfVectors.emplace_back();

  std::cout << "Start sorting.." << std::endl;
  std::sort(vectorOfVectors.begin(), vectorOfVectors.end(), sortFunc);
}

而且我想知道为什么 std::sort 即使在已排序的 vector 上也要进行大量交换？

Answer 1

我认为我们正在进入 STL 的黑暗角落。我研究了您的代码，发现您的 sortFunc() 并不总是返回 true。这是因为传递的参数没有按顺序排列。 std::sort 算法从您的 vectorOfVectors 中选择乱序的元素，即它是 vectorOfVectors< 中 a 的索引 不保证高于 b 的索引。但我不知道如何深入研究，所以我创建了一个单独的问题:https://stackoverflow.com/questions/30539898/counter-intuitive-behavior-of-stdsort

无论如何，我的观点是您对 std::sort 的行为做出了一些假设，但这取决于实现。