/elec/propeller-clock : contents of src/utility/vector at revision 57

: (revision 57)

To get this branch, use:

bzr branch
http://bzr.ed.am/elec/propeller-clock

/*	Copyright (C) 2004 Garrett A. Kajmowicz

	This file is part of the uClibc++ Library.

	This library is free software; you can redistribute it and/or
	modify it under the terms of the GNU Lesser General Public
	License as published by the Free Software Foundation; either
	version 2.1 of the License, or (at your option) any later version.

	This library is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
	Lesser General Public License for more details.

	You should have received a copy of the GNU Lesser General Public
	License along with this library; if not, write to the Free Software
	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

*/

#include <basic_definitions>
#include <memory>
#include <iterator>
#include <func_exception>
#include <algorithm>
#include <type_traits>


#ifndef __STD_HEADER_VECTOR
#define __STD_HEADER_VECTOR

#pragma GCC visibility push(default)

namespace std{

	template <class T, class Allocator = allocator<T> > class vector;
	template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
	template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
	template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
	template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
	template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
	template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
	template <class T, class Allocator> void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);

	template <class T, class Allocator> class _UCXXEXPORT vector {
	public:

		typedef typename Allocator::reference reference;
		typedef typename Allocator::const_reference const_reference;
		typedef typename Allocator::size_type size_type;
		typedef typename Allocator::difference_type difference_type;
		typedef typename Allocator::pointer pointer;
		typedef typename Allocator::const_pointer const_pointer;

		typedef T* iterator;
		typedef const T* const_iterator;
		typedef T value_type;
		typedef Allocator allocator_type;
		typedef std::reverse_iterator<iterator> reverse_iterator;
		typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

		explicit _UCXXEXPORT vector(const Allocator& al= Allocator()): data(0), //defaultValue(T()), 
			data_size(__UCLIBCXX_STL_BUFFER_SIZE__), elements(0), a(al)
		{
			data = a.allocate(data_size);
		}

		explicit _UCXXEXPORT vector(size_type n, const T& value = T(), const Allocator& al= Allocator()) : 
			data(0), data_size(0), elements(0), a(al)
		{
			data_size = n + __UCLIBCXX_STL_BUFFER_SIZE__;
			data = a.allocate(data_size);

			resize(n, value);
		}

		template <class InputIterator> _UCXXEXPORT 
			vector(InputIterator first, InputIterator last, const Allocator& al = Allocator()):
			data(0), data_size(__UCLIBCXX_STL_BUFFER_SIZE__), elements(0), a(al)
		{
			data = a.allocate(data_size);
			assign(first, last);
		}

		_UCXXEXPORT vector(const vector<T,Allocator>& x){
			a = x.a;

			elements  = x.elements;
			data_size = elements + __UCLIBCXX_STL_BUFFER_SIZE__;
			data = a.allocate(data_size);

			for(size_type i = 0; i < elements; i++){
				a.construct(data+i, x.data[i]);
			}	
		}

		_UCXXEXPORT ~vector();	//Below

		_UCXXEXPORT vector<T,Allocator>& operator=(const vector<T,Allocator>& x){
			if(&x == this){
				return *this;
			}

			reserve(x.elements);	//Make sure that we have enough actual memory


			//Copy as many elements as possible

			size_t minElements = elements;
			if(minElements > x.elements){
				minElements = x.elements;
			}
			for(size_t i = 0; i < minElements; ++i){
				data[i] = x.data[i];
			}

			//If we need to add new elements
			if(elements < x.elements){
				for(size_t i = elements; i< x.elements; ++i){
					a.construct(data+i, x.data[i]);
					++elements;
				}
			}

			if(elements > x.elements){
				downsize(x.elements);
			}

			return *this;
		}

		template <class InputIterator> _UCXXEXPORT void assign(InputIterator first, InputIterator last){
			clear();
			insert(begin(), first, last);
		}

		template <class Size, class U> _UCXXEXPORT void assign(Size n, const U& u = U()){
			clear();
			resize(n, u);
		}

		inline allocator_type get_allocator() const{
			return a;
		}

		inline iterator begin(){
			return data;
		}

		inline const_iterator begin() const{
			return data;
		}

		inline iterator end(){
			return (data + elements);
		}

		inline const_iterator end() const{
			return (data + elements);
		}

		inline reverse_iterator rbegin(){
			return reverse_iterator(end());
		}

		inline const_reverse_iterator rbegin() const{
			return const_reverse_iterator(end());
		}

		inline reverse_iterator rend(){
			return reverse_iterator(begin());
		}

		inline const_reverse_iterator rend() const{
			return const_reverse_iterator(begin());
		}

		inline size_type size() const{
			return elements;
		}

		_UCXXEXPORT size_type max_size() const{
			return ((size_type)(-1)) / sizeof(T);
		}

		void downsize(size_type sz);
		void resize(size_type sz, const T & c = T());

		inline size_type capacity() const{
			return data_size;
		}

		inline bool empty() const{
			return (size() == 0);
		}

		void reserve(size_type n);

		inline reference operator[](size_type n){
			return data[n];
		}

		inline const_reference operator[](size_type n) const{
			return data[n];
		}

		_UCXXEXPORT const_reference at(size_type n) const{
			if(n >= elements){
				__throw_out_of_range("Invalid subscript");
			}
			return data[n];
		}

		_UCXXEXPORT reference at(size_type n){
			if(n >= elements){
				__throw_out_of_range("Invalid subscript");
			}
			return data[n];
		}

		inline reference front(){
			return data[0];
		}

		inline const_reference front() const{
			return data[0];
		}

		inline reference back(){
			return data[ size() - 1];
		}

		inline const_reference back() const{
			return data[ size() - 1 ];
		}

		inline void push_back(const T& x){
			resize( size() + 1, x);
		}

		inline void pop_back(){
			downsize(size() - 1);
		}

		_UCXXEXPORT iterator insert(iterator position, const T& x = T()){
			size_type index = position - data;
			resize(size() + 1, x);
			for(size_type i = elements - 1; i > index; --i){
				data[i] = data[i-1];
			}
			data[index] = x;
			return (data + index);
		}

		_UCXXEXPORT void _insert_fill(iterator position, size_type n, const T & x){
			size_type index = position - data;
			resize(size() + n, x);

			for(size_type i = elements -1; (i > (index+n-1)); --i){
				data[i] = data[i-n];
			}
			for(size_type i = 0; i < n; i++){
				data[i + index]  = x;
			}
		}

		template <class InputIterator> _UCXXEXPORT 
			void _insert_from_iterator(iterator position, InputIterator first, InputIterator last)
		{
			T temp;
			while(first !=last){
				temp = *first;
				position = insert(position, temp);
				++position;
				++first;
			}
		}

		template <class InputIterator>
			inline void _dispatch_insert(iterator position, InputIterator first, InputIterator last, __true_type)
		{
			_insert_fill(position, first, last);
		}

		template <class InputIterator>
			inline void _dispatch_insert(iterator position, InputIterator first, InputIterator last, __false_type)
		{
				_insert_from_iterator(position, first, last);
		}

		inline void insert(iterator position, size_type n, const T& x ){
			_insert_fill(position, n, x);
		}

		template <class InputIterator> inline void insert(iterator position, InputIterator first, InputIterator last){
			typedef typename __is_integer<InputIterator>::value __some_type;
			_dispatch_insert(position, first, last, __some_type());
		}

		_UCXXEXPORT iterator erase(iterator position){
			size_type index = position - data;
			for(size_type i = index; i < (elements - 1); ++i){
				data[i] = data[i+1];
			}
			downsize(size() - 1);
			return (data + index);
		}

		_UCXXEXPORT iterator erase(iterator first, iterator last){
			size_type index = first - data;
			size_type width = last - first;
			for(size_type i = index; i < (elements - width) ;++i){
				data[i] = data[i+width];
			}
			downsize(size() - width);
			return (data + index);
		}

		_UCXXEXPORT void swap(vector<T,Allocator>& v){
			if(this == &v){		//Avoid dv.swap(v)
				return;
			}
			T* ptr;
			size_type temp;

			//Swap pointers first
			ptr = data;
			data = v.data;
			v.data  = ptr;

			//Swap element counts
			temp = elements;
			elements = v.elements;
			v.elements = temp;

			//Swap data size
			temp = data_size;
			data_size = v.data_size;
			v.data_size = temp;
		}

		_UCXXEXPORT void clear(){
			downsize(0);
		}

	protected:
		T* data;
		size_type data_size;
		size_type elements;
		Allocator a;
	};



	//Here go template instantiations

	template<class T, class Allocator> _UCXXEXPORT vector<T, Allocator>::~vector(){
		for(size_t i = 0; i < elements; ++i){
			a.destroy(data + i);
		}
		a.deallocate(data, data_size);
	}


	template<class T, class Allocator> _UCXXEXPORT void vector<T, Allocator>::reserve(size_type n){
		if(n > data_size){              //We never shrink...
			T * temp_ptr = data;
			size_type temp_size = data_size;

			data_size = n;
			data = a.allocate(data_size);

			for(size_type i = 0; i<elements; ++i){
				a.construct(data+i, temp_ptr[i]);
				a.destroy(temp_ptr+i);
			}
			a.deallocate(temp_ptr, temp_size);
		}
	}

	template<class T, class Allocator> _UCXXEXPORT void vector<T, Allocator>::resize(size_type sz, const T & c){
		if(sz > elements){      //Need to actually call constructor
			if(sz > data_size){
				reserve(sz + __UCLIBCXX_STL_BUFFER_SIZE__);
			}

			for(size_type i = elements; i<sz ; ++i){
				a.construct(data+i, c);
			}
			elements = sz;
		}else{
			downsize(sz);
		}
	}

	template<class T, class Allocator> _UCXXEXPORT void vector<T, Allocator>::downsize(size_type sz){
		if(sz < elements){      //Actually are downsizing
			for(size_t i = sz; i< elements; ++i){
				a.destroy(data+i);
			}
			elements = sz;
		}
	}


