C++ std set 和std vector 的区别
向量
向量(Vector)是类似于动态数组的容器,当插入或删除新元素时,可以调整其大小。它是标准模板库或STL的模板,为程序提供了更大的灵活性。 vector
的元素被放置在连续存储中,并使用迭代器遍历。
例子:
下面是c++中向量的实现:
运行结果如下:
时间复杂度 O(N) // 对于N次插入而言
辅助空间 O(1)
Set
集合(Set)也是标准模板库或STL的模板之一。它是一个独特元素的容器,这些元素的值一旦添加到集合中就不能被修改,但可以被删除或插入。集合的元素总是以排序的形式存储。
例子
下面是C++中集合的实现 –
运行结果:
时间复杂度。O(Nlog N) // 对于N次插入而言
辅助空间。O(1)
向量和集合之间的表格差异。
向量 | 集合 |
---|---|
向量的元素是不排序的。 | 集合的元素总是被排序的。 |
向量可以包含重复的元素。 | 集合只包含唯一的元素。 |
向量是无序的。 | 集合是有序的。 |
插入一个新元素的时间复杂度是O(1)。 | 插入一个新元素的时间复杂度是O(log N)。 |
Vector对于插入和删除容器末端的元素更快。 | Set对于插入和删除容器中间的元素比较快。 |