问题标签 [strict-weak-ordering]

因此，在使用自定义比较器对向量进行排序时，我在边缘情况下遇到了这种非常奇怪的行为。

运行此代码时，它不会停止，而是永远运行：

但是，当我将 更改为true时false，它可以完美运行。

更奇怪的是，当我减少0要排序的 's 的数量时，它也可以完美地工作。（它适用于 16 或更少0，当我再添加一个0使其成为 17 时，程序不会再次停止。（如果长度超过 16，g++ 会切换到另一种排序算法吗？）

为什么会这样？我是否遗漏了 C++sort()函数中的一些重要概念？

我想知道在 Python 中是否存在一种数据结构，可以为其引入自定义的内部排序策略。我知道OrderedDict等等，但他们没有明确提供我的要求。例如，OrderedDict只保证插入顺序。我真的很想在 C++ 中提供使用比较对象的东西：例如 instd::set<Type,Compare,Allocator>是Compare一个定义数据结构内部排序的参数。通常，或者可能总是，它是一个二元谓词，用于评估属于数据结构的一对元素。Python中有类似的东西吗？你知道任何解决方法吗？

以下课程是否会破坏严格弱排序（与常规相比std::less（因此忽略诸如 Nan 之类的边缘情况值））

There is a coding puzzle I have encountered on one of those sites (I don't recall if it was leetcode or something else) which goes as follows: Given a list of strings, return the lexicographically smallest concatenation that uses each of the strings once. The solution is, on a technical level, fairly simple. You compare 2 strings a and b by checking whether ab<ba (lexicographically), sort the list, concatenate everything.

Now for the actual question: Does this ordering have a name? I tried googling around but never found anything.

There is also a secondary aspect to this, which is: Is it somehow immediately obvious that this is even a strict weak ordering? I certainly didn't think it was. Here is the proof that I came up with to convince myself that it is one:

For any given string s let |s| be its length and let s^n be s repeated n times. If ab<ba then a^|b|b^|a|<b^|a|a^|b| (to see this just successively swap neighboring ab pairs to get a lexicographically increasing sequence that ends in b^|a|a^|b|). It follows that a^|b|<b^|a| because they have the same length. The same argument works for > and = so we have proven that ab<ba is actually equivalent to a^|b|<b^|a|, with the latter clearly defining a strict weak ordering.

首先，我试图搜索类似的问题，但我没有找到任何解释我的问题可能是什么的回应。

问题如下：给定一组坐标为 (x,y,z) 的 N 个节点，使用第 4 个值 F 尽可能快地对它们进行排序。

为此，我想将 astd::set与自定义比较器一起使用，因为它具有 O(log(N)) 复杂性。我知道我也可以尝试一个std::vector和一个调用std::sortonstd::vector但理论上是一个较慢的操作。

为什么这个？因为我不断地在集合中插入元素，更改 F值（这意味着我更改值并重新排序容器中的元素，我删除并重新插入它）并且我想取 F 值较小的元素（这是容器前面的元素）。

但是，让我们来解决这个std::set问题。

坐标定义了唯一性，遵循严格的弱排序规则，这意味着a和b被认为是同一个对象，如果

该问题与定义基于坐标的唯一性标准和基于 F 值的排序标准有关。我不希望集合存储具有相同坐标的两个元素，但我希望它允许存储具有不同坐标但 F 值相同的两个元素

比较器还应满足以下三个属性：

1. 反身性 x < x false
2. 不对称x < y true意味着y < x false
3. 传递x < y && y < z 性意味着x < z true

因此，知道了所有这些属性，我一直在使用以下示例实现：

一些定义

为了方便起见，这里我使用指针

类节点

这里操作符<<重载仅用于调试目的

比较器

我想一个问题可能是两个节点坐标不同但 F 值相同的情况

具体案例的完整示例

Ì在这个例子中，我使用上面的类来插入/查找/删除一些元素，但是它显示在输出中，它的行为不像预期的那样：

要使用 C++11 或更高版本编译它：g++ -o main main.cpp

输出：

**预期输出：** 对应于元素 n1、n5、n2、n3，从 F (n1) 较小的元素到 F (n3) 较大的元素排序。

我将不胜感激任何帮助或想法以及实施的替代方案。谢谢