#ifndef __UCLIBCXX_COMPILE_VECTOR__
#ifdef __UCLIBCXX_EXPAND_VECTOR_BASIC__


#ifdef __UCLIBCXX_EXPAND_CONSTRUCTORS_DESTRUCTORS__
	template<> _UCXXEXPORT vector<char, allocator<char> >::vector(const allocator<char>& al);
	template<> _UCXXEXPORT vector<char, allocator<char> >::vector(size_type n, const char & value, const allocator<char> & al);

	template<> _UCXXEXPORT vector<char, allocator<char> >::~vector();
	template<> _UCXXEXPORT vector<unsigned char, allocator<unsigned char> >::~vector();

#endif //__UCLIBCXX_EXPAND_CONSTRUCTORS_DESTRUCTORS__

	template<> _UCXXEXPORT void vector<char, allocator<char> >::reserve(size_type n);
	template<> _UCXXEXPORT void vector<unsigned char, allocator<unsigned char> >::reserve(size_type n);
	template<> _UCXXEXPORT void vector<short int, allocator<short int> >::reserve(size_type n);
	template<> _UCXXEXPORT void vector<unsigned short int, allocator<unsigned short int> >::reserve(size_type n);
	template<> _UCXXEXPORT void vector<int, allocator<int> >::reserve(size_type n);
	template<> _UCXXEXPORT void vector<unsigned int, allocator<unsigned int> >::reserve(size_type n);
	template<> _UCXXEXPORT void vector<long int, allocator<long int> >::reserve(size_type n);
	template<> _UCXXEXPORT void vector<unsigned long int, allocator<unsigned long int> >::reserve(size_type n);
	template<> _UCXXEXPORT void vector<float, allocator<float> >::reserve(size_type n);
	template<> _UCXXEXPORT void vector<double, allocator<double> >::reserve(size_type n);
	template<> _UCXXEXPORT void vector<bool, allocator<bool> >::reserve(size_type n);

	template<> _UCXXEXPORT void vector<char, allocator<char> >::resize(size_type sz, const char & c);
	template<> _UCXXEXPORT void
		vector<unsigned char, allocator<unsigned char> >::resize(size_type sz, const unsigned char & c);
	template<> _UCXXEXPORT void vector<short int, allocator<short int> >::resize(size_type sz, const short & c);
	template<> _UCXXEXPORT void
		vector<unsigned short int, allocator<unsigned short int> >::resize(size_type sz, const unsigned short int & c);
	template<> _UCXXEXPORT void vector<int, allocator<int> >::resize(size_type sz, const int & c);
	template<> _UCXXEXPORT void vector<unsigned int, allocator<unsigned int> >::resize(size_type sz, const unsigned int & c);
	template<> _UCXXEXPORT void vector<long int, allocator<long int> >::resize(size_type sz, const long int & c);
	template<> _UCXXEXPORT void
		vector<unsigned long int, allocator<unsigned long int> >::resize(size_type sz, const unsigned long int & c);
	template<> _UCXXEXPORT void vector<float, allocator<float> >::resize(size_type sz, const float & c);
	template<> _UCXXEXPORT void vector<double, allocator<double> >::resize(size_type sz, const double & c);
	template<> _UCXXEXPORT void vector<bool, allocator<bool> >::resize(size_type sz, const bool & c);

