vector底层特点

题目

1. 下面这个代码输出的是( )

#include <iostream>

#include <vector>

using namespace std;

int main(void)

{

	vector<int>array;

	array.push_back(100);

	array.push_back(300);

	array.push_back(300);

	array.push_back(300);

	array.push_back(300);

	array.push_back(500);

	vector<int>::iterator itor;

	for(itor=array.begin();itor!=array.end();itor++)

	{

		if(* itor==300)

		{

			itor=array.erase(itor);

		}

	}

	for(itor=array.begin();itor!=array.end();itor++)

	{

			cout<<*itor<<" ";

	}

  return 0;

}

答案：100、300、300、500

知识点

erase删除

iterator erase(iterator pos)
{
	assert(pos >= _start);
	assert(pos < _finish);

	iterator it = pos + 1;
	while (it < _finish)
	{
		*(it - 1) = *it;
		++it;
	}

	--_finish;

	return pos;
}

迭代器失效，并不是该位置不存在，而是其中的内容逻辑不再可信

如 *(it - 1) = *it ，即改变了各个地址原本的内容，此时原本的指针就不再可信，所以最后 return pos 返回的正好是被删除的元素的位置，也是下一个元素移过来的位置，所以指向该位置就相当于指向了删除元素的下一个元素，此时就不应该再++去追寻下一个位置了

2. T是一个数据类型，在vs系列编译器中，debug模式下，关于std::vector::at 和 std::vector::operator[] 描述正确的是( )

A.at总是做边界检查，operator[] 不做边界检查.

B.at 不做边界检查，operator[] 做边界检查.

C.at和operator[]都是会做边界检查的

D.以上都不对

知识点

at(index) 会检查下标是否合法。如果越界，会抛出 std::out_of_range 异常。
operator 不会做边界检查，使用错误索引可能会导致未定义行为（尤其是在 Release 模式下）。

这在 Visual Studio 系列编译器中尤其明显：

Debug 模式下，operator[] 可能在运行时被加上检查机制（例如使用了 _ITERATOR_DEBUG_LEVEL 相关特性），但这是编译器特性，不是标准行为。

标准C++明确规定只有 at() 一定会抛异常检查越界。

代码示例

std::vector::at() 和 std::vector::operator[] 的区别：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30};

    // 使用 at()：会做边界检查，越界会抛出异常
    try {
        std::cout << "v.at(2): " << v.at(2) << std::endl; // OK
        std::cout << "v.at(3): " << v.at(3) << std::endl; // 抛出 std::out_of_range 异常
    } catch (const std::out_of_range& e) {
        std::cout << "异常 caught: " << e.what() << std::endl;
    }

    // 使用 operator[]：不会做边界检查，越界是未定义行为
    std::cout << "v[2]: " << v[2] << std::endl; // OK
    std::cout << "v[3]: " << v[3] << " (未定义行为!)" << std::endl; // 未定义行为

    return 0;
}

输出示例（可能会因编译器和运行环境不同而变化）：

v.at(2): 30
异常 caught: vector::_M_range_check: __n (which is 3) >= this->size() (which is 3)
v[2]: 30
v[3]: -858993460 (未定义行为!)

3. 下面程序的输出结果正确的是( )


int main()
{
	int ar[] = {1,2,3,4,5,6,7,8,9,10};
	int n = sizeof(ar) / sizeof(int);
	vector<int> v(ar, ar+n);  //原始数组转换为 vector
	cout<<v.size()<<":"<<v.capacity()<<endl;  //10：10
	v.reserve(100);
	v.resize(20);
	cout<<v.size()<<":"<<v.capacity()<<endl;  //20：100
	v.reserve(50);  //试图把 capacity 设为 50，但当前已有 100，不会减小
	v.resize(5);
	cout<<v.size()<<":"<<v.capacity()<<endl;  //5：100
}

知识点

reserve和resize

void resize(size_t n, const T& val = T()) 
//T 是模板参数，代表用 vector 这个模板类时，实际存储的数据类型。
//int()=0,double()=0,string()=""，也可以直接用数字填充resize(10,6)
{
	if (n < size)
	{
		_finish = _start + n;
	}
	else
	{
		reserve(n);
		while (_finish != _start + n)
		{
			*_finish = val;
			++_finish;
		}
	}
}

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t oldSize = size();
		T* tmp = new T[n];
		for (size_t i = 0; i < oldSize; i++)
		{
			tmp[i] = _start[i];
		}

		delete[] _start;

		_start = tmp;
		_finish = _start + oldSize;  //大小看起来没变，但更新地址
		_end_of_storage = _start + n;
	}
}

可以看出reserve只考虑 n＞capacity() 的情况

4. 下面程序的输出结果正确的是( )

