vector与list的简单介绍 Vector 最大最小值索引位置，扩容的特点......

vector是表示大小可以变化的数组的序列容器。

就像数组一样，vector对其元素使用连续的存储位置，这意味着也可以使用指向其元素的常规指针上的偏移量来访问其元素，并且与数组中的元素一样高效。但与数组不同的是，它们的大小可以动态变化，它们的存储由容器自动处理。

在内部，vector使用动态分配的数组来存储其元素。当插入新元素时，可能需要重新分配此数组才能增大大小，这意味着分配一个新数组并将所有元素移动到该数组。就处理时间而言，这是一项相对昂贵的任务，因此，每次将元素添加到容器时，vector都不会重新分配。

相反，vector容器可能会分配一些额外的存储来适应可能的增长，因此容器的实际容量可能大于包含其元素（即其大小）严格需要的存储。库可以实施不同的增长策略，以平衡内存使用和重新分配之间的平衡，但无论如何，重新分配应该只在大小的对数增长间隔下发生，以便在vector末尾插入单个元素时可以提供摊销的恒定时间复杂度（参见push_back）。

因此，与数组相比，vector消耗更多的内存，以换取以有效的方式管理存储和动态增长的能力。

与其他动态序列容器（deques、lists 和 forward_lists）相比，vector非常有效地访问其元素（就像数组一样），并且相对有效地从其末端添加或删除元素。对于涉及在末尾以外的位置插入或删除元素的操作，它们的性能比其他操作差，并且迭代器和引用的一致性低于列表和forward_lists。

这么多话，简单的来说vector帮我们构建了c语言中的数组，但与c语言数组相比较而言，他的效率与使用起来远远大于数组。

本篇文章就不再详细向上篇文章string的介绍了，这里只给几个经常用到的几个功能的使用案例与其简单的实现还有一些注意事项；

首先展示成员变量：

template<class T>
class vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;
private:
		iterator _start;
		iterator _finish;
		iterator _endofstorage;
};

每个成员变量都是迭代器指针来存储的，不再是简单的用数组来存！！！

构造函数

我们知道数组有分很多种

比如如下我们构建整形数组与字符数组：

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> v;//整形数组
	vector<char> v;//字符数组
	vector<double> v;//小数数组
	return 0;
}

对于vector有多种构造

我们挨个展示使用案例：

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> first;                                // 空
	vector<int> second(4, 100);                       // 4个100
	vector<int> third(second.begin(), second.end());  // 用second创建，里面存的值与second相同
	vector<int> 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 <class InputIteartor>
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<T>& 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<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> second(4, 100);                       // 4个100
	vector<int>::iterator it = second.begin();
	while (it != second.end())
	{
		cout << *it << " ";
		it++;
	}
	return 0;
}

同样也有反向的，这里便于观察，我们将second换一组值

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int myints[] = { 16,2,77,29 };
	vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));//利用数组构造
	vector<int>::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<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> 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<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> t;
    t.push_back(1);
    t.push_back(2);
    t.push_back(3);
    t.pop_back();
    vector<int> ::iterator pos = find(t.begin(), t.end(), 2);
    cout << *pos << endl;
}

运行结果：

insert

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> t;
    t.push_back(1);
    t.push_back(2);
    t.push_back(3);
    vector<int> ::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<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> t;
    t.push_back(1);
    t.push_back(2);
    t.push_back(3);
    vector<int> ::iterator pos = find(t.begin(), t.end(), 2);
    t.erase(pos);
    for (auto& e : t)
    {
        cout << e << " ";
        e++;
    }
}
运行结果：

erase就与insert相反，他做到的就是挨个向前移动
iterator erase(iterator pos)
{
	assert(pos >= _start);
	assert(pos <= _finish);
	iterator it = pos;
	while (it < _finish)
	{
		*it = *(it + 1);
		++it;
	}
	--_finish;
	return pos;
}
注意：

返回的位置为删除位置的下一个，就比如说vector里面存的是 1 2 3 4 5 6 7 8 9，我们删除5

那么就会返回6的位置的迭代器。

swap

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> t;
    t.push_back(1);
    t.push_back(2);
    t.push_back(3);
    vector<int> ::iterator pos = find(t.begin(), t.end(), 2);
    vector<int> 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;
}

