如何按顺序将项目插入列表？

Question

我有一个DateTimeOffset对象列表，我想按顺序将新的对象插入到列表中。

List<DateTimeOffset> TimeList = ...
// determine the order before insert or add the new item

抱歉，我需要更新我的问题。

List<customizedClass> ItemList = ...
//customizedClass contains DateTimeOffset object and other strings, int, etc.

ItemList.Sort();    // this won't work until set data comparison with DateTimeOffset
ItemList.OrderBy(); // this won't work until set data comparison with DateTimeOffset

此外，如何将DateTimeOffset作为.OrderBy()的参数？

我还尝试过：

ItemList = from s in ItemList
           orderby s.PublishDate descending    // .PublishDate is type DateTime
           select s;

然而，它返回了以下错误信息：

“无法隐式转换类型'System.Linq.IOrderedEnumerable'为'System.Collections.Gerneric.List'。存在显式转换(是否缺少强制转换?)”

- Jerry

---

你能否在需要时对列表进行排序或使用SortedList？ - L.B

List<T>是一个有序的集合。您想要进行排序吗？ - KV Prajapati

你在这里指的是什么“顺序”？ - Daniel Hilgarth

我希望我的列表按照DateTimeOffset排序。 - Jerry

或者使用不同的集合类型，如 SortedBag<T>：在 .NET 中是否有排序集合类型？ - nawfal

Answer 1

假设你的列表已经按升序排序

var index = TimeList.BinarySearch(dateTimeOffset);
if (index < 0) index = ~index;
TimeList.Insert(index, dateTimeOffset);

- L.B

---

你能解释一下你的代码吗？如果他们不知道如何向列表中插入元素，我怀疑他们不会知道~index是什么意思。 - Ash Burlaczenko

@AshBurlaczenko，你说得对，但是问题的背景似乎在我回答后1小时发生了改变，而我太懒了。 - L.B

返回值 如果在已排序的 List<T> 中找到了 item，则返回item的零起始索引；否则，返回一个负数，这个负数是比 item 大的下一个元素的位补码索引或者（如果没有更大的元素）是 Count 的位补码。 - Black Horus

Answer 2

以下是针对边缘情况略有改进的@L.B.的答案：

public static class ListExt
{
    public static void AddSorted<T>(this List<T> @this, T item) where T: IComparable<T>
    {
        if (@this.Count == 0)
        {
            @this.Add(item);
            return;
        }
        if (@this[@this.Count-1].CompareTo(item) <= 0)
        {
            @this.Add(item);
            return;
        }
        if (@this[0].CompareTo(item) >= 0)
        {
            @this.Insert(0, item);
            return;
        }
        int index = @this.BinarySearch(item);
        if (index < 0) 
            index = ~index;
        @this.Insert(index, item);
    }
}

- noseratio

---

这段代码片段使我在一个情况下获得了1000%的性能提升，该情况下我无法使用SortedSet<>，而必须反复对List进行.Sort()操作。 - Nebu

@this 是什么？ - Baruch

@this是一个纯粹的约定变量名，通常用于引用由C#扩展方法扩展的对象。虽然@this是一个有效的C#变量名，但您可以使用其他任何名称，例如，在这里可能有意义的是list。 - noseratio - open to work

在this前面的@允许您将保留字用作参数/变量，这是为那些之前没有遇到过这种情况的人准备的。 - Glenn Watson

Answer 3

使用.NET 4，您可以使用新的SortedSet<T>，否则您将被限制在键值集合SortedList中。

SortedSet<DateTimeOffset> TimeList = new SortedSet<DateTimeOffset>();
// add DateTimeOffsets here, they will be sorted initially

注意： SortedSet<T> 类不接受重复元素。如果元素已经在集合中，此方法将返回 false 而不会抛出异常。

如果允许重复项，则可以使用 List<DateTimeOffset> 并使用其 Sort 方法。

- Tim Schmelter

Answer 4

修改你的LINQ，在结尾处添加ToList()：

ItemList = (from s in ItemList
            orderby s.PublishDate descending   
            select s).ToList();

或者将排序后的列表分配给另一个变量。

var sortedList = from s in ....

- Tommy Grovnes

Answer 5

