起個名字真難 level
获赞
2730
粉丝
27
关注
67
看过 TA
693
杭州师范大学
2019
算法工程师
IP属地:北京
暂未填写个人简介
私信
关注
各位大佬好,今天面试时候问了我,cpp中vector在数组内存不够时会开辟新内存把原来内存中的数据复制到新内存中,这个复制的过程如何优化。我说了我的想法,就是把内存块像链表一样连接起来,不复制。但是面试官不满意,不知道大佬有什么解决方案呢?
BewareMyPower:同意1楼,我也估计是说移动语义,虽然这是C++11标准中已经优化过的东西,C++11也不算什么新东西了。和楼上说的存指针本质上是一样,但是可以直接在vector中优化。 对于vector这种,扩容时肯定要赋值原来的内容,这个开销无法避免。除非你自定义allocator,用内存池,感觉太复杂了,而且这真的有实际作用么? 移动语义对vector的优化在于存放复杂类型,在复制时会调用拷贝构造函数。比如这段代码(copy代表100个元素的拷贝) #include <iostream> #include <vector> using namespace std; struct Object { Object() { p = new int[100]; cout << "ctor" << endl; } ~Object() { if (p) { cout << "dtor" << endl; delete[] p; } } Object(const Object& rhs) { cout << "copy ctor" << endl; p = new int[100]; for (int i = 0; i < 100; i++) p[i] = rhs.p[i]; } int* p; }; int main() { vector<Object> v(2); cout << v.size() << " " << v.capacity() << endl; v.push_back(Object()); return 0; } 运行结果如下 # ./a.out ctor ctor 2 2 ctor copy ctor copy ctor copy ctor dtor dtor dtor dtor dtor dtor 可以发现在容量为2时插入新对象,需要把原来的2个对象拷贝过来,涉及到内部的2*100个int的拷贝,再把新对象的100个int拷贝过来。但这是没必要的,因为旧对象一共300个int全部都拷贝了一份,然后还把原来的给析构了。如果在C++11标准下,给Object加上移动构造函数(move代表1次指针的拷贝) Object(Object&& rhs) noexcept : p(rhs.p) { cout << "move ctor" << endl; rhs.p = nullptr; } 运行结果变成了 # ./a.out ctor ctor 2 2 ctor move ctor move ctor move ctor dtor dtor dtor 可以看到之前多出来的3次copy和dtor变成了3次move,也就是说避免深拷贝,而是仅仅拷贝指针,接管之前的资源。最后把push_back那句改成v.emplace_back(),结果如下 # ./a.out ctor ctor 2 2 ctor move ctor move ctor dtor dtor dtor 继续减少了1次move操作,不用临时构建对象。避免了不必要的复制,原来的数据不进行实际拷贝,只拷贝指向数据的所在地址即可。
0 点赞 评论 收藏
分享
关注他的用户也关注了:
牛客网
牛客企业服务