#elif defined __UCLIBCXX_EXPAND_STRING_CHAR__

#ifdef __UCLIBCXX_EXPAND_CONSTRUCTORS_DESTRUCTORS__

	template<> _UCXXEXPORT vector<char, allocator<char> >::vector(const allocator<char>& al);
	template<> _UCXXEXPORT vector<char, allocator<char> >::vector(size_type n, const char & value, const allocator<char> & al);
	template<> _UCXXEXPORT vector<char, allocator<char> >::~vector();

#endif

	template<> _UCXXEXPORT void vector<char, allocator<char> >::reserve(size_type n);
	template<> _UCXXEXPORT void vector<char, allocator<char> >::resize(size_type sz, const char & c);

#endif
#endif



	template <class T, class Allocator> _UCXXEXPORT bool
		operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y)
	{
		if(x.size() !=y.size() ){
			return false;
		}
		for(size_t i = 0; i < x.size(); ++i){
			if(x[i] != y[i]){
				return false;
			}
		}
		return true;
	}

	template <class T, class Allocator> _UCXXEXPORT bool
		operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y)
	{
		less<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
                return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
	}
	template <class T, class Allocator> _UCXXEXPORT bool
		operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y)
	{
		return !(x == y);
	}
	template <class T, class Allocator> _UCXXEXPORT bool
		operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y)
	{
		greater<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
                return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
	}
	template <class T, class Allocator> _UCXXEXPORT bool
		operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y)
	{
		greater_equal<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
                return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
	}
	template <class T, class Allocator> _UCXXEXPORT bool
		operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y)
	{
		less_equal<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
                return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
	}

	template <class T, class Allocator> _UCXXEXPORT void swap(vector<T,Allocator>& x, vector<T,Allocator>& y){
		x.swap(y);
	}

}

