问题标签 [sortedcollection]

我使用SortedCollection 的这个实现。

用 查找项目索引的语法是'A'什么？
请注意，这'A'不是我选择的排序键。

这是一种失败的方法：

如何在 Cincom VisualWorks 中按两个标准对集合进行排序？

示例：我有一个包含人员的 OrderedCollection，并且想要一个新集合，首先按年龄对人员进行排序，然后如果年龄相同，则按姓名对人员进行排序。

希望你能听懂我的英文！谢谢..

我需要创建一个排序列表，一次添加一个项目。所以我决定使用LinkedList<T>，因为它在插入操作中很有效。但是在找到合适的位置时，似乎需要更长的时间。我正在使用线性搜索来获取位置。如果我使用二进制搜索来获取正确的位置ElementAt，它会提高性能吗？据此，它仍然是一个 O(n) 操作。你怎么看？如果是这样，有没有其他更好的数据结构来做这项工作？因为如果我使用不同的数据结构，当向中间插入一个新值时，我将不得不将该位置之后的所有数据移动一个位置，这显然是不希望的。

我遇到了这个问题，我需要有效地删除列表/数组中的最小元素。这将是相当微不足道的解决 - 一个堆就足够了。

但是，现在的问题是，当我删除最小的元素时，会导致数据结构中其他元素的变化，这可能会导致顺序发生变化。一个例子是这样的：

我有一个元素数组：

当我从数组中删除“1”时，“5”和“12”分别更改为“4”和“17”。

因此不维持排序。

但是，被删除的元素将具有指向所有将被更改的元素的指针，但不知道将更改多少元素以及更改多少。

所以我的问题是：

从数据结构中删除最小元素同时保持排序时，存储这些元素以最大化性能的最佳方法是什么？还是我应该让它不分类？

我当前的实现只是将它们未排序的存储在一个向量中，因此时间复杂度为 O(N^2)，O(N) 用于查找最小元素，以及 N 个删除。

我正在实现Bentley-Ottman 算法，该算法需要扫描线 (SL) 具有以下属性的数据结构：

• 维护一个排序的集合T，其中T是IComparable<T>，
• 元素的插入应该是O(log count)，并且应该返回元素是否已经插入，
• 删除元素应该是O(log count)，
• 对于给定的元素e（无论是否已经在集合中），我需要e在排序顺序旁边的集合的上一个和下一个元素。

SortedList<TKey, TValue>有一个O(count)at 插入和删除，因为它必须移动列表中的所有连续元素。但是，我可以索引它，因此O(1)一旦我知道e.

SortedDictionary<TKey, TValue>并且SortedSet<T>有O(log count)插入和删除，但我找不到任何给我下一个和前一个元素的迭代器。

是否有任何实现可以为我提供全部功能？

如果没有，实现它的最快方法是什么？LinkedList<T>不允许二分查找。List<T>仍然有O(count)插入/删除。我真的必须实现自己的平衡树吗？

我知道由于各种概念上的原因，Java 没有排序列表，但考虑到我需要一个类似于优先级队列但也允许我随机访问（可索引）的集合的情况，换句话说，我需要一个遵循特定顺序的列表。我宁愿不使用Collections.sort()

优选的操作约束：

检索 - O(1)（基于索引的随机访问）
搜索 - O(log n)
插入 - O(log n)
删除 - O(log n)

集合上的迭代器应该给我排序顺序中的所有元素（基于在Comparator数据结构实例化期间提供的预定义）

我更喜欢使用 Java 的内置库来实现这一点，但也可以随意建议外部库。

编辑： TreeSet 不会做，因为基于索引的访问很困难，使用包装器集合也不是我的最佳选择，因为删除意味着我需要从两个集合中删除。

EDIT2：我找不到indexable skip list这似乎有点相关的实现和/或文档，有人可以帮我找到它吗？也欢迎对所提出的数据结构提出任何意见或反对意见。

EDIT3：虽然这可能不是最完美的答案，但我想添加我编写的这段代码，以便任何有类似问题需要排序列表的人都可以在发现它有用时使用它。

检查错误（如果有的话），并提出改进建议（尤其是sortedSubList方法）

您好，我正在学习并且是 smalltalk 的新手，我正在尝试将我的 SortedCollection 打印到屏幕上尝试使用 keysAndValueDo 但我不确定它是如何完成的，如果有人能给我一个很好的一般示例

考虑以下代码：

我只在 Smalltalk 代码中看到过这种“方便”方法使用了几次，然后是 SortedCollection，没有直接的 Obj-C 等效项。什么是 Objective-C 等价物？

我正在开发这个程序，我必须编写一个使用双向链表实现的排序列表模板。SortedList.cpp 是给我的，其中包含测试床主体。我应该在 SortedList.h 文件中实现模板。

该模板有一个 Insert、Delete 和 Print 函数、一个默认构造函数和 Big 3。将 Print 函数的内容复制到您自己的模板中：

我确实写了 SortedList.h，但是当我将我的输出与正确的输出进行比较时，我发现它不匹配。

这是 SortedList.h：

我得到的输出：

这是我应该得到的正确输出：

谁能告诉我我做错了什么？

谢谢

我看到有些人推荐使用SortedContainers一些树结构，比如二叉树，就像这个reddit线程。SortedContainers的文档提到它比二叉树的典型实现更节省空间

话虽如此，我实际上并没有看到有人谈论如何使用它，如果有人对如何使用 Sortedcontainers 或 SortedCollection 模拟 BST 或类似的东西有参考，我将不胜感激