哪种方法是更快的向量(插入然后排序)或集合? [英] Which is approach is faster vector (inserted then sorted) or set?

问题描述

我有一个数字序列(未排序，没有重复)，目标是对它们进行排序.

I have sequence of numbers (unsorted, no duplicate) with the target to sort them.

方法一:插入向量.O(n)，使用排序算法和排序.O(nlogn)

Approach 1: insert into vector. O(n), use sort algo and sort. O(nlogn)

方法二:插入集合.o(nlogn)

Approach 2: insert into set. o(nlogn)

哪种方法会更快?

我觉得 set 会更快，因为 vector 中的每个插入都必须分配完整的数组元素并复制它然后删除它，这可能很昂贵.但我在网上读到了大部分地方向量都设置过了.

I feel set will be faster as every insertion in vector has to allocate complete array element and copy it an then delete it which may be expensive. But I read over web most of the place vector is over set.

谁能建议我在逻辑正确的情况下哪个更快?

Can anyone suggests me which one is faster with proper logic?

如果我们事先不知道元素的编号，哪个会更快设置或向量(因为元素的数量都是小而元素的数量是大的?注意:如果没有大元素集似乎是更好的选择，但它也适合小元素吗?不知道)

if we don't know the no of element in advance which one will be faster set or vector (for both no of element are smaall andd no of elementt is large? note: if no of element is large set is better option it seems but is it good for small also? dont know)

推荐答案

• 如果你事先知道有很多元素可以期待，你可以reserve() 向量中的空间以避免重新分配，使第一个选择非常有趣(快速插入，单一排序).

  • If you know in advance of many elements to expect, you can reserve() the space in your vector to avoid reallocations, making the first choice very interesting (fast insertions, single sort).

    如果您需要执行一次，请使用 std::vector<>.如果程序稍后会发生其他插入，std::set<> 可能更有趣.

    If you need to do it once, go for the std::vector<>. If other insertions will occur later in the program, the std::set<> might be more interesting.

    如果你事先不知道预期的大小，那么向量可能会发生重新分配，std::set<> 是一个不错的选择(更好的理论平均复杂度).

    If you don't know the expected size in advance, then reallocations may occur with the vector, and std::set<> is a good choice (better theoretical average complexity).

    O(n) + O(n * log(n)) 向量vs O(n * log(n)) 集合

    O(n) + O(n * log(n)) for the vector vs O(n * log(n)) for the set

  • 如果元素的数量非常少，您仍然可以保留一些空间(例如，如果您希望有 10 个元素，您可能会保留 100 个以确保安全)，并使用 std::vector

    无论如何，分析这两种解决方案始终是一个好习惯，实际结果将取决于(除其他外)输入的初始排序状态以及每个容器的实现质量.

    Anyway, profiling both solutions is always a good practice, the actual result will depend (among other things) of the initial sorting state of the input, and on the quality of your implementation for each container.

    注意:

    • 记住 std::set 有更大的内存占用，如果它对你很重要的话.
    • Remember that std::set has a bigger memory foot-print, if it matters for you.

    这篇关于哪种方法是更快的向量(插入然后排序)或集合?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！