重庆御临建筑公司官网,wordpress 4.9优化,怎么看得出网站是哪个公司做的,凡科网登录手机端vector
介绍 vector#xff08;向量#xff09;是一种序列容器#xff0c;表示为可以改变大小的数组。vector中的元素使用连续的存储位置#xff0c;这意味着也可以使用指向其元素的常规指针偏移量来访问任意元素#xff0c;且与数组一样高效。但与数组不同的是#xff…vector
介绍 vector向量是一种序列容器表示为可以改变大小的数组。vector中的元素使用连续的存储位置这意味着也可以使用指向其元素的常规指针偏移量来访问任意元素且与数组一样高效。但与数组不同的是vector的大小可以动态变化容器会自动处理他们的存储空间。在其内部vector使用动态分配的数组来存储他们的元素。当插入新元素需要增大容量时存储空间需要重新分配这意味着需要分配一个新数组并将所有元素移动到其中。就处理时间而言这是一个相对昂贵的任务因此vector不会在每次想容器中添加元素时都重新分配。相反vector容器可以分配一些额外的存储空间以适应可能的增长因此容器的实际容量肯呢个大于包含其元素严格所需的存储空间。因此与数组相比向量消耗更多的内存以换取更有效的方式管理存储和动态增长的能力。与其他动态序列容器deque、列表、前向列表相比vector可以非常高效地访问其元素并且可以相对高效地从其末端添加或删除元素。对于涉及在末尾以外的位置插入或删除元素的操作他们的性能比其他操作差并且迭代器引用的一致性不如列表和前向列表。 以上是官方对于vector的介绍从上面我们能够了解到vector本质上就是一种可动态增长的顺序表其特性与数据结构中学习的顺序表相差无几但vector的出现极大地简化了我们使用顺序表的工作量且vector与其他容器有着较深的联系因此学好vector有利于我们未来的学习。 vector的使用 对于vector在学习时我们一定要学会查看文档vector文档vector在实际中非常重要我们要熟悉常见的接口以应对未来的使用。
(constructor)构造函数
函数声明接口说明vector();无参构造vector(size_t n, const T val T());构造并初始化n个valvector(const vector x);拷贝构造vector(inputiterator first, inputiterator last);使用迭代器进行区间初始化构造
代码演示 //构造5个int的空间vectorint v1(5);//构造10个int空间并初始化为1vectorint v2(10, 1);//去掉v2的第一个和最后一个空间使用剩余空间构造并用相同数值初始化vectorint v3(v2.begin(), --v2.end());//拷贝构造vectorint v4 v3;
iterator迭代器的使用
函数名称接口说明beginend获取第一个数据位置的iterator/const_iterator获取最后一个数据的下一个位置的iterator/const_iterator.rbeginrend获取最后一个数据位置的reverse_iterator获取第一个数据前一个位置的reverse_iterator 代码演示
vectorint v(10, 1);
// []下标形式
for (size_t i 0; i v.size(); i)
{cout v[i] ;
}
cout endl;//迭代器
vectorint::iterator it v.begin();
while (it ! v.end())
{cout *it ;it;
}
cout endl;//反向迭代器
vectorint::reverse_iterator rit v.rbegin();
while(rit ! v.rend())
{cout *rit ;rit;
}
cout endl;//范围for
for (auto e : v)
{cout e ;
}
cout endl;
空间管理函数
函数名称接口说明size 获取数据个数 capacity获取容量大小empty判断是否为空resize改变vector的_sizereserve改变vector的capacity
注意
capacity函数在vs和g下的扩容机制略有不同vs下capacity是按1.5倍增长的g下是按2倍增长的。在面试中经常会考察这个问题不要固化地认为vector的扩容都是2倍具体增长多少是根据具体的需求来定义的。vs是PJ版本STLg是SGI版本STL。reserve函数只负责开空间如果明确知道需要开多少空间reserve就可以一次性开好缓解了多次扩容的代价。resize在开空间的同时还会进行初始化影响_size。
扩容机制测试代码
// 测试vector的默认扩容机制
void TestVectorExpand()
{size_t sz;vectorint v;sz v.capacity();cout making v grow:\n;for (int i 0; i 100; i){v.push_back(i);if (sz ! v.capacity()){sz v.capacity();cout capacity changed: sz \n;}}
} 内存管理函数代码演示 //reservevectorint v(10, 1);cout size: v.size() capacity: v.capacity() endl;v.reserve(20);cout size: v.size() capacity: v.capacity() endl;v.reserve(15);cout size: v.size() capacity: v.capacity() endl;v.reserve(5);cout size: v.size() capacity: v.capacity() endl;//resizevectorint v(10, 1);cout size: v.size() capacity: v.capacity() endl;for (auto e : v){cout e ;}cout endl;v.resize(15,2);cout size: v.size() capacity: v.capacity() endl;for (auto e : v){cout e ;}cout endl;v.resize(25, 3);cout size: v.size() capacity: v.capacity() endl;for (auto e : v){cout e ;}cout endl;v.resize(5);cout size: v.size() capacity: v.capacity() endl;for (auto e : v){cout e ;}cout endl;
增删查改
函数名称接口说明push_back尾插pop_back尾删find查找不是vector的成员接口insert在pos之前插入valerase 删除pos位置的数据 swap交换两个vector对象的数据空间operator[]像数组一样访问
代码演示
vectorint v(5, 1);
for (auto e : v)
{cout e ;
}
cout endl;
//尾删
v.pop_back();
for (auto e : v)
{cout e ;
}
cout endl;
//尾插
v.push_back(5);
for (auto e : v)
{cout e ;
}
cout endl;
//pos位置之前插入
v.insert(v.begin(), 4);
for (auto e : v)
{cout e ;
}
cout endl;
//寻找第一个为1数据的位置
vectorint::iterator pos find(v.begin(),v.end(),1);
//删除pos位置的数据
v.erase(pos);
for (auto e : v)
{cout e ;
}
cout endl;
// operator[]的调用
v[2] 9;
for (auto e : v)
{cout e ;
}
cout endl;
//swap交换函数
vectorint v1(5, 2);
swap(v, v1);
for (auto e : v)
{cout e ;
}
cout endl;
vectorvectorint vectorvectorint是C中的动态二维数组结构是一个vector的集合其中每个元素都是一个vectorint用于存储整数。对比c语言中的二维数组两者的存储方式与索引访问方法是一样的不同指出在于1、vector的动态性(vectorvectorint可以动态调整大小支持在运行时添加或删除行)而二维数组的大小需要在编译时固定。2、内存管理方面vector会自动管理内存避免了内存泄漏而二维数组需要手动管理(特别是在动态分配内存时)。3、便利性vector中提供了许多遍历的成员函数(如size()、push_back()等)使用更加灵活。
例题 给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。在「杨辉三角」中每个数是它左上方和右上方的数的和。 C的vector写法
class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorint vv(numRows);for(size_t i 0; i vv.size(); i){vv[i].resize(i1,1);}for(size_t i 2; i vv.size(); i){for(size_t j 1; j vv[i].size()-1; j){vv[i][j] vv[i-1][j] vv[i-1][j-1];}}return vv;}
}; 在使用vectorvectorint做这道题时我们可以发现每一列的数组是动态开辟的这样极大的简化了代码量且在遍历访问数组赋值时由于resize初始化可以给1我们在下面的遍历赋值中可以省去第一二行和每一行的首尾的赋值操作。
vector底层的模拟实现
框架
templateclass T
class vector
{
public:private:iterator _start nullptr;iterator _finish nullptr;iterator _end_of_storage nullptr;
};
默认成员函数的实现
//构造
/*vector()
{}*/
vector() default; // C11 强制生成默认构造
vector(size_t n, const T val T())
{reserve(n);for (size_t i 0; i n; i){push_back(val);}
}
vector(int n, const T val T())
{ //解决传单个整形参数不匹配问题reserve(n);for (size_t i 0; i n; i){push_back(val);}
}
templateclass InputIterator
vector(InputIterator first, InputIterator last)
{while (first ! last){push_back(*first);first;}
}
//拷贝构造
vector(const vectorT v)
{reserve(v.size());for (auto e : v){push_back(e);}
}
//swap
void swap(vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}
//赋值运算符重载
vectorT operator(vectorT tmp)
{swap(tmp);return *this;
}
//析构函数
~vector()
{delete[] _start;_start _finish _end_of_storage nullptr;
} 上面的代码中实现了一个简单的 vector 类的构造函数、拷贝构造、析构函数和一些成员函数。
无参默认构造函数使用 C11 的特性生成一个默认构造函数。这里也可以写一个空的默认构造函数我们只要在变量声明时给了缺省值就无需再给默认值初始化。带参默认构造函数vector(size_t n, const T val T()) 和 vector(int n, const T val T())这两个构造函数用于创建一个包含 n 个元素、初始值为 val 的 vector。使用 reserve(n) 预留空间随后通过 push_back(val) 向 vector 中添加元素。迭代器区间构造函数接受两个迭代器复制 [first, last) 范围内的元素到 vector 中。拷贝构造函数通过 reserve 分配足够的空间然后逐个使用 push_back 复制原 vector 的元素。交换函数通过交换内部指针 _start、_finish 和 _end_of_storage 实现高效的资源交换。赋值运算符重载使用拷贝并交换的技术实现赋值运算符避免多次资源管理确保安全性和效率。析构函数清理分配的内存将指针置为空防止悬挂指针。
迭代器的实现
//迭代器
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
} 上面的代码实现了一个简单的迭代器接口允许用户遍历 vector 中的元素。
iterator 和 const_iterator 分别定义了指向元素的普通指针和常量指针类型即普通迭代器和const迭代器。begin() 返回指向 vector 第一个元素的迭代器_start。end() 返回指向 vector 最后一个元素后一个位置的迭代器_finish用于表示迭代的结束。常量版本的 begin() 和 end() 允许在 const 对象上使用迭代器保证不会修改 vector 中的元素。
空间管理函数
//empty
bool empty()
{if (_start _finish)return true;elsereturn false;
}// size和capacity
size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _end_of_storage - _start;
}
// reserve
void reserve(size_t n)
{if (n capacity()){size_t old_size size();T* tmp new T[n];//memcpy(tmp, _start, old_size * sizeof(T));for (size_t i 0; i old_size; i){tmp[i] _start[i];}delete[] _start;_start tmp;_finish _start old_size;_end_of_storage _start n;}
}
//resize
void resize(size_t n, T val T())
{if (n _finish){_finish _start n;}else{reserve(n);while (_finish _start n){*_finish val;_finish;}}
} 上面代码实现了一些常用的 vector 成员函数包括检查是否为空、获取大小和容量、以及调整容量和大小的功能。
empty检查 vector 是否为空判断 begin() 和 end() 是否相同。如果相同返回 true表示没有元素否则返回 false。size() 返回当前 vector 中元素的数量_finish 与 _start 的差。capacity(): 返回当前分配的空间大小_end_of_storage 与 _start 的差表示在不重新分配内存的情况下最多能容纳多少元素。 reserve(n)用于调整 vector 的容量如果 n 大于当前容量重新分配内存并复制原有元素到新内存中释放旧内存。这里需要注意如果对象中涉及到资源管理时千万不能使用memcpy进行对象之间的拷贝因为memcpy是浅拷贝否则可能会引起内存泄漏甚至程序崩溃。resize(n, val): 调整 vector 的大小如果新大小 n 小于当前大小更新 _finish如果 n 大于当前大小首先调用 reserve(n) 确保有足够的容量然后在新增加的元素位置填充 val。
增删查改
//尾插
void push_back(const T x)
{if (_finish _end_of_storage){reserve(capacity() 0 ? 4 : 2 * capacity());}*_finish x;_finish;
}
//尾删
void pop_back()
{if (!empty());--_finish;
}
//insert
void insert(iterator pos, const T x)
{assert(pos _start);assert(pos _finish);//扩容if (_finish _end_of_storage){//解决迭代器失效的问题size_t len pos - _start;reserve(capacity() 0 ? 4 : 2 * capacity());pos _start len;}iterator end _finish - 1;while (end pos){*(end 1) *end;end--;}*pos x;_finish;
}
//erase
void erase(iterator pos)
{assert(pos _start);assert(pos _finish);iterator end pos 1;while (end _finish){*(end - 1) *end;end;}_finish--;
}// operator[]
T operator[](int i)
{return _start[i];
}
const T operator[](int i) const
{return _start[i];
} 上面代码实现了 vector 的一些基本操作包括尾插、尾删、插入、删除元素以及重载下标运算符。
push_back(x) 在 vector 的末尾添加一个元素 x。如果当前容量已满调用 reserve() 扩大容量初始为 4之后每次扩展为当前容量的两倍随后将新元素赋值到 _finish 指向的位置然后递增 _finish。pop_back() 从 vector 的末尾删除一个元素。先检查是否为空条件判断有一个多余的分号应去掉然后递减 _finish即可。insert(pos, x): 在指定位置 pos 插入元素 x。先检查 pos 是否有效。如果当前容量已满扩容并更新 pos 的指向。通过向后移动元素为新元素留出空间最后将 x 放入 pos 位置并递增 _finish。erase(pos): 删除指定位置的元素。先检查 pos 是否有效。将 pos 后面的元素向前移动覆盖 pos 位置的元素最后递减 _finish。提供对 vector 元素的随机访问。非常量版本返回可修改的元素引用常量版本返回常量引用保证元素不能被修改。
完整代码
vector.h
#pragma once
#includeiostream
#includevector
#includeassert.h
using namespace std;// 模板不能把声明和定义分离因此只定义了一个.h文件。namespace zy
{
//vctorvectorinttemplateclass Tclass vector{public://构造/*vector(){}*/vector() default; // C11 强制生成默认构造vector(size_t n, const T val T()){reserve(n);for (size_t i 0; i n; i){push_back(val);}}vector(int n, const T val T()){ //解决传单个整形参数不匹配问题reserve(n);for (size_t i 0; i n; i){push_back(val);}}templateclass InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}//拷贝构造vector(const vectorT v){reserve(v.size());for (auto e : v){push_back(e);}}//swapvoid swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}//赋值运算符重载vectorT operator(vectorT tmp){swap(tmp);return *this;}//析构函数~vector(){delete[] _start;_start _finish _end_of_storage nullptr;}//迭代器typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//emptybool empty(){if (_start _finish)return true;elsereturn false;}// size和capacitysize_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}// reservevoid reserve(size_t n){if (n capacity()){size_t old_size size();T* tmp new T[n];//memcpy(tmp, _start, old_size * sizeof(T));for (size_t i 0; i old_size; i){tmp[i] _start[i];}delete[] _start;_start tmp;_finish _start old_size;_end_of_storage _start n;}}//resizevoid resize(size_t n, T val T()){if (n _finish){_finish _start n;}else{reserve(n);while (_finish _start n){*_finish val;_finish;}}}//尾插void push_back(const T x){if (_finish _end_of_storage){reserve(capacity() 0 ? 4 : 2 * capacity());}*_finish x;_finish;}//尾删void pop_back(){if (!empty());--_finish;}//insertvoid insert(iterator pos, const T x){assert(pos _start);assert(pos _finish);//扩容if (_finish _end_of_storage){//解决迭代器失效的问题size_t len pos - _start;reserve(capacity() 0 ? 4 : 2 * capacity());pos _start len;}iterator end _finish - 1;while (end pos){*(end 1) *end;end--;}*pos x;_finish;}//erasevoid erase(iterator pos){assert(pos _start);assert(pos _finish);iterator end pos 1;while (end _finish){*(end - 1) *end;end;}_finish--;}// operator[]T operator[](int i){return _start[i];}const T operator[](int i) const{return _start[i];}private:iterator _start nullptr;iterator _finish nullptr;iterator _end_of_storage nullptr;};templateclass Tvoid print_vector(const vectorT v){// 规定不能在没有实例化的类模板里面取东西编译器不能区分这里const_iterator是类型还是静态成员变量// 想取东西需要在开头加typename或者使用auto自动判断类型//typename vectorT::const_iterator it v.begin();auto it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;}void vector_test1(){vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//v.push_back(5);v.insert(v.begin() 1, 6);print_vector(v);auto it v.begin();while (it ! v.end()){//使用insert和erase以后就不能直接访问需要先更新这个迭代器的值。//因为在vs的标准库中是会报错的因为发生了迭代器失效if ((*it) % 2 0){//it v.erase(it);v.erase(it);}else {it;}}print_vector(v);}
};vector迭代器失效问题 迭代器的主要作用就是让算法能够忽略底层数据结构的差异可直接对容器进行遍历。其底层实际就是一个指针或者是对指针进行了封装比如vector的迭代器就是原生态指针T*。因此迭代器失效实际上就是迭代器底层对应的指针所指向的空间被销毁了或被修改了导致迭代器指向的是一块已经被释放的空间或被修改后的空间造成的后果是程序崩溃或取值不对。
对于vector可能会导致其迭代器失效的操作有
会引起其底层空间改变的操作都有可能是迭代器失效比如resize、reserve、insert、assign、push_back等。
#include iostream
using namespace std;
#include vector
int main()
{vectorint v{1,2,3,4,5,6};auto it v.begin();// 将有效元素个数增加到100个多出的位置使用8填充操作期间底层会扩容// v.resize(100, 8);// reserve的作用就是改变扩容大小但不改变有效元素个数操作期间可能会引起底层容量改变// v.reserve(100);// 插入元素期间可能会引起扩容而导致原空间被释放// v.insert(v.begin(), 0);// v.push_back(8);// 给vector重新赋值可能会引起底层容量改变v.assign(100, 8);/*出错原因以上操作都有可能会导致vector扩容也就是说vector底层原理旧空间被释放掉而在打印时it还使用的是释放之间的旧空间在对it迭代器操作时实际操作的是一块已经被释放的空间而引起代码运行时崩溃。解决方式在以上操作完成之后如果想要继续通过迭代器操作vector中的元素只需给it重新赋值即可。*/while(it ! v.end())
{cout *it ;it;
} coutendl;return 0;
} 指定位置元素的删除操作--erase
#include iostream
using namespace std;
#include vector
int main()
{int a[] { 1, 2, 3, 4 };vectorint v(a, a sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvectorint::iterator pos find(v.begin(), v.end(), 3);// 删除pos位置的数据导致pos迭代器失效。v.erase(pos);cout *pos endl; // 此处会导致非法访问return 0;
} erase删除pos位置元素后pos位置之后的元素会往前搬移没有导致底层空间的改变理论上讲迭代器不应该会失效但是如果pos刚好是最后一个元素删完之后pos刚好是end的位置而end位置是没有元素的那么pos就失效了。因此删除vector中任意位置上元素时vs就认为该位置迭代器失效了。
以本题为例删除vector中所有的偶数。
#include iostream
using namespace std;
#include vector
int main()
{vectorint v{ 1, 2, 3, 4 };auto it v.begin();while (it ! v.end()){if (*it % 2 0)v.erase(it);it;} return 0;
} 这样写就会导致迭代器失效的问题在删除it位置的元素后后面的元素会先前覆盖也就是说此时 it 又指向了下一个元素然后it导致跳过了一个元素有可能导致数据删除的不干净。解决办法是每次删除元素后返回一个迭代器给it在删除元素时跳过it这样就避免了‘遍历时有元素被跳过。
#include iostream
using namespace std;
#include vector
int main()
{vectorint v{ 1, 2, 3, 4 };auto it v.begin();while (it ! v.end()){if (*it % 2 0)it v.erase(it);elseit;} return 0;
} 值得注意的是Linux下g编译器对迭代器失效的检测并不是非常严格处理也没有vs下极端。且与vector类似string在插入扩容操作和erase之后迭代器也会失效。 迭代器失效解决办法是在使用前对迭代器重新赋值即可。
