目录
>>2.?元素的删除iterator erase(iterator position); iterator erase(iterator first, iterator last)
一：vector的相关使用与操作
1.vector的相关介绍：
- vector是表示可变大小数组的序列容器。
-
就像数组一样， vector 也采用的连续存储空间来存储元素。也就是意味着可以采用下标对 vector 的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
-
本质讲， vector 使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因此每当一个新的元素加入到容器的时候，vector 并不会每次都重新分配大小。
-
vector 分配空间策略： vector 会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
-
因此， vector 占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
-
与其它动态序列容器相比（ deques, lists and forward_lists ）， vector 在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists 和forward_lists统一的迭代器和引用更好。
2.vector的使用：
构造和析构
|
(constructor)
构造函数声明
|
接口说明
|
|
vector()
（重点）
|
无参构造
|
|
vector
（
size_t n, const T& val =T()
）
|
构造并初始化
n
个
val
|
|
vector (const T& x);
（重点）
|
拷贝构造
|
|
vector (Iterator first, Iterator last);
|
使用迭代器进行初始化构造
|
注意：T()：T是内置类型T()的结果就是0，T是自定义类型，则类必须提供默认的构造函数。?
迭代器（vector iterator 的使用）
|
iterator
的使用
|
接口说明
|
|
begin()?
+
end()
（重点）
|
获取第一个数据位置的
iterator/const_iterator
， 获取最后一个数据的下一个位置
的
iterator/const_iterator
|
|
rbegin ()
+
rend()
|
获取最后一个数据位置的
reverse_iterator
，获取第一个数据前一个位置的
reverse_iterator
|
容量的操作（vector 空间增长问题）
|
容量空间
| 接口说明 |
|
size()
|
获取数据个数
|
|
capacity()
|
获取容量大小
|
|
empty()
|
判断是否为空
|
| resize(size_t n, T val = T())（重点） |
改变
vector
的
size
|
|
reserve (size_t n)
（重点）
|
改变
vector
放入
capacity
|
-
capacity 的代码在 vs 和 g++ 下分别运行会发现， vs 下 capacity 是按 1.5 倍增长的， g++ 是按 2 倍增长的 。不要固化的认为，顺序表增容都是2 倍，具体增长多少是根据具体的需求定义的。vs 是 PJ 版本 STL ， g++ 是 SGI 版本 STL 。
-
reserve 只负责开辟空间，如果确定知道需要用多少空间， reserve 可以缓解 vector 增容的代价缺陷问题。
-
resize 在开空间的同时还会进行初始化，影响 size 。
修改（vector 增删查改）
|
vector
增删查改
|
接口说明
|
| push_back(const T& val)（重点） |
尾插
|
|
pop_back()?
（重点）
|
尾删
|
| find(class Iterator, class T) |
查找。（注意这个是算法模块实现，不是
vector
的成员接口）
|
| insert（iterator position, const T& val） void insert (iterator position, size_t?n, const T& val); template <class InputIterator> void insert (iterator position, InputIterator first, InputIterator last); |
在
position
之前插入
val
|
| erase(iterator position) erase (iterator first, iterator last); |
删除
position
位置的数据
|
| swap(vector& x) |
交换两个
vector
的数据空间
|
| operator[] (size_type n)（重点） operator[] (size_type n) const; |
像数组一样访问
|
vector扩容机制的验证：
分别在vs和linux下运行如下代码：
void TestPushBack()
{
vector<int>v;
size_t sz = v.capacity();
for (int i = 0; i < 100; i++)
{
v.push_back(i);
//容量每改变一次就扩容一次
if (sz != v.capacity())
{
sz = v.capacity();
cout << sz << endl;
}
}
}
二：迭代器失效
1.什么是迭代器？
迭代器就类似于一个指针
迭代器失效，实际就是迭代器对应的指针失效了
2.为什么迭代器会失效？
迭代器对应的指针如果指向的是一块非法的空间，则指针就失效了，即迭代器就失效了。
3.vector哪些操作会导致迭代器失效？
注意：linux和vs下对于迭代器失效的处理是不同的，以下给出了两种环境下的测试对比。
>>1.所有可能会导致扩容操作的方法都可能会导致迭代器失效
? ? ? ? push_back() | insert | assign
? ? ? ? reserve | resize
? ? ? ? operator=
例如：
>>2.?元素的删除iterator erase(iterator position); iterator erase(iterator first, iterator last)
>>3.swap
4.迭代器失效该如何解决？
在使用迭代器之前，最好给迭代器重新赋值，以上问题的解决方法：
//解决迭代器失效的方法，在使用之前对其重新赋值
//以下为修改之后的结果
void itoratorTest4()
{
vector<int>v = { 1, 2, 3, 4, 5 };
auto it = v.begin();
v.resize(10, 6);
it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
}
void itoratorTest5()
{
vector<int>v = { 1, 2, 3, 4, 5 };
auto it = v.begin();
while (it != v.end())
{
it = v.erase(it);
}
}
void itoratorTest6()
{
vector<int>v1 = { 1, 2, 3, 4, 5 };
vector<int>v2 = { 6, 7, 8, 9, 0 };
auto it1 = v1.begin();
auto it2 = v2.begin();
swap(v1, v2);
//while (it1 != v2.end())
it1 = v1.begin();
it2 = v2.begin();
while (it1 != v1.end())
{
cout << *it1 << " ";
it1++;
}
//while (it2 != v1.end())
while (it2 != v2.end())
{
cout << *it2 << " ";
it2++;
}
}三：vector的模拟实现
//Vector.h
#pragma once
namespace Ld
{
template<class Iterator>
size_t distance(Iterator first, Iterator end)
{
size_t count = 0;
while (first != end)
{
count++;
first++;
}
return count;
}
}//Vertor.cpp
#include<iostream>
using namespace std;
#pragma warning(disable:4996)
#include"vector.h"
#include<assert.h>
namespace Ld
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef T* reverse_iterator;
typedef const T* const_iterator;
///构造和析构函数//
vector()
:start(nullptr)
, finish(nullptr)
, end_of_storage(nullptr)
{}
vector(int n, const T&value = T())
:start(new T[n])
, finish(start)
, end_of_storage(start+n)
{
for (int i = 0; i < n; i++)
{
*finish++ = value;
}
}
//区间构造
template<class Iterator>
vector(Iterator first,Iterator last)
{
size_t n = Ld::distance(first,last);
start = new T[n];
finish = start;
end_of_storage = start + n;
while (first != last)
{
*finish = *first;
finish++;
first++;
}
}
vector(const vector<T>&v)
:start(nullptr)
, finish(nullptr)
, end_of_storage(nullptr)
{
vector<T>temp(v.cbegin(), v.cend());
this->swap(temp);
}
vector<T>& operator=(vector<T>v)
{
this->swap(v);
return *this;
}
~vector()
{
if (start)
{
delete[] start;
start = nullptr;
finish = nullptr;
end_of_storage = nullptr;
}
}
迭代器操作//
iterator begin()
{
return start;
}
iterator end()
{
return finish;
}
const_iterator cbegin()const
{
return start;
}
const_iterator cend()const
{
return finish;
}
reverse_iterator rbegin()
{
return end();
}
reverse_iterator rend()
{
return begin();
}
容量操作
size_t size()
{
return finish - start;
}
size_t capacity()
{
return end_of_storage - start;
}
bool empty()
{
return finish == start;
}
void resize(size_t newsize, const T&value = T())
{
size_t oldsize = size();
if (newsize > oldsize)
{
size_t oldcapacity = capacity();
if (newsize > oldcapacity)
{
//需要进行扩容
reserve(newsize);
}
for (size_t i = oldsize; i < newsize; i++)
{
start[i] = value;
}
}
finish = start + newsize;
}
void reserve(size_t newcapacity)
{
size_t oldcapacity = capacity();
size_t n = size();
if (oldcapacity < newcapacity)
{
//1.申请新空间
T*temp = new T[newcapacity];
//2.元素拷贝
if (start)
{
for (size_t i = 0; i < n; i++)
{
temp[i] = start[i];
}
delete[] start;
}
//3.旧空间的释放
start = temp;
finish = start + n;
end_of_storage = start + newcapacity;
}
}
元素访问/
T&operator[](size_t index)
{
assert(index < size());
return start[index];
}
T&front()
{
return start[0];
}
T&back()
{
return *(finish-1);
}
const T&operator[](size_t index)const
{
assert(index < size());
return start[index];
}
const T&front()const
{
return start[0];
}
const T&back()const
{
return *(finish - 1);
}
//修改/
void push_back(const T&value)
{
if (finish == end_of_storage)
reserve(capacity() * 2 + 3);
*finish = value;
finish++;
}
void pop_back()
{
if (!empty())
{
finish--;
}
}
iterator insert(iterator pos,const T&value)
{
if (pos<start || pos>finish)
{
return pos;
}
if (finish == end_of_storage)
reserve(capacity() * 2 + 3);
auto it = finish - 1;
while (it >= pos)
{
*(it + 1) = *it;
it--;
}
*it = value;
finish++;
return pos;
}
iterator erase(iterator pos)
{
if (pos < start || pos >= finish)
return pos;
auto it = pos + 1;
while (it < finish)
{
*(it - 1) = *it;
it++;
}
finish--;
return pos;
}
void clear()
{
finish = start;
}
void swap(vector<T>&v)
{
std::swap(start, v.start);
std::swap(finish, v.finish);
std::swap(end_of_storage, v.end_of_storage);
}
private:
iterator start;
iterator finish;
iterator end_of_storage;
};
}
void TestVector1()
{
Ld::vector<int> v1;
Ld::vector<int> v2(10, 5);
Ld::vector<int> v3(v2);
int array[] = { 1, 2, 3, 4, 5 };
Ld::vector<int> v4(array, array + sizeof(array) / sizeof(array[0]));
for (size_t i = 0; i < v2.size(); ++i)
cout << v2[i] << " ";
cout << endl;
for (auto e : v3)
cout << e << " ";
cout << endl;
auto it = v4.begin();
while (it != v4.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// 注意：目前实现的vector不支持{}的构造
// bite::vector<int> v5{ 1, 2, 3, 4, 5 };
}
void TestVector2()
{
int array[] = { 1, 2, 3, 4, 5 };
Ld::vector<int> v(array, array + sizeof(array) / sizeof(array[0]));
cout << v.size() << endl;
cout << v.capacity() << endl;
cout << v.front() << endl;
cout << v.back() << endl;
v.push_back(6);
v.push_back(7);
v.push_back(8);
v.push_back(8);
cout << v.size() << endl;
cout << v.capacity() << endl;
cout << v.front() << endl;
cout << v.back() << endl;
for (auto e : v)
cout << e << " ";
cout << endl;
v.pop_back();
v.pop_back();
v.pop_back();
for (auto e : v)
cout << e << " ";
cout << endl;
v.insert(v.begin(), 0);
for (auto e : v)
cout << e << " ";
cout << endl;
v.erase(v.begin());
for (auto e : v)
cout << e << " ";
cout << endl;
cout << v.size() << endl;
cout << v.capacity() << endl;
cout << v.front() << endl;
cout << v.back() << endl;
v.clear();
if (v.empty())
{
cout << "v is empty()" << endl;
}
else
{
cout << "v is not empty()" << endl;
}
}
void TestVector3()
{
Ld::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.resize(10, 4); // 元素个数增多，扩容，多出的元素使用4填充
v.resize(20); // 元素个数增多，扩容，多出的元素使用int()默认值即0填充
v.resize(8); // 元素个数缩小
v.resize(15, 8); // 元素个数增多，但是不需要扩容
Ld::vector<int> vv(5, 3);
v.swap(vv);
for (auto e : v)
cout << e << " ";
cout << endl;
for (auto e : vv)
cout << e << " ";
cout << endl;
}
class String
{
public:
String(const char*str = "")
{
if (nullptr == str)
_str = "";
_str = new char[strlen(str) + 1];
strcpy(_str, str);
}
String(const String&s)
:_str(new char[strlen(s._str) + 1])
{
strcpy(_str, s._str);
}
String& operator=(const String &s)
{
if (this != &s)
{
char*temp = new char[strlen(s._str) + 1];
strcpy(temp, s._str);
delete[] _str;
_str = temp;
}
return *this;
}
private:
char*_str;
};
void TestVector4()
{
Ld::vector<String> v;
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");
v.push_back("4444");
}
void TestVector5()
{
Ld::vector<Ld::vector<int>> vv;
vv.resize(5);
for (size_t i = 0; i < vv.size(); ++i)
vv[i].resize(i + 1, 1);
for (size_t i = 2; i < 5; ++i)
{
for (size_t j = 1; j < i; ++j)
{
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
for (size_t i = 0; i < vv.size(); ++i)
{
for (size_t j = 0; j < vv[i].size(); ++j)
{
cout << vv[i][j] << " ";
}
cout << endl;
}
}
void TestVector6()
{
Ld::vector<int>v;
v.resize(5);
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
auto it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
int main()
{
//TestVector1();
//TestVector2();
//TestVector3();
//TestVector4();
TestVector5();
//TestVector6();
return 0;
}
