c++ - 在遍历 vector 时一遍又一遍地比较 vector 内部的一组两个整数

Question

我有一个整数 vector ，我想继续比较每一对，直到比较完所有整数。我想找到这对之间的绝对差异。例如:

30
25
65
183
83
22

比较30和25，然后比较65和183，再比较83和22，以此类推。我想找出每次比较的绝对差异。这些数字都是随机的，因此它必须在对中找到较大的整数，然后从最小的整数中减去它。我该怎么做呢？

Answer 1

尝试在数组索引上使用迭代器——对于大型集合，您会看到不同之处。

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>

int main()
{
  std::vector <int> xs = { 30, 25, 65, 183, 83, 22, -3 };
  std::vector <int> ds;

  auto print = [&]()
  {
    for (int d : ds)
      std::cout << d << " ";
    std::cout << "\n";
  };

  // method one (two-pass using standard algorithms)
  {
    std::adjacent_difference( begin(xs), end(xs), std::back_inserter( ds ), 
      []( int a, int b ) { return std::abs( b - a ); } 
    );
    bool b = false;
    ds.erase( std::remove_if( begin(ds), end(ds), [&b]( auto foo ) { return b = !b; } ), end(ds) );
  }
  print();

  // method two (one-pass for random access iterators, two-pass for sequential iterators)
  ds.clear();
  {
    auto a = begin(xs);
    auto b = next(a);
    auto n = std::distance( begin(xs), end(xs) ) / 2;
    while (n--)
    {
      ds.emplace_back( std::abs( *b - *a ) );
      a = next(b);
      b = next(a);
    }
  }
  print();

  // method three (one-pass for sequential iterators)
  ds.clear();
  {
    auto a = begin(xs);
    auto b = next(a);
    while (a != end(xs) and b != end(xs))
    {
      ds.emplace_back( std::abs( *b - *a ) );
      a = next( b );
      b = next( a );
    }
  }
  print();
}

方法一仅使用标准算法，效果很好，并且易于阅读。它总是进行两次传递，并且比其他两种算法具有双倍的内存需求。

如果您有随机访问迭代器，方法二是最有效的。它通过一次，只使用所需的内存。您可以使用简单的 ds.reserve( n ) 和简单的赋值来调整内存需求，假设 ds 也通过随机访问迭代器访问。

方法三是一种变体，它不假设您的输入迭代器并且仍然使用单次传递。 (它可能仍然会在流迭代器上失败，除非你记住一些数据......大声笑，感谢 C++。)