为什么从向量构建一个集合是 O(N)

Question

众所周知，set 是使用红黑树实现的，因此插入一个元素将是 O(log N) 复杂度的任务。但是，如果给定一个包含 n 个不同整数的向量，那么应该通过 NlogN 任务从中创建一个集合。但是在很多地方，我发现它是作为 O(N) 给出的。有人可以帮我解决这个问题吗？提前致谢。

Link 到我读这篇文章的地方 Complexity of building a set from list?

Answer 1

如果向量已经排序，那么构造set确实是O(N)（但一般不是！）。

来自cppreference：

template< class InputIt >    
set( InputIt first, InputIt last,
     const Compare& comp = Compare(),
     const Allocator& alloc = Allocator() );

Range constructor. Constructs the container with the contents of the range [first, last). If multiple elements in the range have keys that compare equivalent, it is unspecified which element is inserted

Complexity

N log(N) where N = std::distance(first, last) in general, linear in N if the range is already sorted by value_comp().

标准中的相关引用是：

22.4.6.2#4 Complexity: Linear in N if the range [first, last) is already sorted using comp and otherwise NlogN, where N is last - first.

该标准仅规定了容器的作用，而不是它们如何完成的。使用红黑树是典型的，但不是实现 std::set.

所必需的

为什么从向量构建一个集合是 O(N)

why building a set from vector is O(N)

c++

vector

set

time-complexity

insertion