#pragma GCC visibility pop

#endif


57 by edam added ulibc	1	/* Copyright (C) 2004 Garrett A. Kajmowicz
	2
	3	This file is part of the uClibc++ Library.
	4
	5	This library is free software; you can redistribute it and/or
	6	modify it under the terms of the GNU Lesser General Public
	7	License as published by the Free Software Foundation; either
	8	version 2.1 of the License, or (at your option) any later version.
	9
	10	This library is distributed in the hope that it will be useful,
	11	but WITHOUT ANY WARRANTY; without even the implied warranty of
	12	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	13	Lesser General Public License for more details.
	14
	15	You should have received a copy of the GNU Lesser General Public
	16	License along with this library; if not, write to the Free Software
	17	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
	18
	19	*/
	20
	21	#include <basic_definitions>
	22	#include <memory>
	23	#include <iterator>
	24	#include <func_exception>
	25	#include <algorithm>
	26	#include <type_traits>
	27
	28
	29	#ifndef __STD_HEADER_VECTOR
	30	#define __STD_HEADER_VECTOR
	31
	32	#pragma GCC visibility push(default)
	33
	34	namespace std{
	35
	36	template <class T, class Allocator = allocator<T> > class vector;
	37	template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
	38	template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
	39	template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
	40	template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
	41	template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
	42	template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
	43	template <class T, class Allocator> void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);
	44
	45	template <class T, class Allocator> class _UCXXEXPORT vector {
	46	public:
	47
	48	typedef typename Allocator::reference reference;
	49	typedef typename Allocator::const_reference const_reference;
	50	typedef typename Allocator::size_type size_type;
	51	typedef typename Allocator::difference_type difference_type;
	52	typedef typename Allocator::pointer pointer;
	53	typedef typename Allocator::const_pointer const_pointer;
	54
	55	typedef T* iterator;
	56	typedef const T* const_iterator;
	57	typedef T value_type;
	58	typedef Allocator allocator_type;
	59	typedef std::reverse_iterator<iterator> reverse_iterator;
	60	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
	61
	62	explicit _UCXXEXPORT vector(const Allocator& al= Allocator()): data(0), //defaultValue(T()),
	63	data_size(__UCLIBCXX_STL_BUFFER_SIZE__), elements(0), a(al)
	64	{
65	data = a.allocate(data_size);
66	}
67
68	explicit _UCXXEXPORT vector(size_type n, const T& value = T(), const Allocator& al= Allocator()) :
69	data(0), data_size(0), elements(0), a(al)
70	{
71	data_size = n + __UCLIBCXX_STL_BUFFER_SIZE__;
72	data = a.allocate(data_size);
73
74	resize(n, value);
75	}
76
77	template <class InputIterator> _UCXXEXPORT
78	vector(InputIterator first, InputIterator last, const Allocator& al = Allocator()):
79	data(0), data_size(__UCLIBCXX_STL_BUFFER_SIZE__), elements(0), a(al)
80	{
81	data = a.allocate(data_size);
82	assign(first, last);
83	}
84
85	_UCXXEXPORT vector(const vector<T,Allocator>& x){
86	a = x.a;
87
88	elements = x.elements;
89	data_size = elements + __UCLIBCXX_STL_BUFFER_SIZE__;
90	data = a.allocate(data_size);
91
92	for(size_type i = 0; i < elements; i++){
93	a.construct(data+i, x.data[i]);
94	}
95	}
96
97	_UCXXEXPORT ~vector(); //Below
98
99	_UCXXEXPORT vector<T,Allocator>& operator=(const vector<T,Allocator>& x){
100	if(&x == this){
101	return *this;
102	}
103
104	reserve(x.elements); //Make sure that we have enough actual memory
105
106
107	//Copy as many elements as possible
108
109	size_t minElements = elements;
110	if(minElements > x.elements){
111	minElements = x.elements;
112	}
113	for(size_t i = 0; i < minElements; ++i){
114	data[i] = x.data[i];
115	}
116
117	//If we need to add new elements
118	if(elements < x.elements){
119	for(size_t i = elements; i< x.elements; ++i){
120	a.construct(data+i, x.data[i]);
121	++elements;
122	}
123	}
124
125	if(elements > x.elements){
126	downsize(x.elements);
127	}
128
129	return *this;
130	}
131
132	template <class InputIterator> _UCXXEXPORT void assign(InputIterator first, InputIterator last){
133	clear();
134	insert(begin(), first, last);
135	}
136
137	template <class Size, class U> _UCXXEXPORT void assign(Size n, const U& u = U()){
138	clear();
139	resize(n, u);
140	}
141
142	inline allocator_type get_allocator() const{
143	return a;
144	}
145
146	inline iterator begin(){
147	return data;
148	}
149
150	inline const_iterator begin() const{
151	return data;
152	}
153
154	inline iterator end(){
155	return (data + elements);
156	}
157
158	inline const_iterator end() const{
159	return (data + elements);
160	}
161
162	inline reverse_iterator rbegin(){
163	return reverse_iterator(end());
164	}
165
166	inline const_reverse_iterator rbegin() const{
167	return const_reverse_iterator(end());
168	}
169
170	inline reverse_iterator rend(){
171	return reverse_iterator(begin());
172	}
173
174	inline const_reverse_iterator rend() const{
175	return const_reverse_iterator(begin());
176	}
177
178	inline size_type size() const{
179	return elements;
180	}
181
182	_UCXXEXPORT size_type max_size() const{
183	return ((size_type)(-1)) / sizeof(T);
184	}
185
186	void downsize(size_type sz);
187	void resize(size_type sz, const T & c = T());
188
189	inline size_type capacity() const{
190	return data_size;
191	}
192
193	inline bool empty() const{
194	return (size() == 0);
195	}
196
197	void reserve(size_type n);
198
199	inline reference operator[](size_type n){
200	return data[n];
201	}
202
203	inline const_reference operator[](size_type n) const{
204	return data[n];
205	}
206
207	_UCXXEXPORT const_reference at(size_type n) const{
208	if(n >= elements){
209	__throw_out_of_range("Invalid subscript");
210	}
211	return data[n];
212	}
213
214	_UCXXEXPORT reference at(size_type n){
215	if(n >= elements){
216	__throw_out_of_range("Invalid subscript");
217	}
218	return data[n];
219	}
220
221	inline reference front(){
222	return data[0];
223	}
224
225	inline const_reference front() const{
226	return data[0];
227	}
228
229	inline reference back(){
230	return data[ size() - 1];
231	}
232
233	inline const_reference back() const{
234	return data[ size() - 1 ];
235	}
236
237	inline void push_back(const T& x){
238	resize( size() + 1, x);
239	}
240
241	inline void pop_back(){
242	downsize(size() - 1);
243	}
244
245	_UCXXEXPORT iterator insert(iterator position, const T& x = T()){
246	size_type index = position - data;
247	resize(size() + 1, x);
248	for(size_type i = elements - 1; i > index; --i){
249	data[i] = data[i-1];
250	}
251	data[index] = x;
252	return (data + index);
253	}
254
255	_UCXXEXPORT void _insert_fill(iterator position, size_type n, const T & x){
256	size_type index = position - data;
257	resize(size() + n, x);
258
259	for(size_type i = elements -1; (i > (index+n-1)); --i){
260	data[i] = data[i-n];
261	}
262	for(size_type i = 0; i < n; i++){
263	data[i + index] = x;
264	}
265	}
266
267	template <class InputIterator> _UCXXEXPORT
268	void _insert_from_iterator(iterator position, InputIterator first, InputIterator last)
269	{
270	T temp;
271	while(first !=last){
272	temp = *first;
273	position = insert(position, temp);
274	++position;
275	++first;
276	}
277	}
278
279	template <class InputIterator>
280	inline void _dispatch_insert(iterator position, InputIterator first, InputIterator last, __true_type)
281	{
282	_insert_fill(position, first, last);
283	}
284
285	template <class InputIterator>
286	inline void _dispatch_insert(iterator position, InputIterator first, InputIterator last, __false_type)
287	{
288	_insert_from_iterator(position, first, last);
289	}
290
291	inline void insert(iterator position, size_type n, const T& x ){
292	_insert_fill(position, n, x);
293	}
294
295	template <class InputIterator> inline void insert(iterator position, InputIterator first, InputIterator last){
296	typedef typename __is_integer<InputIterator>::value __some_type;
297	_dispatch_insert(position, first, last, __some_type());
298	}
299
300	_UCXXEXPORT iterator erase(iterator position){
301	size_type index = position - data;
302	for(size_type i = index; i < (elements - 1); ++i){
303	data[i] = data[i+1];
304	}
305	downsize(size() - 1);
306	return (data + index);
307	}
308
309	_UCXXEXPORT iterator erase(iterator first, iterator last){
310	size_type index = first - data;
311	size_type width = last - first;
312	for(size_type i = index; i < (elements - width) ;++i){
313	data[i] = data[i+width];
314	}
315	downsize(size() - width);
316	return (data + index);
317	}
318
319	_UCXXEXPORT void swap(vector<T,Allocator>& v){
320	if(this == &v){ //Avoid dv.swap(v)
321	return;
322	}
323	T* ptr;
324	size_type temp;
325
326	//Swap pointers first
327	ptr = data;
328	data = v.data;
329	v.data = ptr;
330
331	//Swap element counts
332	temp = elements;
333	elements = v.elements;
334	v.elements = temp;
335
336	//Swap data size
337	temp = data_size;
338	data_size = v.data_size;
339	v.data_size = temp;
340	}
341
342	_UCXXEXPORT void clear(){
343	downsize(0);
344	}
345
346	protected:
347	T* data;
348	size_type data_size;
349	size_type elements;
350	Allocator a;
351	};
352
353
354
355	//Here go template instantiations
356
357	template<class T, class Allocator> _UCXXEXPORT vector<T, Allocator>::~vector(){
358	for(size_t i = 0; i < elements; ++i){
359	a.destroy(data + i);
360	}
361	a.deallocate(data, data_size);
362	}
363
364
365	template<class T, class Allocator> _UCXXEXPORT void vector<T, Allocator>::reserve(size_type n){
366	if(n > data_size){ //We never shrink...
367	T * temp_ptr = data;
368	size_type temp_size = data_size;
369
370	data_size = n;
371	data = a.allocate(data_size);
372
373	for(size_type i = 0; i<elements; ++i){
374	a.construct(data+i, temp_ptr[i]);
375	a.destroy(temp_ptr+i);
376	}
377	a.deallocate(temp_ptr, temp_size);
378	}
379	}
380
381	template<class T, class Allocator> _UCXXEXPORT void vector<T, Allocator>::resize(size_type sz, const T & c){
382	if(sz > elements){ //Need to actually call constructor
383	if(sz > data_size){
384	reserve(sz + __UCLIBCXX_STL_BUFFER_SIZE__);
385	}
386
387	for(size_type i = elements; i<sz ; ++i){
388	a.construct(data+i, c);
389	}
390	elements = sz;
391	}else{
392	downsize(sz);
393	}
394	}
395
396	template<class T, class Allocator> _UCXXEXPORT void vector<T, Allocator>::downsize(size_type sz){
397	if(sz < elements){ //Actually are downsizing
398	for(size_t i = sz; i< elements; ++i){
399	a.destroy(data+i);
400	}
401	elements = sz;
402	}
403	}
404
405
406	#ifndef __UCLIBCXX_COMPILE_VECTOR__
407	#ifdef __UCLIBCXX_EXPAND_VECTOR_BASIC__
408
409
410	#ifdef __UCLIBCXX_EXPAND_CONSTRUCTORS_DESTRUCTORS__
411	template<> _UCXXEXPORT vector<char, allocator<char> >::vector(const allocator<char>& al);
412	template<> _UCXXEXPORT vector<char, allocator<char> >::vector(size_type n, const char & value, const allocator<char> & al);
413
414	template<> _UCXXEXPORT vector<char, allocator<char> >::~vector();
415	template<> _UCXXEXPORT vector<unsigned char, allocator<unsigned char> >::~vector();
416
417	#endif //__UCLIBCXX_EXPAND_CONSTRUCTORS_DESTRUCTORS__
418
419	template<> _UCXXEXPORT void vector<char, allocator<char> >::reserve(size_type n);
420	template<> _UCXXEXPORT void vector<unsigned char, allocator<unsigned char> >::reserve(size_type n);
421	template<> _UCXXEXPORT void vector<short int, allocator<short int> >::reserve(size_type n);
422	template<> _UCXXEXPORT void vector<unsigned short int, allocator<unsigned short int> >::reserve(size_type n);
423	template<> _UCXXEXPORT void vector<int, allocator<int> >::reserve(size_type n);
424	template<> _UCXXEXPORT void vector<unsigned int, allocator<unsigned int> >::reserve(size_type n);
425	template<> _UCXXEXPORT void vector<long int, allocator<long int> >::reserve(size_type n);
426	template<> _UCXXEXPORT void vector<unsigned long int, allocator<unsigned long int> >::reserve(size_type n);
427	template<> _UCXXEXPORT void vector<float, allocator<float> >::reserve(size_type n);
428	template<> _UCXXEXPORT void vector<double, allocator<double> >::reserve(size_type n);
429	template<> _UCXXEXPORT void vector<bool, allocator<bool> >::reserve(size_type n);
430
431	template<> _UCXXEXPORT void vector<char, allocator<char> >::resize(size_type sz, const char & c);
432	template<> _UCXXEXPORT void
433	vector<unsigned char, allocator<unsigned char> >::resize(size_type sz, const unsigned char & c);
434	template<> _UCXXEXPORT void vector<short int, allocator<short int> >::resize(size_type sz, const short & c);
435	template<> _UCXXEXPORT void
436	vector<unsigned short int, allocator<unsigned short int> >::resize(size_type sz, const unsigned short int & c);
437	template<> _UCXXEXPORT void vector<int, allocator<int> >::resize(size_type sz, const int & c);
438	template<> _UCXXEXPORT void vector<unsigned int, allocator<unsigned int> >::resize(size_type sz, const unsigned int & c);
439	template<> _UCXXEXPORT void vector<long int, allocator<long int> >::resize(size_type sz, const long int & c);
440	template<> _UCXXEXPORT void
441	vector<unsigned long int, allocator<unsigned long int> >::resize(size_type sz, const unsigned long int & c);
442	template<> _UCXXEXPORT void vector<float, allocator<float> >::resize(size_type sz, const float & c);
443	template<> _UCXXEXPORT void vector<double, allocator<double> >::resize(size_type sz, const double & c);
444	template<> _UCXXEXPORT void vector<bool, allocator<bool> >::resize(size_type sz, const bool & c);
445
446	#elif defined __UCLIBCXX_EXPAND_STRING_CHAR__
447
448	#ifdef __UCLIBCXX_EXPAND_CONSTRUCTORS_DESTRUCTORS__
449
450	template<> _UCXXEXPORT vector<char, allocator<char> >::vector(const allocator<char>& al);
451	template<> _UCXXEXPORT vector<char, allocator<char> >::vector(size_type n, const char & value, const allocator<char> & al);
452	template<> _UCXXEXPORT vector<char, allocator<char> >::~vector();
453
454	#endif
455
456	template<> _UCXXEXPORT void vector<char, allocator<char> >::reserve(size_type n);
457	template<> _UCXXEXPORT void vector<char, allocator<char> >::resize(size_type sz, const char & c);
458
459	#endif
460	#endif
461
462
463
464	template <class T, class Allocator> _UCXXEXPORT bool
465	operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y)
466	{
467	if(x.size() !=y.size() ){
468	return false;
469	}
470	for(size_t i = 0; i < x.size(); ++i){
471	if(x[i] != y[i]){
472	return false;
473	}
474	}
475	return true;
476	}
477
478	template <class T, class Allocator> _UCXXEXPORT bool
479	operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y)
480	{
481	less<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
482	return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
483	}
484	template <class T, class Allocator> _UCXXEXPORT bool
485	operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y)
486	{
487	return !(x == y);
488	}
489	template <class T, class Allocator> _UCXXEXPORT bool
490	operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y)
491	{
492	greater<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
493	return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
494	}
495	template <class T, class Allocator> _UCXXEXPORT bool
496	operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y)
497	{
498	greater_equal<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
499	return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
500	}
501	template <class T, class Allocator> _UCXXEXPORT bool
502	operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y)
503	{
504	less_equal<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
505	return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
506	}
507
508	template <class T, class Allocator> _UCXXEXPORT void swap(vector<T,Allocator>& x, vector<T,Allocator>& y){
509	x.swap(y);
510	}
511
512	}
513
514	#pragma GCC visibility pop
515
516	#endif
517