我采用了@Noseratio的答案，并将其与这里的Jeppe的答案重新组合， 得到了一个适用于实现IList集合（我需要它用于Path的ObservableCollection）和不实现IComparable类型的函数。

    /// <summary>
    /// Inserts a new value into a sorted collection.
    /// </summary>
    /// <typeparam name="T">The type of collection values, where the type implements IComparable of itself</typeparam>
    /// <param name="collection">The source collection</param>
    /// <param name="item">The item being inserted</param>
    public static void InsertSorted<T>(this IList<T> collection, T item)
        where T : IComparable<T>
    {
        InsertSorted(collection, item, Comparer<T>.Create((x, y) => x.CompareTo(y)));
    }

    /// <summary>
    /// Inserts a new value into a sorted collection.
    /// </summary>
    /// <typeparam name="T">The type of collection values</typeparam>
    /// <param name="collection">The source collection</param>
    /// <param name="item">The item being inserted</param>
    /// <param name="comparerFunction">An IComparer to comparer T values, e.g. Comparer&lt;T&gt;.Create((x, y) =&gt; (x.Property &lt; y.Property) ? -1 : (x.Property &gt; y.Property) ? 1 : 0)</param>
    public static void InsertSorted<T>(this IList<T> collection, T item, IComparer<T> comparerFunction)
    {
        if (collection.Count == 0)
        {
            // Simple add
            collection.Add(item);
        }
        else if (comparerFunction.Compare(item, collection[collection.Count - 1]) >= 0)
        {
            // Add to the end as the item being added is greater than the last item by comparison.
            collection.Add(item);
        }
        else if (comparerFunction.Compare(item, collection[0]) <= 0)
        {
            // Add to the front as the item being added is less than the first item by comparison.
            collection.Insert(0, item);
        }
        else
        {
            // Otherwise, search for the place to insert.
            int index = 0;
            if (collection is List<T> list)
            {
                index = list.BinarySearch(item, comparerFunction);
            }
            else if (collection is T[] arr)
            {
                index = Array.BinarySearch(arr, item, comparerFunction);
            }
            else
            {
                for (int i = 0; i < collection.Count; i++)
                {
                    if (comparerFunction.Compare(collection[i], item) <= 0)
                    {
                        // If the item is the same or before, then the insertion point is here.
                        index = i;
                        break;
                    }

                    // Otherwise loop. We're already tested the last element for greater than count.
                }
            }

            if (index < 0)
            {
                // The zero-based index of item if item is found,
                // otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count.
                index = ~index;
            }

            collection.Insert(index, item);
        }
    }

- Slate

---

collection.ToArray() will create another collection which is more costlier than the linear search i.e. collection.IndexOf() - zafar

我在结尾处进行了新的处理--集合遗憾地没有二分搜索，但是...嗯。 - Slate

Answer 6

我很好奇对这里提出的两个建议进行基准测试，使用SortedSet类和基于列表的二分搜索插入。从我的（非科学的）结果在.NET Core 3.1上来看，似乎对于小型(低几百)集合，List可能使用更少的内存，但是随着集合变大，SortedSet在时间和内存方面开始获胜。

（项是具有两个字段Guid id和string name的小类实例）

50个项：

|        Method |     Mean |     Error |    StdDev |  Gen 0 | Gen 1 | Gen 2 | Allocated |
|-------------- |---------:|----------:|----------:|-------:|------:|------:|----------:|
|     SortedSet | 5.617 μs | 0.0183 μs | 0.0153 μs | 0.3052 |     - |     - |    1.9 KB |
| SortedAddList | 5.634 μs | 0.0144 μs | 0.0135 μs | 0.1755 |     - |     - |   1.12 KB |

200个项目：

|        Method |     Mean |    Error |   StdDev |  Gen 0 | Gen 1 | Gen 2 | Allocated |
|-------------- |---------:|---------:|---------:|-------:|------:|------:|----------:|
|     SortedSet | 24.15 μs | 0.066 μs | 0.055 μs | 0.6409 |     - |     - |   4.11 KB |
| SortedAddList | 28.14 μs | 0.060 μs | 0.053 μs | 0.6714 |     - |     - |   4.16 KB |

1000个项目：

|        Method |     Mean |   Error |  StdDev |  Gen 0 | Gen 1 | Gen 2 | Allocated |
|-------------- |---------:|--------:|--------:|-------:|------:|------:|----------:|
|     SortedSet | 107.5 μs | 0.34 μs | 0.30 μs | 0.7324 |     - |     - |   4.73 KB |
| SortedAddList | 169.1 μs | 0.41 μs | 0.39 μs | 2.4414 |     - |     - |  16.21 KB |

- Noah Stahl

Answer 7

插入特定索引的项目

您可以使用以下方法：

DateTimeOffset dto;

 // Current time
 dto = DateTimeOffset.Now;

//This will insert the item at first position
TimeList.Insert(0,dto);

//This will insert the item at last position
TimeList.Add(dto);

你可以使用 LINQ 来排序集合：

//This will sort the collection in ascending order
List<DateTimeOffset> SortedCollection=from dt in TimeList select dt order by dt;

- techfun

---

为什么不使用扩展方法.OrderBy()进行排序呢？ - Ash Burlaczenko

是的，Ash Burlaczenko，我们也可以这样做。我习惯于在LINQ中编写大查询。这就是为什么我写了上面的查询，那是我脑海中浮现的第一个想法。但我同意你的看法。谢谢。 - techfun

List<T>.Add方法没有重载接受索引参数的版本。我认为你想使用List<T>.Insert方法。 - Daniel Hilgarth

是的，Daniel hilgarth，我的意思是Insert(Index,object)方法。谢谢。 - techfun

将项目首先插入或添加到列表中，然后对列表进行排序是最好的方法吗？还是第一次将项目插入正确的位置更好？ - Jerry

好问题，杰瑞。我不确定最好的方法。我认为这将取决于我们在集合中拥有的数据和我们插入的日期。但是是的，BinarySearch非常高效，您可以使用它或SortedSet集合。 - techfun

Answer 8

非常简单，将数据添加到列表后

list.OrderBy(a => a.ColumnName).ToList();

- peeyush singh

Answer 9

你可以先找到想要的索引，然后使用 Insert(index, object)。

- levi

---

告诉我编写更多的排序顺序。 - levi