STL源码初步接触
STL = Standard Template Library，直译过来是：标准模板库，是惠普实验室开发的一系列软件的统称。从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其他一些组件的集合。这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。STL现在是C++的一部分，因此不用额外安装什么。STL所实现的，是依据泛型思维架设起来的一个概念结构。说了这么多还是不知道STL是个什么东东，今天只是初接触这个概念，感觉很高深的样子，先这样理解吧，STL就是一个仓库，一个存放各种工具的仓库。它的工具分为六大类（六大组件） ：
容器（containers）:各种数据结构，如Vector，list，deque,set,map,用来存放底层数据。一般有序列式（下面要写的Vector就是个这种）、关联式等。
算法（algorithms）:各种常用算法如：sort,search,copy,erase……
迭代器（iterator）：扮演容器与算法之间的胶合剂，是所谓的“泛型指针”，共5种类型，以及他们的衍生变化。所有的STL容器都附带有自己专属的迭代器。原生指针也是一种迭代器。
仿函数（functor）：行为类似函数可作为算法的某种策略。一般函数指针可认为是侠义的仿函数。
配接器（adapter）：一种用来修饰容器，或仿函数，或迭代器接口的东西。
配置器（allocators）负责空间配置与管理。配置器是一个实现了动态空间配置、空间管理、空间释放的class template。
因为下面主要是实现Vector的简单操作，所以就再多讲一点它。Vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。因此Vector的运用对于内存的合理运用与运用得灵活性有很大的帮助。Vector维护的是一个连续的空间，无论元素的型别为何，普通指针都可以作为Vector的迭代器而满足所有必要条件。
Vector 的简单实现：
#pragma once
#include<iostream>
#include<assert.h>
#include<stdlib.h>
using namespace std;
template<class T>
class Vector
{
public:
typedef T* Iterator;
typedef const T* Citerator;
public:
Vector()
:start(NULL)
,finish(NULL)
,endofstorage(NULL)
{}
Vector(const Vector<T>& v)
//:start(new T[v.endofstorage - v.start])
//, finish(v.finish )
//, endofstorage(v.endofstorage)
:start(new T[v.endofstorage - v.start])
, finish(start + (v.finish - v.start))
,endofstorage(start + (v.endofstorage - v.start)) {
my_memcopy(start, v.start, sizeof(T)*(v.endofstorage - v.start));
}
//向Vector中存入size个元素
Vector(Citerator array, size_t size)
:start(new T[size])
, finish(start)
, endofstorage(start + size) {
for (size_t index = ; index < size; ++size) {
start[index] = array[index];
finish++;
}
}
Vector<T>&operator=(const Vector<T>& v) {
if (this != &v) {
Vector<int>tmp(v);
swap(tmp);
}
return *this;
}
~Vector(){
if (start) {
delete[] start;
start = NULL;
// delete[] finish;
finish = NULL;
// delete[] endofstorage;
endofstorage = NULL;
}
}
// 返回首元素的迭代器
Iterator Begin() {
return start;
}
Citerator Begin()const {
return start;
}
// 获取Vector中最后一个元素的下一个位置
Iterator End() {
return finish:
}
Iterator End()const {
return finish;
}
size_t Size()const {
return finish - start;
}
size_t Capacity()const {
return endofstorage - start;
}
bool Empty()const {
return finish == start;
}
T& operator[](size_t index) {
return start[index];
}
const T& operator[](size_t index)const {
return start[index];
}
T& At(size_t index) {
if ((index <= Size()) && (index >= ))
return start[index];
}
const T& At(size_t index)const {
if ((index <= Size()) && (index >= ))
return start[index];
}
// 获取Vector中的第一个元素
T& Front() {
return srart[];
}
const T& Front()const {
return start[];
}
// 获取Vector中的最后一个元素
T& Back() {
return start[finish - start];
}
const T& Back()const {
return start[finish - start];
}
void PushBack(const T& x) {
capacity();
// start[finish - start + 1] = x;
start[finish - start] = x;
finish++;
}
void PopBack() {
if (!Empty()) {
finish--;
}
}
// 在pos位置上插入元素x
Iterator Insert(Iterator pos, const T& x) {
for (size_t index = Size(); index >= (size_t)(pos - start); index--) {
start[index + ] = start[index];
}
*pos = x;
finish++;
return pos;
}
// 删除pos位置上面的元素
Iterator Erase(Iterator pos) {
for (size_t index = (size_t)(pos - start); index < Size(); index++) {
start[index] = start[index + ];
}
finish--;
return pos;
}
// 给Vector赋值n个值为x的元素
void Assign(size_t n, const T& x) {
if (n > endofstorage - start) {
finish = start + n;
capacity();
for (size_t index = ; index < n; index++) {
start[index] = x;
}
}
else {
for (size_t index = ; index < n; index++)
start[index] = x;
}
finish = start + n;
}
public:
//自己管理 扩容
void capacity() {
if (finish >= endofstorage) {
size_t capacity = * (endofstorage - start) + ;
Iterator tmp = new T[capacity];
// 拷贝元素
my_memcopy(tmp, start, sizeof(T)*(endofstorage - start));
size_t ret = finish-start;
delete start;
start = tmp;
finish = start + ret;
endofstorage = start + capacity;
//
/*Iterator pos = start;
size_t index = 0;
while (pos < endofstprage)
temp[index++] = *pos++;
deleta[] start;
start = temp;
finish = start + index;
endofstorage = start + capacity;*/ }
}
void swap(Vector<T>& v) {
std::swap(start, v.start);
std::swap(finish, v.finish);
std::swap(endofstorage, v.endofstorage);
}
void Print() {
for (size_t i = ; i < Size(); i++)
{
cout << start[i] << " ";
}
cout << endl;
}
void* my_memcopy(void* dest, const void* src, size_t sz) {
//assert(!dest || !src);
assert(dest != NULL || src != NULL);
char* ret = (char*)dest;
char* tmp = (char*)src;
while (sz--) {
*ret = *tmp;
ret++;
tmp++;
}
return dest;
}
private:
Iterator start;
Iterator finish;
Iterator endofstorage;
};
其中，注释掉的代码部分是我曾经踩过的坑，下面是部分测试代码
#include"vector.h"
void Test1()
{
Vector<int> list1;
list1.PushBack();
list1.PushBack();
list1.PushBack();
list1.PushBack();
list1.PushBack();
list1.Print();
Vector<int> list2;
list2.PushBack();
list2.PushBack();
list2.PushBack();
list2.PushBack();
list2.PushBack();
list2.Print();
list1 = list2;
list1.Print();
}
void Test2()
{
Vector<int> list1;
list1.PushBack();
list1.PushBack();
list1.PushBack();
list1.PushBack();
list1.PushBack();
list1.Print();
list1.PopBack();
list1.Print();
list1.Insert(&list1.At(), );
list1.Print();
list1.Erase(&list1.At());
list1.Print();
}
int main()
{
Test1();
Test2();
getchar();
return ;
}
注意：扩容时函数中my_memcpy()函数，它的本质就是值拷贝,当Vector中存放的内置类型时没有任何问题，但是像String类这种问题就无法解决。所以下面给出了另一种写法。
/*Iterator pos = start;
size_t index = 0;
while (pos < endofstprage)
temp[index++] = *pos++;
deleta[] start;
start = temp;
finish = start + index;
endofstorage = start + capacity;*/