std:sort与插入std :: set [英] std:sort vs inserting into an std::set

问题描述

我正在阅读cin的一些线段.每个线段均由起点和终点表示. 2D. X和Y.

I am reading some line segments from cin. Each line segment is represented by a start and end point. 2D. X and Y.

输入未排序.它是随机顺序的. (更新:但是我需要它们先按X，然后按Y排序)

The input is not sorted. It is in random order. (Update:But I need them sorted first by X and then by Y)

我可以读取所有段，将它们存储在向量中，然后调用std :: sort.另一方面，我可以创建一个空的std :: set并在每个段到达时插入它们.该集将自动维护排序顺序.两种方法中哪种更有效?

I can read in all the segments, store them in a vector and then call std::sort. On the other hand, I can create an empty std::set and insert each segment as it arrives. The set will automatically maintain sorted order. Which of the two approaches is more efficient?

更新:预先知道输入的总大小(段数).

Update: The total size of the input (number of segments) is known in advance.

推荐答案

您应该测量两种方法的性能，以确保安全，但是可以肯定地假设std::vector上的std::sort是 way 比插入std::set更快，这是由于局部效果和树插入算法中隐藏的大常量所致.而且，后续的查找和迭代将更快.

You should measure the performance of both approaches to be sure, but it's a safe bet to assume that std::sort on an std::vector is way faster than inserting into an std::set due to locality effects and the large constants hiding in the tree insertion algorithm. Also, the subsequent lookups and iteration will be faster.

(但是，std::set更适合支持一系列插入和删除/查找/迭代混合.保持向量中的顺序很昂贵，因为每个插入平均需要花费线性时间.)

(However, std::set is better suited for supporting a mixed series of insertions and deletions/lookups/iterations. Maintaining order in vector is expensive, as each insertion will take linear time on average.)

这篇关于std:sort与插入std :: set的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！