vector类的功能实现 | 夕阳余晖 如你的羞怯似醉
Cobb 611 0

vector的实现

vector 扩容策略

知识储备

名字:向量容器 底层数据结构:内存可扩容的数组 扩容方式:vs下1.5倍方式扩容, g++下按2倍扩容,
验证方式: 不同平台下输入一个数据,就打印一下容量capacity

使用场景:(因为vector底层是数组,所以场景是数组的使用场景) 1.只在末尾进行元素增加和删除 O(1) 2.下标访问(随机访问)多 O(1) operator[]

增加:push_back(val)尾部添加 O(1) 常量时间 insert(interator, val);

删除:pop_back()尾部删除 O(1) , 非末尾元素不适合用:因为数组内存空间连续 ,删除/增加 之后数据要大量移位。erase(interator); 修改:vec[i] = 10 []只能用作访问和修改,不能用作添加元素

查询: for (int i=0; i<vec.size(); i++) { if (vec[i] == 50) { xxx } }

清除:clear(); clear做的事情:把底层数组中对象全部析构,不用释放内存。 重置 size: 0 v.front() 访问首元素 v.back() 访问末尾元素 下标访问(随机访问)多 O(1)

为什么不在链表容器中进行 operator[] : 关键字 - 空间连续 - 指针偏移 - 底层实现方式 数组中指针相减 : 表示 两指针的距离

注意: 1.默认构造的vector,初始空间为0,插入元素时,以0-1-2-4-8-16。。。的方式进行扩容,刚开始空间小,需不断的申请空间,拷贝 所以内存的初始使用效率不高 ==================》 reserve 预留空间,可以提高初始内存使用效率,避免了频繁扩容

2.resize什么作用? 和reserve的区别 resize和reserve都有预留内存空间的功能,但是reserve不会添加新元素,而resize会给预留的内存空间上放满元素 reserve 就是扩容。。。。。() v.reserve(1000); v.size(); 0 v.capacity(); 1000 v.resize(1000); v.size(); 1000 v.capacity(); 1000




unordered_map表中查询出现次数


// unordered_map表中查询出现次数
int main()
{
    vector<int> v;
    srand(time(0));
    for (int i = 0; i < 100; i++)
    {
        v.push_back(rand() % 20);
    }

    // 统计vector中所有元素以及它出现的次数信息,并打印成:  数字xxx   重复次数xxx
    // key:数字   value:该数字重复的次数  O(1)
    unordered_map<int, int> m;

    // 遍历所有的数字,先从map表查,有的话直接给次数+1;没有的话,插入[数字,1]
    for (int i = 0; i < v.size(); i++)
    {
        /*auto it = m.find(v[i]);
        if (it == m.end())
        {
            m.emplace(v[i], 1);
        }
        else
        {
            it->second++;
        }*/
        // v[i] 存在, m[v[i]]=》value
        // v[i] 不存在, m[v[i]]  [v[i], 0] 
        m[v[i]]++;
    }

    // d pair
    for (auto& d : m)
    {
        cout << d.first << " => " << d.second << endl;
    }
}

#if 0
int main()
{
    // 底层vec_=nullptr,目前没有开辟过任何空间
    vector<int> v1;
    v1.reserve(100); // 给vector底层预分配100个空间
    //v1.resize(100);
    cout << v1.size() << endl;
    cout << v1.capacity() << endl;

    // O(1)  0 -> 1
    v1.push_back(20);
    // 1->2
    v1.push_back(30);
    // 2->4
    v1.push_back(40);
    v1.push_back(50);
    // 4->8
    v1.push_back(24);

    // size() 返回容器的元素个数
    for (int i = 0; i < v1.size(); i++)
    {
        // v1.operator[](i)
        cout << v1[i] << " ";
    }
    cout << endl;

    v1.pop_back();
    v1.pop_back();

    for (int i = 0; i < v1.size(); i++)
    {
        // v1.operator[](i)
        cout << v1[i] << " ";
    }
    cout << endl;

    v1.clear();

    for (int i = 0; i < v1.size(); i++)
    {
        // v1.operator[](i)
        cout << v1[i] << " ";
    }
    cout << endl;
}
#endif
评论区