哪種更好的方法來排序不同的數字？

Question

在C++中使用STL其中兩個操作花費更少的CPU時間來大量不同數字進行排序：

• 推元件成一組
• 存放在向量中的元素和調用sort（）函數？

Answer 1

如果是一次性操作，我會使用std::vector後跟std::sort。這個解決方案應該是等價的：一個集合中的插入是O（log（n）），並且你爲N個元素這麼做，所以它是O（N log（N）） （proof）。另一方面，插入一個向量（假設你事先知道大小）是O（N），排序是O（N log（N）），所以在全局上它是O（N log（N） ））。 （或者，如果您不知道最終大小，它應該在典型實現的O（log（N））重新分配中達到確定的大小）;但是，如果您不知道最終大小，另一方面，一個集合（如果實現爲RB樹）需要爲每個節點分配，這意味着您必須調用分配器N次 - 並且POD容器中的分配器調用可能會是瓶頸。此外，樹通常具有較少的緩存局部性和使用更多的內存，所以所有這些開銷可能會損害性能。另外，big-O符號表示函數時間依賴性，但隱藏乘法常量;不要拿我的話來說，但是我幾乎可以肯定，由於每個元素需要額外的簿記工作，所以N *集合插入將在最後花費更多的成本（樹插入通常需要一些努力恢復RB樹屬性）。

---

在另一方面，如果你要保持排序你的數據結構（由新數據來）設定通常是正確的解決方案。

---

但是，一如既往，有疑問時輪廓。