vector
标准库中的vector类的介绍：
这么多话，简单的来说vector帮我们构建了c语言中的数组，但与c语言数组相比较而言，他的效率与使用起来远远大于数组。
本篇文章就不再详细向上篇文章string的介绍了，这里只给几个经常用到的几个功能的使用案例与其简单的实现还有一些注意事项；
首先展示成员变量：
template
class vector
{
public:
typedef T iterator;
typedef const T const_iterator;
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
每个成员变量都是迭代器指针来存储的，不再是简单的用数组来存！！！
构造函数
我们知道数组有分很多种
比如如下我们构建整形数组与字符数组：
include
include
using namespace std;
int main()
{
vector v;//整形数组
vector v;//字符数组
vector v;//小数数组
return 0;
}
对于vector有多种构造
我们挨个展示使用案例：
include
include
using namespace std;
int main()
{
vector first; // 空
vector second(4, 100); // 4个100
vector third(second.begin(), second.end()); // 用second创建，里面存的值与second相同
vector fourth(third); // a copy of third
int myints[] = { 16,2,77,29 };
vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));//利用数组构造
//挨个打印
cout << "first:";
for (auto e : first)
{
cout << e << " ";
}
cout << endl;
cout << "second:";
for (auto e : second)
{
cout << e << " ";
}
cout << endl;
cout << "third:";
for (auto e : third)
{
cout << e << " ";
}
cout << endl;
cout << "fourth:";
for (auto e : fourth)
{
cout << e << " ";
}
cout << endl;
cout << "The contents of fifth are:";
for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
cout << ' ' << *it;
cout << '\n';
return 0;
}
实现：
对于构造函数不存在浅拷贝与深拷贝的问题，实现起来非常容易，那我就举例几个吧
template
vector(InputIteartor first, InputIteartor last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
vector(size_t n, const T& val = T())
: _start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
vector(int n, const T& val = T())
: _start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
拷贝函数：
但是我们实现拷贝函数的时候就需要注意一点，我们做到的不是仅仅是浅拷贝，打个比方说，我们的vector存的是二叉树，如果进行浅拷贝的化，那就意味着left与right也会被拷贝进入新的对象，这样就会导致新的对象的left指向的是老的树。所以构造函数要做到的是深拷贝；
vector(const vector& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(v.capacity());
for (auto& e : v)
{
push_back(e);
}
}
我们在拷贝的时候 是将v的每一个val的值赋给e，不再是仅仅将指针的值赋给他，这一点就是做到了深拷贝！！
迭代器：
vector的迭代器与string的迭代器完全相关，不太清楚的，可以去看我写的string那一篇，那一篇从原理详细讲解了迭代器；
就比如我们使用迭代器打印上面的second
include
include
using namespace std;
int main()
{
vector second(4, 100); // 4个100
vector::iterator it = second.begin();
while (it != second.end())
{
cout << *it << " ";
it++;
}
return 0;
}
同样也有反向的，这里便于观察，我们将second换一组值
include
include
using namespace std;
int main()
{
int myints[] = { 16,2,77,29 };
vector fifth(myints, myints + sizeof(myints) / sizeof(int));//利用数组构造
vector::reverse_iterator it = fifth.rbegin();
while (it != fifth.rend())
{
cout << *it << " ";
it++;
}
return 0;
}
因为我们存的成员变量有存首位置的迭代器，所以可以直接返回_start，这一点实现起来还是很方便的；
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;
}
最常用的几个：push_back，pop_back，size，empty,clear
后插，后删，存储的个数，是否为空，与清空数据
include
include
using namespace std;
int main()
{
vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
cout << "添加完后vector：";
for (auto& e : v)
{
cout << e << " ";
e++;
}
cout << endl;
cout << "vector的大小：";
cout << v.size() << endl;
v.pop_back();
cout << "后删完后vector：";
for (auto& e : v)
{
cout << e << " ";
e++;
}
cout << endl;
cout << "vector是否为空：";
cout << v.empty() << endl;//为空返回true，反之false
cout << "clear后：";
v.clear();//清空
for (auto& e : v)
{
cout << e << " ";
e++;
}
cout << endl;
return 0;
}
查找与修改
vector同样与string一样支持这些功能
就比如查找我们可以通过find查找特定的值，也可以通过直接下标operator[]任意访问
find
include
include
using namespace std;
int main()
{
vector t;
t.push_back(1);
t.push_back(2);
t.push_back(3);
t.pop_back();
vector ::iterator pos = find(t.begin(), t.end(), 2);
cout << *pos << endl;
}
运行结果：
insert
include
include
using namespace std;
int main()
{
vector t;
t.push_back(1);
t.push_back(2);
t.push_back(3);
vector ::iterator pos = find(t.begin(), t.end(), 2);
t.insert(pos,10);
for (auto& e : t)
{
cout << e << " ";
e++;
}
}
运行结果：
void insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _endofstorage)
{
//扩容
size_t len = pos - _start;
size_t cp = capacity() == 0 ? 4 : capacity() 2;
reserve(cp);
pos = _start + len;
}
T end = _finish - 1;
while (end >= pos)
{
(end + 1) = end;
--end;
}
*pos = x;
++_finish;
}
erase
include
include
using namespace std;
int main()
{
vector t;
t.push_back(1);
t.push_back(2);
t.push_back(3);
vector ::iterator pos = find(t.begin(), t.end(), 2);
t.erase(pos);
for (auto& e : t)
{
cout << e << " ";
e++;
}
}
运行结果：
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos <= _finish);
iterator it = pos;
while (it < _finish)
{
it = (it + 1);
++it;
}
--_finish;
return pos;
}
swap
include
include
using namespace std;
int main()
{
vector t;
t.push_back(1);
t.push_back(2);
t.push_back(3);
vector ::iterator pos = find(t.begin(), t.end(), 2);
vector v(5, 7);//5个7
swap(t, v);
cout << "换后的t:" << " ";
for (auto& e : t)
{
cout << e << " ";
e++;
}
cout << endl;
cout << "换后的v:" << " ";
for (auto& e : v)
{
cout << e << " ";
e++;
}
cout << endl;
}
运行结果：
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
operator[]
include
include
using namespace std;
int main()
{
vector t;
t.push_back(1);
t.push_back(2);
t.push_back(3);
vector ::iterator pos = find(t.begin(), t.end(), 2);
cout << t[2];
}
T& operator
{
assert(pos < size());
return _start[pos];
//return (_start + pos);
}
const T& operator const
{
assert(pos < size());
//return (_start + pos);
return _start[pos];
}
其实到这里vector常用的功能已经说完了，
list
- 标准库中的list类的介绍：
list对于官方的介绍其实很简单，其实就是一句话就可以概括，带头的双向循环链表；
用法与vector差不多完完全全一样，这里就不在展示全部实现了，只给大家展示使用，给大家推荐一篇好的文章把
STL详解（五）—— list的介绍及使用_stl的list-CSDN博客
STL详解（六）—— list的模拟实现_stl list 作为参数-CSDN博客
如果要自己实现vector与list的模拟实现，需要注意的一点就是深拷贝的问题；
首先的准备工作（实现list类的框架）：
我们上面已经介绍过了list是链表那么作为链表的每个结点，他都是会有prev，next指针，还有存储的val值。解决了list类的单个结点的信息，那么对于list我们要准备的成员变量就是两个成员变量，一个就是头结点指针（也叫哨兵位结点指针），另一个就是size大小；
template
struct list_node
{
T _data;
list_node _prev;
list_node _next;
list_node(const T& x = T())
:_data(x)
, _prev(nullptr)
, _next(nullptr)
{}
};
class list
{
typedef list_node Node;
private:
Node* _head;
size_t _size;
};
（这里的迭代器实现有点特殊，这里就不在详细说了，我就直接删除了，下篇文章会尽可能详细说明）
拷贝构造：
再次基础上我想先添加上构造函数与析构函数，然后再拿list举例来说明深拷贝问题；
template
struct list_node
{
T _data;
list_node _prev;
list_node _next;
list_node(const T& x = T())
:_data(x)
, _prev(nullptr)
, _next(nullptr)
{}
};
class list
{
typedef list_node Node;
public:
void empty_init()
{
_head = new Node;//data初始化为0
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
~list()
{
clear();
delete _head;
_head = nullptr;
_size = 0;
}
private:
Node* _head;
size_t _size;
};
同样我们再实现拷贝构造的时候还是需要注意深拷贝问题，深拷贝！！！特别重要；
实现起来与vector原理一模一样还是用auto
list(list<T>& It)//拷贝
{
empty_init();
for (auto e : It)
{
push_back(e);
}
}
erase注意：
erase的删除后的返回值与vector相同原理，就是为了防止迭代器失效，他会返回删除位置的下一个结点的迭代器！！！
大致就这样
接下来我会再写几篇文章介绍string与vector与list一些特殊的小点帮助理解；
就比如说string的''\0''问题，string的capacity大小设计的特点，空间增长的特点，迭代器失效，与反迭代器的实现。
Vector 最大 最小值 索引 位置，扩容的特点......
