有没有办法使用 C++ 标准库对结构体集合中的单个成员变量进行排序？

Question

假设我有一个非常简单结构的向量：

struct SimpleStruct { int a; int b; int c; };
std::vector<SimpleStruct> vs;

我希望按“a”对该结构进行排序，而“b”和“c”的位置保持不变。 本质上是围绕

a

旋转，按

a

排序，然后取消旋转。 举个例子：

before: {1, 10, 11}, { 5, 100, 111}, {3, 1000, 1111}
after: {1, 10, 11}, {3, 100, 111}, {5, 1000, 1111} //'a' is now sorted, 'b' and 'c' relative position unchanged

如果我只关心正确性并希望最大程度地减少潜在错误的数量，那么使用标准库，显而易见的解决方案是创建第二个类型为 {value, index} 的集合，按值排序，然后覆盖对应索引。

这是极其低效的，因为从概念上讲，我们真正需要的是带有自定义比较和自定义交换的标准排序操作。

有没有一种方法可以使用标准库在 C++ 中执行此操作，而无需创建自定义排序方法？

首选 C++20，最好不使用范围。

Answer 1

这可以在 C++20 范围的帮助下轻松完成

std::vector<SimpleStruct> vs = {{1, 10, 11}, {5, 100, 111}, {3, 1000, 1111}};
std::ranges::sort(vs | std::views::transform(&SimpleStruct::a));
// vs now becoms {1, 10, 11}, {3, 100, 111}, {5, 1000, 1111}

演示

请注意，

ranges::sort(vs, {}, &SimpleStruct::a)

是不正确的，因为投影仅应用于比较，因此它仍然会对整个

SimpleStruct

对象而不是

SimpleStruct::a

进行排序。

Answer 2

正如评论所建议的，使用迭代器更加复杂，但通用的解决方案可能是：

#include <iostream>
#include <algorithm>

template <typename Iter, typename MemberRef>
struct MemberIter
{
  Iter i;
  MemberIter(Iter i, MemberRef): i(i) {}
  using iterator_category = std::random_access_iterator_tag;
  using difftype = std::ptrdiff_t;
  using value_type = std::remove_reference<decltype(MemberRef()(*i))>::type;
  value_type& operator*() { return MemberRef()(*i); }
  value_type* operator->() { return &(MemberRef()(*i)); }
  MemberIter& operator++() { ++i; return *this; }
  MemberIter operator++(int) { MemberIter tmp = *this; ++i; return tmp; }
  MemberIter& operator--() { --i; return *this; }
  MemberIter operator--(int) { MemberIter tmp = *this; --i; return tmp; }
  MemberIter& operator+=(difftype diff) { i += diff; return *this; }
  MemberIter& operator-=(difftype diff) { i -= diff; return *this; }
  difftype operator-(const MemberIter& other) const { return i - other.i; }
  MemberIter operator+(difftype diff) const { auto p = *this; p.i = i + diff; return p; }
  MemberIter operator-(difftype diff) const { auto p = *this; p.i = i - diff; return p; }
  bool operator==(const MemberIter& other) const { return i == other.i; }
  bool operator!=(const MemberIter& other) const { return i != other.i; }
  bool operator<(const MemberIter& other) const { return i < other.i; }
  bool operator>(const MemberIter& other) const { return i > other.i; }
  bool operator<=(const MemberIter& other) const { return i <= other.i; }
  bool operator>=(const MemberIter& other) const { return i >= other.i; }
  value_type& operator[] (difftype offset) const { return MemberRef()(*(i + offset)); }
};

struct SimpleStruct { int a; double b; char c; };

int main()
{
  SimpleStruct arr[10];
  for (int i = 0; i < 10; ++i) 
  {
    arr[i].a = rand() % int(1e6);
    arr[i].b = rand() / 1e6;
    arr[i].c = rand() % int(1e6);
  }
  
  for (int i = 0; i < 10; ++i)
    std::cout << arr[i].a << "  " << arr[i].b << "  " << int(arr[i].c) << "\n";
  
  auto mf = [](auto& x)->double& { return x.b; }; // Create a lambda that returns the reference to the class member of interest.
  auto begin = MemberIter(arr, mf), end = MemberIter(arr + 10, mf);
  
  std::sort(begin, end, [](auto b1, auto b2)->bool { return b1 < b2; });
  std::stable_sort(begin, end, [](auto b1, auto b2)->bool { return b1 > b2; });
  
  std::cout << "\n";
  for (int i = 0; i < 10; ++i)
    std::cout << arr[i].a << "  " << arr[i].b << "  " << int(arr[i].c) << "\n";
} 

演示：https://godbolt.org/z/hzedjaMsx

像这样的排序可能比将数据复制到新向量+排序+复制回来要慢，但当内存稀缺时，这种方法会很方便。