#ベクターの使用法
java コース )
ベクトルと配列の最大の違いは、ベクトルではプログラマー自身が容量の問題を考慮する必要がないことです。ライブラリ自体は容量の動的な増加を実現しますが、配列 プログラマは、拡張を実行するために手動で拡張関数を記述する必要があります。Vector のシミュレーション実装
template <class T> class Vector { public: typedef T* Iterator; typedef const T* Iterator; Vector() :_start(NULL) ,_finish(NULL) ,_endOfStorage(NULL) {} void template<class T> PushBack(const T& x) { Iterator end = End(); Insert(end, x); } void Insert(Iterator& pos, const T& x) { size_t n = pos - _start; if (_finish == _endOfStorage) { size_t len = Capacity() == 0 ? 3 : Capacity()*2; Expand(len); } pos = _start+n; for (Iterator end = End(); end != pos; --end) { *end = *(end-1); } *pos = x; ++_finish; } Iterator End() { return _finish; } Iterator Begin() { return _start; } void Resize(size_t n, const T& val = T())//用Resize扩容时需要初始化空间,并且可以缩小容量 { if (n < Size()) { _finish = _start+n; } else { Reserve(n); size_t len = n-Size(); for (size_t i = 0; i < len; ++i) { PushBack(val); } } } void Reserve(size_t n)//不用初始化空间,直接增容 { Expand(n); } inline size_t Size() { return _finish-_start; } inline size_t Capacity() { return _endOfStorage-_start; } void Expand(size_t n) { const size_t size = Size(); const size_t capacity = Capacity(); if (n > capacity) { T* tmp = new T[n]; for (size_t i = 0; i < size; ++i) { tmp[i] = _start[i]; } delete[] _start; _start = tmp; _finish = _start+size; _endOfStorage = _start+n; } } T& operator[](size_t pos) { assert(pos < Size()); return _start[pos]; } const T& operator[](size_t pos) const { assert(pos < Size()); return _start[pos]; } protected: Iterator _start; //指向第一个元素所在节点 Iterator _finish; //指向最后一个元素所在节点的下一个节点 Iterator _endOfStorage; //可用内存空间的末尾节点 };
リストの使用
非連続ストレージ構造: リストは二重リンク リストです。構造、リンクされたリストの双方向の走査をサポートします。各ノードには、要素自体、前の要素を指すノード (prev)、次の要素を指すノード (next) の 3 つの情報が含まれます。 したがって、list は任意の位置のデータ要素に効率的にアクセス、挿入、削除できます。追加のポインターのメンテナンスが含まれるため、オーバーヘッドが比較的高くなります。List のシミュレーション実装
template<class T> class List { typedef __ListNode<T> Node; public: typedef __ListIterator<T, T&, T*> Iterator; typedef __ListIterator<T, const T&, const T*> ConstIterator; Iterator Begin() { return _head->_next; } Iterator End() { return _head; } ConstIterator Begin() const { return _head->_next; } ConstIterator End() const { return _head; } List() { _head = new Node(T()); _head->_next = _head; _head->_prev = _head; } // l2(l1) List(const List& l) { _head = new Node(T()); _head->_next = _head; _head->_prev = _head; ConstIterator it = l.Begin(); while (it != l.End()) { PushBack(*it); ++it; } } ~List() { Clear(); delete _head; _head = NULL; } void Clear() { Iterator it = Begin(); while (it != End()) { Node* del = it._node; ++it; delete del; } _head->_next = _head; _head->_prev = _head; } void PushBack(const T& x) { Insert(End(), x); } void PushFront(const T& x) { Insert(Begin(), x); } void PopBack() { Erase(--End()); } void PopFront() { Erase(Begin()); } void Insert(Iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* tmp = new Node(x); prev->_next = tmp; tmp->_prev = prev; tmp->_next = cur; cur->_prev = prev; } Iterator Erase(Iterator& pos) { assert(pos != End()); Node* prev = (pos._node)->_prev; Node* next = (pos._node)->_next; prev->_next = next; next->_prev = prev; delete pos._node; pos._node = prev; return Iterator(next); } protected: Node* _head; };
vector と list の違い
*Vector はランダムアクセス効率が高いですが、 in 挿入や削除(末尾を除く)の際にはデータを移動する必要があり、操作が簡単ではありません。 #リスト アクセスでは、リンクされたリスト全体を走査する必要があり、ランダム アクセスの効率は低くなります。ただし、ポインターの位置を変更するだけでデータの挿入と削除を行う方が便利です。 #リストは一方向、ベクトルは双方向です。 #vector 内の反復子は使用後無効になりますが、list 内の反復子は使用後も引き続き使用できます。以上がJavaのベクトルとリストの違いの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。