运行结果：

swap是由std标准库实现的，我们只需要利用他将两个对象的每个成员变量都交换完，不遗漏就可以；

		void swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);
		}

operator[]

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> t;
    t.push_back(1);
    t.push_back(2);
    t.push_back(3);
    vector<int> ::iterator pos = find(t.begin(), t.end(), 2);
    cout << t[2];
}

运行代码：

这个没得说了，

T& operator[](size_t pos)
{
	assert(pos < size());
	return _start[pos];
	//return *(_start + pos);
}
const T& operator[](size_t pos) const
{
	assert(pos < size());
	//return *(_start + pos);
	return _start[pos];
}

其实到这里vector常用的功能已经说完了，

list

1. 标准库中的list类的介绍：

list是序列容器，允许在序列中的任何位置执行恒定时间插入和擦除操作，并在两个方向上进行迭代。

list容器以双链表的形式实现;双链表可以将它们包含的每个元素存储在不同且不相关的存储位置。排序通过与指向其前面元素的链接的每个元素的关联以及指向其后面元素的链接来保持内部排序。

它们与forward_list非常相似：主要区别在于forward_list对象是单链表，因此它们只能向前迭代，以换取更小、更高效。

与其他基本标准序列容器（数组、向量和 deque）相比，列表在插入、提取和移动元素方面通常表现更好，这些元素位于容器内已经获得迭代器的任何位置，因此在大量使用这些元素的算法中也是如此，例如排序算法。

与其他序列容器相比， list s 和 forward_lists 的主要缺点是它们无法通过其位置直接访问元素;例如，要访问中的 list 第六个元素，必须从已知位置（如开始或结束）迭代到该位置，这需要这些位置之间的线性时间。它们还会消耗一些额外的内存来保留与每个元素关联的链接信息（这对于大型小型元素列表来说可能是一个重要因素）。

list对于官方的介绍其实很简单，其实就是一句话就可以概括，带头的双向循环链表；

用法与vector差不多完完全全一样，这里就不在展示全部实现了，只给大家展示使用，给大家推荐一篇好的文章把

STL详解（五）—— list的介绍及使用_stl的list-CSDN博客

STL详解（六）—— list的模拟实现_stl list 作为参数-CSDN博客

如果要自己实现vector与list的模拟实现，需要注意的一点就是深拷贝的问题；

首先的准备工作（实现list类的框架）：

我们上面已经介绍过了list是链表那么作为链表的每个结点，他都是会有prev，next指针，还有存储的val值。解决了list类的单个结点的信息，那么对于list我们要准备的成员变量就是两个成员变量，一个就是头结点指针（也叫哨兵位结点指针），另一个就是size大小；

template <class T>
struct list_node
{
	T _data;
	list_node<T>* _prev;
	list_node<T>* _next;
	list_node(const T& x = T())
		:_data(x)
		, _prev(nullptr)
		, _next(nullptr)
	{}
};
class list
{
    typedef list_node<T> Node;
private:
		Node* _head;
		size_t _size;
	};

（这里的迭代器实现有点特殊，这里就不在详细说了，我就直接删除了，下篇文章会尽可能详细说明）

拷贝构造：

再次基础上我想先添加上构造函数与析构函数，然后再拿list举例来说明深拷贝问题；

template <class T>
struct list_node
{
	T _data;
	list_node<T>* _prev;
	list_node<T>* _next;
	list_node(const T& x = T())
		:_data(x)
		, _prev(nullptr)
		, _next(nullptr)
	{}
};
class list
{
    typedef list_node<T> 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 最大最小值索引位置，扩容的特点......

vector与list的简单介绍 Vector 最大 最小值 索引 位置，扩容的特点......

vector

标准库中的vector类的介绍：

构造函数

实现：

拷贝函数：

迭代器：

最常用的几个：push_back，pop_back，size，empty,clear

后插，后删，存储的个数，是否为空，与清空数据

查找与修改

find

运行结果：

insert

运行结果：

erase

运行结果：

swap

运行结果：

operator[]

list

1. 标准库中的list类的介绍：

首先的准备工作（实现list类的框架）：

拷贝构造：

erase注意：

相关推荐

最近更新

热门阅读

vector与list的简单介绍 Vector 最大最小值索引位置，扩容的特点......