C++コンテナ--vector

vector
vectorは、可変サイズ配列のシーケンスコンテナを表すことができる.vectorは配列と同じ連続記憶空間を用いて要素を記憶する.次の表を使用してvectorの要素にアクセスでき、配列と同様に効率的です.配列と異なる点:vectorのサイズは動的に変更でき、そのサイズはコンテナによって自動的に処理され、配列は一定長になります.vector割り当て領域ポリシー:vectorは、実際に必要とされるストレージ領域よりもストレージ領域が大きいため、vectorが最後に挿入されるときに定数時間の複雑さで完了することを保証するために、可能な増加に適応するために追加の領域を割り当てます.他のダイナミックシーケンスコンテナ(deque,list)に比べてvectorは要素にランダムにアクセスする際により効率的であり、テールプラグとテール削除は比較的効率的である.しかし,末尾で挿入や削除を行わず,より効率的である.
インタフェース
構築:

vector();	//     
vector(size_type n, const value_type& val = value_type());	//       n val
vector(const vector& v);	//     
vector(InputIterator first, InputIterator last);	//             

反復器:

//          
begin();	// vector     
end();		// vector          
rbegin();	// vector    
rend();		// vector          
cbegin();	// const  
cend();

容量:

size();	//     
capacity();	//     
empty();	//   
void resize(size_type n, value_type val = value_type());	//         
void reserve(size_type n);	//       

注意:
capacityの増加はvsで1.5倍増加し、g++は2倍増加し、異なるバージョンのSTLシーケンステーブルの増容は異なるreserveが空間を開くだけを担当する可能性があり、どれだけの空間が必要かを知っていれば、reserveはvectorの増容欠陥を緩和することができ、reserveは現在の容量より小さく、reserveは何もしないでresizeが空間を開くときに初期化し、sizeに影響を与える.縮小sizeも含めて可能です
追加削除:

void push_back(const value_type& val);	//   
void pop_back();	//   
InputIterator find(InputIterator first, InputIterator last, const T& val);	//   ，     
iterator insert(iterator position, const value_type& val);	//  pos    
iterator erase(iterator position);	//   pos     
void swap(vector& v);	//     vector     
reference operator[](size_type n);	// []   ，     

注意:
findはアルゴリズム実装であり、メンバー関数ではなく、反復器が再カプセル化されており、異なるコンテナの反復器ではreferenceがT&の別名であるtypedefを使用することができ、STLのソースコードではreferenceがインタフェース統一を維持するためにpop_frontインタフェースは、効率が高いので、後でキューqueueを実現する下位構造ではvector iteratorを反復器に使用することはできません.
使用中の問題
反復器の無効化:
反復器が無効になったシーン:削除理由:現在のノードはすでに解放されており、解放ノードに対して++操作を実行することは、空のポインタを逆参照して解決することに相当する:関数の戻り値を削除すると次の反復器の位置に戻り、削除後に反復器キャパシタの無効を再取得する必要がある理由はすべてこれであり、解決方法も同じである.次の反復器の位置に戻り、再取得

#include  
#include  
#include  

int main() {
	int a[] = { 1, 2, 3, 4 };
	std::vector<int> v(a, a + sizeof(a) / sizeof(int));

	//   find  3     iterator    
	std::vector<int>::iterator pos = find(v.begin(), v.end(), 3);

	//   pos     ，  pos     。   
	pos = v.erase(pos);
	std::cout << *pos << std::endl; //          

	//  pos      ，  pos     。   
	// insert        ，   insert     
	//       ，   pos        ，           。   
	pos = find(v.begin(), v.end(), 3);
	pos = v.insert(pos, 30);
	std::cout << *pos << std::endl;	//          

	return 0;
}

インプリメンテーション
3つのポインタ制御を使用して、start(有効要素の開始)、finish(有効要素の終了)、end_of_storage(容量の終了)vectorの実現は比較的簡単で、具体的なコード分析を見つけます
ソースコード

#include 
#include 
#include 
template <class T>

class Vector {
public:
	typedef T* iterator;
	typedef const T* const_iterator;

	iterator begin() {
		return _start;
	}
	iterator end() {
		return _finish;
	}

	const_iterator cbegin() const {
		return _start;
	}
	const_iterator cend() const {
		return _finish;
	}

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

public:
	Vector()
		: _start(nullptr)
		, _finish(nullptr)
		, _endofStorage(nullptr) {}
	Vector(size_t n, const T& val = T()) 
		: _start(nullptr)
		, _finish(nullptr)
		, _endofStorage(nullptr) {
		reserve(n);
		while (n--)
		{
			push_back(val);
		}
	}

	//       Iterator    ，             [first,last]   Vector           
	//          ，     [first,last]             
	template <class InputIterator>
	Vector(InputIterator first, InputIterator last) {
		reserve(last - first);
		while (first != last)
		{
			push_back(*first);
			++first;
		}
	}

	Vector(const Vector<T>& vec) 
		: _start(nullptr)
		, _finish(nullptr)
		, _endofStorage(nullptr) {

		reserve(vec.capacity());
		iterator it = begin();
		const_iterator vit = vec.cbegin();
		while (vit != vec.cend())
		{
			*it++ = *vit++;
		}
		_finish = _start + vec.size();
		_endofStorage = _start + vec.capacity();	
	}
	Vector<T>& operator= (Vector<T> vec) {
		Swap(vec);
		return *this;
	}
	void reserve(size_t n) {
		if (n > capacity())
		{
			size_t Size = size();
			T* tmp = new T[n];

			//        memcpy
			if (_start)
			{
				for (size_t i = 0; i < Size; ++i)
					tmp[i] = _start[i];
			}
			// delete[] _start;
			_start = tmp;
			_finish = _start + Size;
			_endofStorage = _start + n;
		}
	}
	void resize(size_t n, const T& val = T()) {
		if (n < size())
		{
			_finish = _start + n;
		}
		if (n > capacity())
		{
			reserve(n);
		}
		iterator it = _finish;
		_finish = _start + n;
		while (it != _finish)
		{
			*it = val;
			++it;
		}
	}
	void Swap(Vector<T>& vec) {
		std::swap(_start, vec._start);
		std::swap(_finish, vec._finish);
		std::swap(_endofStorage, vec._endofStorage);	
	}

	void push_back(const T& val) {
		insert(end(), val);
	}
	void pop_back() {
		erase(end());
	}
	iterator insert(iterator pos, const T& val) {
		assert(pos <= _endofStorage);
		if (_finish == _endofStorage) {
			size_t Size = size();
			size_t new_capacity = capacity() == 0 ? 1 : capacity() * 2;
			reserve(new_capacity);
			pos = _start + Size;
		}
		iterator end = _finish - 1;
		while (end >= pos)
		{
			*(end + 1) = *end;
			--end;
		}
		*pos = val;
		++_finish;
		return pos;
	}

	//             ，                  
	iterator erase(iterator pos) {
		iterator begin = pos + 1;
		while (begin != _finish)
		{
			*(begin - 1) = *begin;
			++begin;
		}
		--_finish;
		return pos;
	}

	T& operator[](size_t pos) {
		return _start[pos];
	}

	void print() {
		for (auto& e : *this)
		{
			std::cout << e << " ";
		}
		std::cout << std::endl;
	}


private:
	iterator _start;
	iterator _finish;
	iterator _endofStorage;
};