int main()
{
	int ar[] ={1,2,3,4,0,5,6,7,8,9};
	int n = sizeof(ar) / sizeof(int);
	vector<int> v(ar, ar+n);
	vector<int>::iterator it = v.begin();
	while(it != v.end())
	{
		if(*it != 0)
			cout<<*it;
		else
			v.erase(it);  //v.erase(it) 会删除 it 所指的元素，并使该迭代器失效。
		it++;
	}
	return 0;
}
//正确：
	while(it != v.end())
	{
		if(*it != 0)
			cout<<*it;
      it++;
		else
		it=v.erase(it);
	}

5. 下面关于迭代器失效的描述哪个是错误的（）

A.vector的插入操作一定会导致迭代器失效

B.vector的插入操作有可能不会导致迭代器失效

C.vector的删除操作只会导致指向被删除元素及后面的迭代器失效

D.vector的删除操作只会导致指向被删除元素的迭代器失效

知识点

插入操作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 : capacity() * 2);
		pos = _start + len;
	}

	iterator it = _finish - 1;
	while (it >= pos)
	{
		*(it + 1) = *it;
		--it;
	}

	*pos = x;
	++_finish;
}

当插入需要扩容时，迭代器就失效了，因为指针原本指向的内存空间不够，另辟空间作为存储空间，原本指针指向的地址失效，需要以重新开辟的空间作为地址，即 pos = _start + len

vector底层实现

#pragma once
#include <assert.h>
#include <algorithm>

namespace zoya
{
	template<class T>
	class vector
	{
	public:
		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() {} //默认构造函数
		//vector(const vector& v) 等价
		//因为类名本身是模板类 vector<T>，所以写成 vector 实际就是 vector<T>。
		vector(const vector<T>& v)  //拷贝构造函数
		{
			reverse(v.size());  //预留空间
			for (auto& e : v)  
			//由于 e 是引用（auto&），但 v 是 const，所以 e 的类型其实是 const T&
			{
				push_back(e);  //每个e加到新vector中
			}
		}

		~vector()
		{
			delete[] _start;  
			//reserve中new T[n]申请了内存，所以_start指向的内存是动态申请的，要在析构函数delete[]释放
			_start = _finish = _end_of_storage = nullptr;
		}

		/* 普通写法 赋值运算符
		//vector& operator=(const vector& v)
		vector<T>& operator=(const vector<T>& v)
		{
			if (this != &v)
			{
				delete[] _start;
				_start = _finish = _end_of_storage = nullptr;;
				reserve(v.size());
				for (auto& e : v)
				{
					push__back(e);
				}
			}
			return *this;
		}*/

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

		//vector<T>& operator=(vector<T>& v)
		//错误写法，这样会让v1=v2，也让v2=v1了
		vector<T>& operator=(vector<T> v)
		{
			this->swap(v);
			//swap(v)
			//this-> 明确告诉编译器去当前类作用域里找名为 swap 的成员函数
			//但swap(v)这是一个非限定名调用，编译器会优先查找当前作用域中是否有 swap 函数。也可能不自动从当前类中查找成员，可能有编译错误或歧义
			return *this;
		}

		void resize(size_t n, const T& val = T()) 
		//T 是模板参数，代表用 vector 这个模板类时，实际存储的数据类型。
		//int()=0,double()=0,string()=""，也可以直接用数字填充resize(10,6)
		{
			if (n < size)
			{
				_finish = _start + n;
			}
			else
			{
				reserve(n);
				while (_finish != _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
		}

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t oldSize = size();
				T* tmp = new T[n];
				for (size_t i = 0; i < oldSize; i++)
				{
					tmp[i] = _start[i];
				}

				delete[] _start;

				_start = tmp;
				_finish = _start + oldSize;  //大小看起来没变，但更新地址
				_end_of_storage = _start + n;
			}
		}

		size_t capacity() const //在调用时不会修改类中的任何成员变量
		{
			return _end_of_storage - _start;
		}

		size_t size() const
		{
			return _finish - _start;
		}

		T& operator[](size_t i)  
		//操作非const的vector对象
		{
			assert(i < size());
			return _start[i];
		}

		const T& operator[](size_t i) const 
		//操作const的vector对象，且成员函数不会修改对象本身
		{
			assert(i < size());
			return _start[i];
		}

		void push_back(const T& x)
		{
			if (_finish == _end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}

			//*_finish = x;
			new (_finish) T(x);
			++_finish;
		}

		void pop_back()
		{
			assert(_finish > _start);
			--_finish;
			_finish->~T();
		}

		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 : capacity() * 2);
				pos = _start + len;
			}

			iterator it = _finish - 1;
			while (it >= pos)
			{
				*(it + 1) = *it;
				--it;
			}

			*pos = x;
			++_finish;
		}

		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);

			iterator it = pos + 1;
			while (it < _finish)
			{
				*(it - 1) = *it;
				++it;
			}

			--_finish;

			return pos;
		}

	private:
		iterator _start = nullptr;  //数据起始位置
		iterator _finish = nullptr;  //最后一个有效元素的下一个位置
		iterator _end_of_storage = nullptr;  //当前申请空间的结尾
	};
}

#c++##vector#