stlab.adobe.com Adobe Systems Incorporated

vector.hpp

Go to the documentation of this file.
00001 /*
00002     Copyright 2005-2007 Adobe Systems Incorporated
00003     Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
00004     or a copy at http://stlab.adobe.com/licenses.html)
00005 */
00006 
00007 /*************************************************************************************************/
00008 
00009 #ifndef ADOBE_VECTOR_HPP
00010 #define ADOBE_VECTOR_HPP
00011 
00012 /*************************************************************************************************/
00013 
00014 #include <adobe/config.hpp>
00015 
00016 #include <adobe/vector_fwd.hpp>
00017 
00018 #include <algorithm>
00019 #include <cassert>
00020 #include <cstddef>
00021 #include <iterator>
00022 #include <memory>
00023 
00024 #include <boost/operators.hpp>
00025 #include <boost/static_assert.hpp>
00026 #include <boost/type_traits/has_nothrow_constructor.hpp>
00027 #include <boost/type_traits/is_integral.hpp>
00028 #include <boost/utility/enable_if.hpp>
00029 
00030 #include <adobe/empty.hpp>
00031 #include <adobe/typeinfo.hpp>
00032 #include <adobe/memory.hpp>
00033 #include <adobe/algorithm/minmax.hpp>
00034 
00035 #include <adobe/move.hpp>
00036 #include <adobe/implementation/swap.hpp>
00037 
00038 #ifdef ADOBE_STD_SERIALIZATION
00039 #include <adobe/iomanip.hpp>
00040 #endif
00041 
00042 /*************************************************************************************************/
00043 
00044 namespace adobe {
00045 namespace version_1 {
00046 
00053 /*************************************************************************************************/
00054 
00056 template <typename T,   // T models Regular
00057           typename A>   // A models Allocator(T)
00058 class vector : boost::totally_ordered<vector<T, A>, vector<T, A> >
00059 {
00060  public:
00061     typedef T&                              reference;
00062     typedef const T&                        const_reference;
00063     typedef T*                              iterator;
00064     typedef const T*                        const_iterator;
00065     typedef std::size_t                     size_type;
00066     typedef std::ptrdiff_t                  difference_type;
00067     typedef T                               value_type;
00068     typedef A                               allocator_type;
00069     typedef T*                              pointer;
00070     typedef const T*                        const_pointer;
00071     typedef std::reverse_iterator<T*>       reverse_iterator;
00072     typedef std::reverse_iterator<const T*> const_reverse_iterator;
00073     
00074  private:
00075     struct header_t
00076     {
00077         struct compact_header_t
00078         {
00079             boost::compressed_pair<A, T*> allocate_finish_m;
00080             T* end_of_storage_m;
00081         };
00082         aligned_storage<compact_header_t> header_m;
00083         T  storage_m[1];
00084 
00085         allocator_type& allocator() { return header_m.get().allocate_finish_m.first(); }
00086         const allocator_type& allocator() const { return header_m.get().allocate_finish_m.first(); }
00087 
00088         pointer& finish() { return header_m.get().allocate_finish_m.second(); }
00089         const pointer& finish() const { return header_m.get().allocate_finish_m.second(); }
00090 
00091         pointer& end_of_storage() { return header_m.get().end_of_storage_m; }
00092         const pointer& end_of_storage() const { return header_m.get().end_of_storage_m; }
00093     };
00094 
00095     header_t* header_m;
00096     
00097     void set_finish(T* x)
00098     {
00099         assert(header_m != 0 || x == 0);
00100         if (header_m) header_m->finish() = x;
00101     }
00102     
00103     const T* end_of_storage() const { return header_m ? header_m->end_of_storage() : 0; }
00104     
00105     static header_t* allocate(allocator_type, std::size_t);
00106     
00107     size_type remaining() const { return end_of_storage() - end(); }
00108     
00109     template <typename I> // I models InputIterator
00110     void append(I f, I l) { append(f, l, typename std::iterator_traits<I>::iterator_category()); }
00111     
00112     template <typename I> // I models InputIterator
00113     void append(I f, I l, std::input_iterator_tag);
00114     
00115     template <typename I> // I models ForwardIterator
00116     void append(I f, I l, std::forward_iterator_tag);
00117     
00118     template <typename I> // I models InputIterator
00119     void append_move(I f, I l)
00120     { append_move(f, l, typename std::iterator_traits<I>::iterator_category()); }
00121     
00122     template <typename I> // I models InputIterator
00123     void append_move(I f, I l, std::input_iterator_tag);
00124     
00125     template <typename I> // I models ForwardIterator
00126     void append_move(I f, I l, std::forward_iterator_tag);
00127     
00128     template <typename I> // I models InputIterator
00129     iterator insert(iterator p, I f, I l, std::input_iterator_tag);
00130     
00131     template <typename I> // I models ForwardIterator
00132     iterator insert(iterator p, I f, I l, std::forward_iterator_tag);
00133    
00134  public:
00135     // 23.2.4.1 construct/copy/destroy
00136 
00137     explicit vector(const allocator_type& a) : header_m(allocate(a, 0)) { }
00138     vector() : header_m(0) { }
00139     
00140     explicit vector(size_type n) : header_m(allocate(allocator_type(), n))
00141     {
00142         std::uninitialized_fill_n(end(), n, value_type());
00143         set_finish(end() + n);
00144     }
00145     
00146     vector(size_type n, const value_type& x) : header_m(allocate(allocator_type(), n))
00147     {
00148         std::uninitialized_fill_n(end(), n, x);
00149         set_finish(end() + n);
00150     }
00151 
00152     vector(size_type n, const value_type& x, const allocator_type& a) : header_m(allocate(a, n))
00153     {
00154         std::uninitialized_fill_n(end(), n, x);
00155         set_finish(end() + n);
00156     }
00157 
00158     vector(const vector& x) : header_m(allocate(x.get_allocator(), x.size()))
00159     {
00160 #ifndef NDEBUG
00161     /* REVISIT (sparent) : MS stupid "safety check" doesn't known about empty ranges. */
00162         set_finish(x.begin() == x.end() ? end() : std::uninitialized_copy(x.begin(), x.end(), end()));
00163 #else
00164         set_finish(std::uninitialized_copy(x.begin(), x.end(), end()));
00165 #endif
00166     }
00167 
00168     template <typename I> // I models InputIterator
00169     vector(I f, I l, typename boost::disable_if<boost::is_integral<I> >::type* = 0) : header_m(0)
00170     { append(f, l); }
00171 
00172     template <typename I> // I models InputIterator
00173     vector(I f, I l, const allocator_type& a,
00174         typename boost::disable_if<boost::is_integral<I> >::type* = 0) : header_m(allocate(a), 0)
00175     { append(f, l); }
00176 
00177     ~vector() {
00178         if (header_m) {
00179             clear();
00180 
00181             typename allocator_type::template rebind<char>::other alloc(get_allocator());
00182             alloc.deallocate(reinterpret_cast<char*>(header_m),
00183                 (end_of_storage() - begin()) * sizeof(T) + (sizeof(header_t) - sizeof(T)));
00184         }
00185     }
00186 
00187     // adobe addition
00188     
00189     vector(move_from<vector> x) : header_m(x.source.header_m) { x.source.header_m = 0; }
00190 
00191     allocator_type get_allocator() const
00192     { return header_m ? header_m->allocator() : allocator_type(); }
00193     
00194     iterator begin() { return header_m ? &header_m->storage_m[0] : 0; }
00195     iterator end() { return header_m ? header_m->finish() : 0; }
00196     
00197     const_iterator begin() const { return header_m ? &header_m->storage_m[0] : 0; }
00198     const_iterator end() const { return header_m ? header_m->finish() : 0; }
00199     
00200     reverse_iterator rbegin() { return reverse_iterator(end()); }
00201     reverse_iterator rend() { return reverse_iterator(begin()); }
00202     
00203     const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
00204     const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
00205     
00206     size_type size() const { return size_type(end() - begin()); }
00207     size_type max_size() const { return size_type(-1) / sizeof(value_type); }
00208     
00209     size_type capacity() const { return size_type(end_of_storage() - begin()); }
00210     bool empty() const { return begin() == end(); }
00211     
00212     reference operator[](size_type n) { assert(n < size()); return *(begin() + n); }
00213     const_reference operator[](size_type n) const { assert(n < size()); return *(begin() + n); }
00214     
00215     /*
00216         REVISIT (sparent@adobe.com): at() explicitly omitted because it pulls in out_of_range
00217         which inherits from logic_error and uses std::string.
00218     */
00219     
00220     vector& operator=(vector x) { swap(x); return *this; }
00221     
00222     void reserve(size_type n);
00223     
00224     reference front() { assert(!empty()); return *begin(); }
00225     const_reference front() const { assert(!empty()); return *begin(); }
00226     
00227     reference back() { assert(!empty()); return *(end() - 1); }
00228     const_reference back() const { assert(!empty()); return *(end() - 1); }
00229     
00230     void push_back(value_type x)
00231     { append_move(&x, &x + 1); }
00232     
00233     void pop_back() { assert(!empty()); resize(size() - 1); }
00234     
00235     void swap(vector& x) { std::swap(header_m, x.header_m); }
00236         
00237     iterator insert(iterator p, value_type x)
00238     { return insert_move(p, &x, &x + 1); }
00239     
00240     template <typename I> // I models InputIterator
00241     iterator insert(iterator p, I f, I l, typename boost::disable_if<boost::is_integral<I> >::type* = 0)
00242     { return insert(p, f, l, typename std::iterator_traits<I>::iterator_category()); }
00243     
00244     template <typename I> // I models ForwardIterator
00245     iterator insert_move(iterator p, I f, I l);
00246     
00247     iterator insert(iterator p, size_type n, const T& x);
00248     
00249     iterator erase(iterator pos) { assert(pos != end()); return erase(pos, pos + 1); }
00250     
00251     iterator erase(iterator f, iterator l);
00252     
00253     void clear() { erase(begin(), end()); }
00254     
00255     void resize(size_type n);
00256     
00257     void resize(size_type n, const value_type& x);
00258     
00259     friend inline bool operator==(const vector& x, const vector& y)
00260     {
00261 #if defined(_MSC_VER) && _MSC_VER == 1600 && _ITERATOR_DEBUG_LEVEL != 0
00262         return (x.size() == y.size()) && std::_Equal1(x.begin(), x.end(),
00263                                                       y.begin(), std::tr1::false_type());
00264 #else
00265         return (x.size() == y.size()) && std::equal(x.begin(), x.end(), y.begin());
00266 #endif
00267     }
00268     
00269     friend inline bool operator<(const vector& x, const vector& y)
00270     {
00271         return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
00272     }
00273     
00274     friend inline void swap(vector& x, vector& y) { x.swap(y); }
00275 };
00276 
00277 template <typename T, typename A>
00278 typename vector<T, A>::header_t* vector<T, A>::allocate(allocator_type a, std::size_t n)
00279 {
00280     if (n == 0) {
00281         if (a == allocator_type()) return 0;
00282          n = 1;
00283     }
00284 
00285     typename allocator_type::template rebind<char>::other alloc(a);
00286 
00287     header_t* result = reinterpret_cast<header_t*>(alloc.allocate(sizeof(header_t) - sizeof(T)
00288             + n * sizeof(T)));
00289     construct(&result->allocator(), a);
00290     result->finish() = &result->storage_m[0];
00291     result->end_of_storage() = result->finish() + n;
00292     
00293     return result;
00294 }
00295 
00296 template <typename T, typename A>
00297 template <typename I> // I models InputIterator
00298 void vector<T, A>::append(I f, I l, std::input_iterator_tag) { while (f != l) { push_back(*f); ++f; } }
00299 
00300 template <typename T, typename A>
00301 template <typename I> // I models InputIterator
00302 void vector<T, A>::append_move(I f, I l, std::input_iterator_tag)
00303 { while (f != l) { push_back(adobe::move(*f)); ++f; } }
00304     
00305 template <typename T, typename A>
00306 template <typename I> // I models ForwardIterator
00307 void vector<T, A>::append(I f, I l, std::forward_iterator_tag)
00308 {
00309     size_type n(std::distance(f, l));
00310     
00311     if (remaining() < n) reserve((adobe::max)(size() + n, 2 * size()));
00312     set_finish(std::uninitialized_copy(f, l, end()));
00313 }
00314     
00315 template <typename T, typename A>
00316 template <typename I> // I models ForwardIterator
00317 void vector<T, A>::append_move(I f, I l, std::forward_iterator_tag)
00318 {
00319     size_type n(std::distance(f, l));
00320     
00321     if (remaining() < n) reserve((adobe::max)(size() + n, 2 * size()));
00322     set_finish(uninitialized_move(f, l, end()));
00323 }
00324     
00325 template <typename T, typename A>
00326 template <typename I> // I models InputIterator
00327 typename vector<T, A>::iterator vector<T, A>::insert(iterator p, I f, I l, std::input_iterator_tag)
00328 {
00329     size_type o(p - begin());
00330     size_type s = size();
00331     append(f, l);
00332     // REVISIT (sparent) : This could be a move based rotate
00333     std::rotate(begin() + o, begin() + s, end());
00334     return end() - s + o;
00335 }
00336     
00337 template <typename T, typename A>
00338 template <typename I> // I models ForwardIterator
00339 typename vector<T, A>::iterator vector<T, A>::insert(iterator p, I f, I l, std::forward_iterator_tag)
00340 {
00341     size_type n(std::distance(f, l));
00342     iterator  last = end();
00343     size_type before = p - begin();
00344 
00345     if (remaining() < n) {
00346         vector tmp;
00347         tmp.reserve((adobe::max)(size() + n, 2 * size()));
00348         tmp.append_move(begin(), p);
00349         tmp.append(f, l);
00350         tmp.append_move(p, last);
00351         swap(tmp);
00352     } else {
00353         size_type after(last - p);
00354         
00355         if (n < after) {
00356             append_move(last - n, last);
00357             move_backward(p, last - n, last);
00358             std::copy(f, l, p);
00359         } else {
00360             I m = f;
00361             std::advance(m, after);
00362             append(m, l);
00363             append_move(p, last);
00364             std::copy(f, m, p);
00365         }
00366     }
00367     return begin() + before + n;
00368 }
00369     
00370 template <typename T, typename A>
00371 template <typename I> // I models ForwardIterator
00372 typename vector<T, A>::iterator vector<T, A>::insert_move(iterator p, I f, I l)
00373 {
00374     size_type n(std::distance(f, l));
00375     iterator  last = end();
00376     size_type before = p - begin();
00377 
00378     if (remaining() < n) {
00379         vector tmp;
00380         tmp.reserve((adobe::max)(size() + n, 2 * size()));
00381         tmp.append_move(begin(), p);
00382         tmp.append_move(f, l);
00383         tmp.append_move(p, last);
00384         swap(tmp);
00385     } else {
00386         size_type after(last - p);
00387         
00388         if (n < after) {
00389             append_move(last - n, last);
00390             move_backward(p, last - n, last);
00391             adobe::move(f, l, p);
00392         } else {
00393             I m = f;
00394             std::advance(m, after);
00395             append_move(m, l);
00396             append_move(p, last);
00397             adobe::move(f, m, p);
00398         }
00399     }
00400     return begin() + before + n;
00401 }
00402 
00403 template <typename T, typename A>
00404 void vector<T, A>::reserve(size_type n)
00405 {
00406     if (capacity() < n) {
00407         vector tmp;
00408         tmp.header_m = allocate(get_allocator(), n);
00409         tmp.header_m->finish() = uninitialized_move(begin(), end(), tmp.end());
00410         swap(tmp);
00411     }
00412 }
00413 
00414 template <typename T, typename A>
00415 typename vector<T, A>::iterator vector<T, A>::insert(iterator p, size_type n, const T& x)
00416 {
00417     iterator  last = end();
00418     size_type before = p - begin();
00419 
00420     if (remaining() < n) {
00421         vector tmp;
00422         tmp.reserve((adobe::max)(size() + n, 2 * size()));
00423         tmp.append_move(begin(), p);
00424         std::uninitialized_fill_n(tmp.end(), n, x);
00425         tmp.set_finish(tmp.end() + n);
00426         tmp.append_move(p, last);
00427         swap(tmp);
00428     } else {
00429         size_type after(last - p);
00430         
00431         if (n < after) {
00432             append_move(last - n, last);
00433             move_backward(p, last - n, last);
00434             std::fill_n(p, n, x);
00435         } else {
00436             std::uninitialized_fill_n(last, n - after, x);
00437             set_finish(last + (n - after));
00438             append_move(p, last);
00439             std::fill_n(p, after, x);
00440         }
00441     }
00442     return begin() + before + n;
00443 }
00444     
00445 template <typename T, typename A>
00446 typename vector<T, A>::iterator vector<T, A>::erase(iterator f, iterator l)
00447 {
00448     iterator i = adobe::move(l, end(), f);
00449     for (iterator b(i), e(end()); b != e; ++b) {
00450         b->~value_type();
00451     }
00452     set_finish(i);
00453     return f;
00454 }
00455     
00456 template <typename T, typename A>
00457 void vector<T, A>::resize(size_type n)
00458 {
00459     if (n < size()) erase(begin() + n, end());
00460     else insert(end(), n - size(), value_type());
00461 }
00462     
00463 template <typename T, typename A>
00464 void vector<T, A>::resize(size_type n, const value_type& x)
00465 {
00466     if (n < size()) erase(begin() + n, end());
00467     else insert(end(), n - size(), x);
00468 }
00469 
00470 /*************************************************************************************************/
00471 
00472 #ifdef ADOBE_STD_SERIALIZATION
00473 
00474 template <typename T, typename A>
00475 std::ostream& operator<<(std::ostream& out, const vector<T, A>& x)
00476 {
00477     out << begin_sequence;
00478     
00479     for (typename vector<T, A>::const_iterator first(x.begin()), last(x.end()); first != last; ++first)
00480     {
00481         out << format(*first);
00482     }
00483     
00484     out << end_sequence;
00485     
00486     return out;
00487 }
00488 
00489 #endif
00490 
00491 /*************************************************************************************************/
00492 
00493 BOOST_STATIC_ASSERT(sizeof(vector<int>) == sizeof(void*));
00494 
00495 /*************************************************************************************************/
00496 
00497 } // namespace version_1
00498 } // namespace adobe
00499 
00500 /*************************************************************************************************/
00501 
00502 ADOBE_NAME_TYPE_1("vector:version_1:adobe", adobe::version_1::vector<T0,
00503         adobe::capture_allocator<T0> >)
00504 ADOBE_NAME_TYPE_2("vector:version_1:adobe", adobe::version_1::vector<T0, T1>)
00505 
00506 /*************************************************************************************************/
00507 
00508 namespace boost {
00509 
00510 template <typename T, typename A>
00511 struct has_nothrow_constructor<adobe::version_1::vector<T, A> > : boost::mpl::true_ { };
00512 
00513 } // namespace boost
00514 
00518 /*************************************************************************************************/
00519 
00520 #endif

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google