按照它们的常量ID排序自定义类型的向量

Question

我需要对自定义类型为std::vector<Blah> v的向量按照Blah的整数id进行排序。我通过使用在Blah中重载了运算符<的方式来实现： std::sort(v.begin(), v.end())

bool operator< (const Blah& b) const { return (id < b.id); }

我发现Blah的私有id不能声明为const int id，否则类型Blah不符合std::sort的要求（我认为这与不可交换值有冲突）。

如果id不是const，一切都很好。然而，我不喜欢对象没有常量id仅仅是为了在向量中重新排列它们的顺序的要求而不同。

有没有办法绕过这个问题，还是这就是现状？

- symphonic

---

是的，实际上 id 需要是唯一的。 - symphonic

我猜测你想根据ID进行排序，以便可以通过ID访问元素。为此，使用映射可能更合适。 - Daniel Jour

@RichardForrest，你不能交换一个具有const成员的对象。 - Quentin

@IorisN：地图是极其有用的数据结构。虽然排序向量有时（经常？）更快，但在真正需要性能之前，请使用地图，因为地图更加方便。 - Erik Alapää

是的，你可能可以在谷歌上找到一些关于STL向量和性能的好文章 - 其中一个原因是数组/向量具有良好的缓存局部性，这有时会极大地提高性能。但是映射表也可以非常适合性能 - 例如，它们永远不需要像哈希表那样重新散列，因此性能始终是对数级别的100％。 - Erik Alapää

Answer 1

这是唯一的方法吗？还是有别的方法？

恐怕这是唯一的方法。如果您想要对向量进行排序，也就是原则上的一个数组，那么当交换它们时，您必须为元素 分配 值。

至少我是这样认为的，实际上您可以有一些小技巧。将您的对象包装成一个联合体：

template<typename T>
union ac {
 // actual object
 T thing;
 // assignment first destructs object, then copy
 // constructs a new inplace.
 ac & operator=(ac<T> const & other) {
  thing. ~T();
  new (& thing) T(other. thing);
 }
 // need to provide constructor, destructor, etc.
 ac(T && t) : thing (std:: forward<T>(t))
 {}
 ac(ac<T> const & other) : thing (other. thing) {}
 ~ac() {
  thing. ~T();
 }
 // if you need them, add move assignment and constructor
};

您可以实现（复制）赋值运算符，首先销毁当前对象，然后从提供的旧对象中（复制）构造一个新对象。您还需要提供构造函数和析构函数，当然，由于早期语言标准中对联合成员的限制，这仅适用于C++11及以上版本。这似乎非常好用：Live demo. 但我认为您应该先重新审查一些设计选择，例如，如果常量id真的需要成为您对象的一部分。

- Daniel Jour

---

这是一个有趣的结构。谢谢分享。虽然我不打算使用它，但我接受你的答案，因为它确实回答了我的问题。 - symphonic

Answer 2

这是唯一的方法吗？还是有其他方法可以解决这个问题？

所以你想要更新/交换对象的整个数据（包括其标识），并保持标识不变；这两者是相互冲突的，因为常量意味着“不改变”（而交换意味着“更改这些实例”）。

你在这里遇到了两种（竞争的）const-ness定义：概念上的const-ness（数据所说/表示的含义相同）和二进制const-ness（表示数据的字节不会改变）。 （第一个定义是引入语言中mutable的原因：在打破二进制const-ness的同时保持概念上的const-ness的能力）。

你的数据在概念上是恒定的（数据的接口应该是const），但不是二进制恒定的（你可以交换值，因此你的位可能会消失到另一个实例）。

这个问题的规范思路是在内部保持数据非const，并为客户端代码提供只读的公共/受保护访问。

你说：

“然而，我不喜欢对象没有恒定的id，只是为了重新排列它们在向量中的顺序。”

仅仅因为身份在概念上是恒定的（暴露的API是/应该是恒定的），你没有实际强制要求保持数据的恒定性（并且基于API也不应有偏好）。

- utnapistim