向量

向量(Vector)是类似于动态数组的容器,当插入或删除新元素时,可以调整其大小。它是标准模板库或STL的模板,为程序提供了更大的灵活性。vector的元素被放置在连续存储中,并使用迭代器遍历。

例子:

vector  v;
v.push_back(1);
v.push_back(2);
v.clear();

下面是c++中向量的实现:

#include 
using namespace std;

// Driver Code
int main()
{
    vector v;

    // Inserting elements in vector
    v.push_back(211);
    v.push_back(26);
    v.push_back(212);
    v.push_back(20);
    v.push_back(10);

    cout << "Elements in vector are:";
    for (auto it : v) {
        cout << it << " ";
    }

    return 0;
}

运行结果如下:

Elements in vector are:
211 26 212 20 10

时间复杂度 O(N) // 对于N次插入而言
辅助空间 O(1)

Set

集合(Set)也是标准模板库或STL的模板之一。它是一个独特元素的容器,这些元素的值一旦添加到集合中就不能被修改,但可以被删除或插入。集合的元素总是以排序的形式存储。

例子

set  s;
s.insert(1);
s.insert(12);
int key = 1;
s.erase(key);

下面是C++中集合的实现 –

#include 
using namespace std;

// Driver Code
int main()
{
    set s;

    // Insert elements into the set
    s.insert(211);
    s.insert(26);
    s.insert(212);
    s.insert(20);

    // Duplicate elements
    s.insert(0);

    cout << "Elements in set: ";

    // The inserted elements get sorted 
    for (auto it : s) {
        cout << it << " ";
    }

    return 0;
}

运行结果:

Elements in set:
20 26 211 212

时间复杂度。O(Nlog N) // 对于N次插入而言
辅助空间。O(1)

向量和集合之间的表格差异。

向量 集合
向量的元素是不排序的。 集合的元素总是被排序的。
向量可以包含重复的元素。 集合只包含唯一的元素。
向量是无序的。 集合是有序的。
插入一个新元素的时间复杂度是O(1)。 插入一个新元素的时间复杂度是O(log N)。
Vector对于插入和删除容器末端的元素更快。 Set对于插入和删除容器中间的元素比较快。