Vector是STL库中的一种数据结构,本质上而言,Vector是一种动态数组结构,何为动态数组?动态数组指的是,在内存上面是连续地址,但是在每次初始化数组的时候,都事先分配好一大块内存,然后再分配给数组元素。
Vector的时间复杂度和数组是一样的
Vector的增删改查的实现
增
实例代码:
vector<int> g_vec; g_vec.push_back(22); cout << g_vec[0] << endl; //时间复杂度 1
删
vector<int> g_vec; g_vec.push_back(22); cout << g_vec[0] << endl; //时间复杂度 1 g_vec.pop_back(); //删除
插入
vector<int> g_vec; g_vec.push_back(22); cout << g_vec[0] << endl; //时间复杂度 1 g_vec.pop_back(); //删除 cout << g_vec.size() << endl; g_vec.push_back(12); g_vec.push_back(23); //插入 vector <int>::iterator theIterator = g_vec.begin(); g_vec.insert(theIterator,1,33); for (int i = 0 ; i < g_vec.size();i++) { cout << g_vec[i] << endl; }
时间复杂度:
增:O(1)
删: O(1)
插入:O(n):因为插入后,后面的元素需要往后移
erase:O(n):同理