diff options
Diffstat (limited to 'libstdc++/stl/vector.h')
-rw-r--r-- | libstdc++/stl/vector.h | 544 |
1 files changed, 544 insertions, 0 deletions
diff --git a/libstdc++/stl/vector.h b/libstdc++/stl/vector.h new file mode 100644 index 00000000000..bb6a404766b --- /dev/null +++ b/libstdc++/stl/vector.h @@ -0,0 +1,544 @@ +/* + * + * Copyright (c) 1994 + * Hewlett-Packard Company + * + * Permission to use, copy, modify, distribute and sell this software + * and its documentation for any purpose is hereby granted without fee, + * provided that the above copyright notice appear in all copies and + * that both that copyright notice and this permission notice appear + * in supporting documentation. Hewlett-Packard Company makes no + * representations about the suitability of this software for any + * purpose. It is provided "as is" without express or implied warranty. + * + * + * Copyright (c) 1996 + * Silicon Graphics Computer Systems, Inc. + * + * Permission to use, copy, modify, distribute and sell this software + * and its documentation for any purpose is hereby granted without fee, + * provided that the above copyright notice appear in all copies and + * that both that copyright notice and this permission notice appear + * in supporting documentation. Silicon Graphics makes no + * representations about the suitability of this software for any + * purpose. It is provided "as is" without express or implied warranty. + */ + +#ifndef __SGI_STL_VECTOR_H +#define __SGI_STL_VECTOR_H + +#include <stddef.h> +#include <algobase.h> +#include <alloc.h> + +template <class T, class Alloc = alloc> +class vector { +public: + typedef T value_type; + typedef value_type* pointer; + typedef value_type* iterator; + typedef const value_type* const_iterator; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef reverse_iterator<const_iterator, value_type, const_reference, + difference_type> const_reverse_iterator; + typedef reverse_iterator<iterator, value_type, reference, difference_type> + reverse_iterator; +protected: + typedef simple_alloc<value_type, Alloc> data_allocator; + iterator start; + iterator finish; + iterator end_of_storage; + void insert_aux(iterator position, const T& x); + void deallocate() { + if (start) data_allocator::deallocate(start, end_of_storage - start); + } +public: + iterator begin() { return start; } + const_iterator begin() const { return start; } + iterator end() { return finish; } + const_iterator end() const { return finish; } + reverse_iterator rbegin() { return reverse_iterator(end()); } + const_reverse_iterator rbegin() const { + return const_reverse_iterator(end()); + } + reverse_iterator rend() { return reverse_iterator(begin()); } + const_reverse_iterator rend() const { + return const_reverse_iterator(begin()); + } + size_type size() const { return size_type(end() - begin()); } + size_type max_size() const { return size_type(-1); } + size_type capacity() const { return size_type(end_of_storage - begin()); } + bool empty() const { return begin() == end(); } + reference operator[](size_type n) { return *(begin() + n); } + const_reference operator[](size_type n) const { return *(begin() + n); } + vector() : start(0), finish(0), end_of_storage(0) {} + vector(size_type n, const T& value) { + start = allocate_and_fill(n, value); + finish = start + n; + end_of_storage = finish; + } + explicit vector(size_type n) { + start = allocate_and_fill(n, T()); + finish = start + n; + end_of_storage = finish; + } + vector(const vector<T, Alloc>& x) { + start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end()); + finish = start + (x.end() - x.begin()); + end_of_storage = finish; + } +#ifdef __STL_MEMBER_TEMPLATES + template <class InputIterator> + vector(InputIterator first, InputIterator last) : + start(0), finish(0), end_of_storage(0) { + range_initialize(first, last, iterator_category(first)); + } +#else /* __STL_MEMBER_TEMPLATES */ + vector(const_iterator first, const_iterator last) { + size_type n = 0; + distance(first, last, n); + start = allocate_and_copy(n, first, last); + finish = start + n; + end_of_storage = finish; + } +#endif /* __STL_MEMBER_TEMPLATES */ + ~vector() { + destroy(start, finish); + deallocate(); + } + vector<T, Alloc>& operator=(const vector<T, Alloc>& x); + void reserve(size_type n) { + if (capacity() < n) { + const size_type old_size = size(); + const iterator tmp = allocate_and_copy(n, start, finish); + destroy(start, finish); + deallocate(); + start = tmp; + finish = tmp + old_size; + end_of_storage = start + n; + } + } + reference front() { return *begin(); } + const_reference front() const { return *begin(); } + reference back() { return *(end() - 1); } + const_reference back() const { return *(end() - 1); } + void push_back(const T& x) { + if (finish != end_of_storage) { + construct(finish, x); + ++finish; + } else + insert_aux(end(), x); + } + void swap(vector<T, Alloc>& x) { + ::swap(start, x.start); + ::swap(finish, x.finish); + ::swap(end_of_storage, x.end_of_storage); + } + iterator insert(iterator position, const T& x) { + size_type n = position - begin(); + if (finish != end_of_storage && position == end()) { + construct(finish, x); + ++finish; + } else + insert_aux(position, x); + return begin() + n; + } + iterator insert(iterator position) { return insert(position, T()); } +#ifdef __STL_MEMBER_TEMPLATES + template <class InputIterator> + void insert(iterator position, InputIterator first, InputIterator last) { + range_insert(position, first, last, iterator_category(first)); + } +#else /* __STL_MEMBER_TEMPLATES */ + void insert(iterator position, + const_iterator first, const_iterator last); +#endif /* __STL_MEMBER_TEMPLATES */ + void insert (iterator position, size_type n, const T& x); + void pop_back() { + --finish; + destroy(finish); + } + void erase(iterator position) { + if (position + 1 != end()) + copy(position + 1, finish, position); + --finish; + destroy(finish); + } + void erase(iterator first, iterator last) { + iterator i = copy(last, finish, first); + destroy(i, finish); + finish = finish - (last - first); + } + void resize(size_type new_size, const T& x) { + if (new_size < size()) + erase(begin() + new_size, end()); + else + insert(end(), new_size - size(), x); + } + void resize(size_type new_size) { resize(new_size, T()); } + void clear() { erase(begin(), end()); } + +protected: + iterator allocate_and_fill(size_type n, const T& x) { + iterator result = data_allocator::allocate(n); +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + uninitialized_fill_n(result, n, x); + return result; +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + data_allocator::deallocate(result, n); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + } + +#ifdef __STL_MEMBER_TEMPLATES + template <class ForwardIterator> + iterator allocate_and_copy(size_type n, + ForwardIterator first, ForwardIterator last) { + iterator result = data_allocator::allocate(n); +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + uninitialized_copy(first, last, result); + return result; +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + data_allocator::deallocate(result, n); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + } +#else /* __STL_MEMBER_TEMPLATES */ + iterator allocate_and_copy(size_type n, + const_iterator first, const_iterator last) { + iterator result = data_allocator::allocate(n); +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + uninitialized_copy(first, last, result); + return result; +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + data_allocator::deallocate(result, n); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + } +#endif /* __STL_MEMBER_TEMPLATES */ + + +#ifdef __STL_MEMBER_TEMPLATES + template <class InputIterator> + void range_initialize(InputIterator first, InputIterator last, + input_iterator_tag) { + for ( ; first != last; ++first) + push_back(*first); + } + + // This function is only called by the constructor. We have to worry + // about resource leaks, but not about maintaining invariants. + template <class ForwardIterator> + void range_initialize(ForwardIterator first, ForwardIterator last, + forward_iterator_tag) { + size_type n = 0; + distance(first, last, n); + start = allocate_and_copy(n, first, last); + finish = start + n; + end_of_storage = finish; + } + + template <class BidirectionalIterator> + void range_initialize(BidirectionalIterator first, + BidirectionalIterator last, + bidirectional_iterator_tag) { + range_initialize(first, last, forward_iterator_tag()); + } + + template <class RandomAccessIterator> + void range_initialize(RandomAccessIterator first, + RandomAccessIterator last, + random_access_iterator_tag) { + range_initialize(first, last, forward_iterator_tag()); + } + + template <class InputIterator> + void range_insert(iterator pos, + InputIterator first, InputIterator last, + input_iterator_tag); + + template <class ForwardIterator> + void range_insert(iterator pos, + ForwardIterator first, ForwardIterator last, + forward_iterator_tag); + + template <class BidirectionalIterator> + void range_insert(iterator pos, + BidirectionalIterator first, BidirectionalIterator last, + bidirectional_iterator_tag) { + range_insert(pos, first, last, forward_iterator_tag()); + } + + template <class RandomAccessIterator> + void range_insert(iterator pos, + RandomAccessIterator first, RandomAccessIterator last, + random_access_iterator_tag) { + range_insert(pos, first, last, forward_iterator_tag()); + } +#endif /* __STL_MEMBER_TEMPLATES */ +}; + +template <class T, class Alloc> +inline bool operator==(const vector<T, Alloc>& x, const vector<T, Alloc>& y) { + return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); +} + +template <class T, class Alloc> +inline bool operator<(const vector<T, Alloc>& x, const vector<T, Alloc>& y) { + return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); +} + + + +template <class T, class Alloc> +vector<T, Alloc>& vector<T, Alloc>::operator=(const vector<T, Alloc>& x) { + if (&x != this) { + if (x.size() > capacity()) { + const iterator tmp = allocate_and_copy(x.end() - x.begin(), + x.begin(), x.end()); + destroy(start, finish); + deallocate(); + start = tmp; + end_of_storage = start + (x.end() - x.begin()); + } + else if (size() >= x.size()) { + iterator i = copy(x.begin(), x.end(), begin()); + destroy(i, finish); + } + else { + copy(x.begin(), x.begin() + size(), start); + uninitialized_copy(x.begin() + size(), x.end(), finish); + } + finish = start + x.size(); + } + return *this; +} + +template <class T, class Alloc> +void vector<T, Alloc>::insert_aux(iterator position, const T& x) { + if (finish != end_of_storage) { + construct(finish, *(finish - 1)); + ++finish; + T x_copy = x; + copy_backward(position, finish - 2, finish - 1); + *position = x_copy; + } + else { + const size_type old_size = size(); + const size_type len = old_size != 0 ? 2 * old_size : 1; + const iterator new_start = data_allocator::allocate(len); + iterator new_finish = new_start; +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + new_finish = uninitialized_copy(start, position, new_start); + construct(new_finish, x); + ++new_finish; + new_finish = uninitialized_copy(position, finish, new_finish); +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy(new_start, new_finish); + data_allocator::deallocate(new_start, len); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + destroy(begin(), end()); + deallocate(); + start = new_start; + finish = new_finish; + end_of_storage = new_start + len; + } +} + +template <class T, class Alloc> +void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) { + if (n != 0) { + if (size_type (end_of_storage - finish) >= n) { + T x_copy = x; + const size_type elems_after = finish - position; + const iterator old_finish = finish; + if (elems_after > n) { + uninitialized_copy(finish - n, finish, finish); + finish += n; + copy_backward(position, old_finish - n, old_finish); + fill(position, position + n, x_copy); + } + else { + uninitialized_fill_n(finish, n - elems_after, x_copy); + finish += n - elems_after; + uninitialized_copy(position, old_finish, finish); + finish += elems_after; + fill(position, old_finish, x_copy); + } + } + else { + const size_type old_size = size(); + const size_type len = old_size + max(old_size, n); + const iterator new_start = data_allocator::allocate(len); + iterator new_finish = new_start; +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + new_finish = uninitialized_copy(start, position, new_start); + new_finish = uninitialized_fill_n(new_finish, n, x); + new_finish = uninitialized_copy(position, finish, new_finish); +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy(new_start, new_finish); + data_allocator::deallocate(new_start, len); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + destroy(start, finish); + deallocate(); + start = new_start; + finish = new_finish; + end_of_storage = new_start + len; + } + } +} + +#ifdef __STL_MEMBER_TEMPLATES + +template <class T, class Alloc> template <class InputIterator> +void vector<T, Alloc>::range_insert(iterator pos, + InputIterator first, InputIterator last, + input_iterator_tag) { + for ( ; first != last; ++first) { + pos = insert(pos, *first); + ++pos; + } +} + +template <class T, class Alloc> template <class ForwardIterator> +void vector<T, Alloc>::range_insert(iterator position, + ForwardIterator first, + ForwardIterator last, + forward_iterator_tag) { + if (first != last) { + size_type n = 0; + distance(first, last, n); + if (size_type (end_of_storage - finish) >= n) { + const size_type elems_after = finish - position; + const iterator old_finish = finish; + if (elems_after > n) { + uninitialized_copy(finish - n, finish, finish); + finish += n; + copy_backward(position, old_finish - n, old_finish); + copy(first, last, position); + } + else { + ForwardIterator mid = first; + advance(mid, elems_after); + uninitialized_copy(mid, last, finish); + finish += n - elems_after; + uninitialized_copy(position, old_finish, finish); + finish += elems_after; + copy(first, mid, position); + } + } + else { + const size_type old_size = size(); + const size_type len = old_size + max(old_size, n); + const iterator new_start = data_allocator::allocate(len); + iterator new_finish = new_start; +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + new_finish = uninitialized_copy(start, position, new_start); + new_finish = uninitialized_copy(first, last, new_finish); + new_finish = uninitialized_copy(position, finish, new_finish); +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy(new_start, new_finish); + data_allocator::deallocate(new_start, len); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + destroy(start, finish); + deallocate(); + start = new_start; + finish = new_finish; + end_of_storage = new_start + len; + } + } +} + +#else /* __STL_MEMBER_TEMPLATES */ + +template <class T, class Alloc> +void vector<T, Alloc>::insert(iterator position, + const_iterator first, + const_iterator last) { + if (first != last) { + size_type n = 0; + distance(first, last, n); + if (end_of_storage - finish >= n) { + const size_type elems_after = finish - position; + const iterator old_finish = finish; + if (elems_after > n) { + uninitialized_copy(finish - n, finish, finish); + finish += n; + copy_backward(position, old_finish - n, old_finish); + copy(first, last, position); + } + else { + uninitialized_copy(first + elems_after, last, finish); + finish += n - elems_after; + uninitialized_copy(position, old_finish, finish); + finish += elems_after; + copy(first, first + elems_after, position); + } + } + else { + const size_type old_size = size(); + const size_type len = old_size + max(old_size, n); + const iterator new_start = data_allocator::allocate(len); + iterator new_finish = new_start; +# ifdef __STL_USE_EXCEPTIONS + try { +# endif /* __STL_USE_EXCEPTIONS */ + new_finish = uninitialized_copy(start, position, new_start); + new_finish = uninitialized_copy(first, last, new_finish); + new_finish = uninitialized_copy(position, finish, new_finish); +# ifdef __STL_USE_EXCEPTIONS + } + catch(...) { + destroy(new_start, new_finish); + data_allocator::deallocate(new_start, len); + throw; + } +# endif /* __STL_USE_EXCEPTIONS */ + destroy(start, finish); + deallocate(); + start = new_start; + finish = new_finish; + end_of_storage = new_start + len; + } + } +} + +#endif /* __STL_MEMBER_TEMPLATES */ + +#endif /* __SGI_STL_VECTOR_H */ |