14 #ifndef STXXL_VECTOR_HEADER
15 #define STXXL_VECTOR_HEADER
20 #include <stxxl/bits/mng/mng.h>
21 #include <stxxl/bits/common/tmeta.h>
22 #include <stxxl/bits/containers/pager.h>
23 #include <stxxl/bits/common/is_sorted.h>
26 __STXXL_BEGIN_NAMESPACE
37 template <
unsigned_type modulo2,
unsigned_type modulo1>
38 class double_blocked_index
40 static const unsigned_type modulo12 = modulo1 * modulo2;
43 unsigned_type block1, block2;
48 void set(unsigned_type pos)
51 block2 = pos / modulo12;
52 pos -= block2 * modulo12;
53 block1 = pos / modulo1;
54 offset = (pos - block1 * modulo1);
56 assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
57 assert( block1 < modulo2);
58 assert( offset < modulo1);
62 double_blocked_index()
67 double_blocked_index(unsigned_type pos)
72 double_blocked_index(unsigned_type block2, unsigned_type block1, unsigned_type)
74 this->block2 = block2;
75 this->block1 = block1;
76 this->offset = offset;
77 pos = block2 * modulo12 + block1 * modulo1 + offset;
79 assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
80 assert( block1 < modulo2);
81 assert( offset < modulo1);
84 double_blocked_index & operator = (unsigned_type pos)
91 double_blocked_index & operator ++ ()
95 if (offset == modulo1)
99 if (block1 == modulo2)
106 assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
107 assert( block1 < modulo2);
108 assert( offset < modulo1);
114 double_blocked_index operator ++ (
int)
116 double_blocked_index former(*
this);
122 double_blocked_index & operator -- ()
137 assert(block2 * modulo12 + block1 * modulo1 + offset == this->pos);
138 assert( block1 < modulo2);
139 assert( offset < modulo1);
145 double_blocked_index operator -- (
int)
147 double_blocked_index former(*
this);
152 double_blocked_index operator + (unsigned_type addend)
const
154 return double_blocked_index(pos + addend);
157 double_blocked_index & operator += (unsigned_type addend)
163 double_blocked_index operator - (unsigned_type addend)
const
165 return double_blocked_index(pos - addend);
168 unsigned_type operator - (
const double_blocked_index & dbi2)
const
170 return pos - dbi2.pos;
173 double_blocked_index & operator -= (unsigned_type subtrahend)
175 set(pos - subtrahend);
179 bool operator == (
const double_blocked_index & dbi2)
const
181 return pos == dbi2.pos;
184 bool operator != (
const double_blocked_index & dbi2)
const
186 return pos != dbi2.pos;
189 bool operator < (
const double_blocked_index & dbi2)
const
191 return pos < dbi2.pos;
194 bool operator <= (
const double_blocked_index & dbi2)
const
196 return pos <= dbi2.pos;
199 bool operator > (
const double_blocked_index & dbi2)
const
201 return pos > dbi2.pos;
204 bool operator >= (
const double_blocked_index & dbi2)
const
206 return pos >= dbi2.pos;
209 double_blocked_index & operator >>= (unsigned_type shift)
215 unsigned_type get_pos()
const
220 const unsigned_type & get_block2()
const
225 const unsigned_type & get_block1()
const
230 const unsigned_type & get_offset()
const
237 template <
unsigned BlkSize_>
238 class bid_vector :
public std::vector<BID<BlkSize_> >
242 { block_size = BlkSize_ };
243 typedef bid_vector<block_size> _Self;
244 typedef std::vector<BID<BlkSize_> > _Derived;
245 typedef unsigned size_type;
247 bid_vector(size_type _sz) : _Derived(_sz)
262 template <
typename Tp_,
typename AllocStr_,
typename SzTp_,
typename DiffTp_,
263 unsigned BlkSize_,
typename PgTp_,
unsigned PgSz_>
268 template <
typename Tp_,
typename AllocStr_,
typename SzTp_,
typename DiffTp_,
269 unsigned BlkSize_,
typename PgTp_,
unsigned PgSz_>
273 BlkSize_, PgTp_, PgSz_>
_Self;
283 typedef SzTp_ size_type;
284 typedef DiffTp_ difference_type;
285 typedef unsigned block_offset_type;
287 friend class vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_>;
288 typedef bid_vector<BlkSize_> bids_container_type;
289 typedef typename bids_container_type::iterator bids_container_iterator;
293 typedef std::random_access_iterator_tag iterator_category;
294 typedef typename vector_type::value_type value_type;
295 typedef typename vector_type::reference reference;
296 typedef typename vector_type::const_reference const_reference;
297 typedef typename vector_type::pointer pointer;
298 typedef typename vector_type::const_pointer const_pointer;
300 enum { block_size = BlkSize_ };
303 double_blocked_index<PgSz_, block_type::size> offset;
315 p_vector(a.p_vector) { }
317 block_offset_type block_offset()
const
319 return static_cast<block_offset_type
>(offset.get_offset());
321 bids_container_iterator bid()
const
323 return p_vector->bid(offset);
326 difference_type operator - (
const _Self & a)
const
328 return offset - a.offset;
333 return offset - a.offset;
336 _Self operator - (size_type op)
const
338 return _Self(p_vector, offset.get_pos() - op);
341 _Self operator + (size_type op)
const
343 return _Self(p_vector, offset.get_pos() + op);
346 _Self & operator -= (size_type op)
352 _Self & operator += (size_type op)
358 reference operator * ()
360 return p_vector->element(offset);
363 pointer operator -> ()
365 return &(p_vector->element(offset));
368 const_reference operator * ()
const
370 return p_vector->const_element(offset);
373 const_pointer operator -> ()
const
375 return &(p_vector->const_element(offset));
378 reference operator [] (size_type op)
380 return p_vector->element(offset.get_pos() + op);
383 const_reference operator [] (size_type op)
const
385 return p_vector->const_element(offset.get_pos() + op);
390 p_vector->touch(offset);
393 _Self & operator ++ ()
398 _Self operator ++ (
int)
404 _Self & operator -- ()
409 _Self operator -- (
int)
415 bool operator == (
const _Self & a)
const
417 assert(p_vector == a.p_vector);
418 return offset == a.offset;
420 bool operator != (
const _Self & a)
const
422 assert(p_vector == a.p_vector);
423 return offset != a.offset;
425 bool operator < (
const _Self & a)
const
427 assert(p_vector == a.p_vector);
428 return offset < a.offset;
430 bool operator <= (
const _Self & a)
const
432 assert(p_vector == a.p_vector);
433 return offset <= a.offset;
435 bool operator > (
const _Self & a)
const
437 assert(p_vector == a.p_vector);
440 bool operator >= (
const _Self & a)
const
442 assert(p_vector == a.p_vector);
448 assert(p_vector == a.p_vector);
449 return offset == a.offset;
453 assert(p_vector == a.p_vector);
454 return offset != a.offset;
458 assert(p_vector == a.p_vector);
459 return offset < a.offset;
463 assert(p_vector == a.p_vector);
464 return offset <= a.offset;
468 assert(p_vector == a.p_vector);
473 assert(p_vector == a.p_vector);
490 template <
typename Tp_,
typename AllocStr_,
typename SzTp_,
typename DiffTp_,
491 unsigned BlkSize_,
typename PgTp_,
unsigned PgSz_>
495 BlkSize_, PgTp_, PgSz_>
_Self;
499 friend class vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>;
505 typedef SzTp_ size_type;
506 typedef DiffTp_ difference_type;
507 typedef unsigned block_offset_type;
509 friend class vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_>;
510 typedef bid_vector<BlkSize_> bids_container_type;
511 typedef typename bids_container_type::iterator bids_container_iterator;
515 typedef std::random_access_iterator_tag iterator_category;
516 typedef typename vector_type::value_type value_type;
517 typedef typename vector_type::reference reference;
518 typedef typename vector_type::const_reference const_reference;
519 typedef typename vector_type::pointer pointer;
520 typedef typename vector_type::const_pointer const_pointer;
522 enum { block_size = BlkSize_ };
525 double_blocked_index<PgSz_, block_type::size> offset;
546 block_offset_type block_offset()
const
548 return static_cast<block_offset_type
>(offset.get_offset());
550 bids_container_iterator bid()
const
555 difference_type operator - (
const _Self & a)
const
557 return offset - a.offset;
560 difference_type operator - (
const iterator & a)
const
562 return offset - a.offset;
565 _Self operator - (size_type op)
const
567 return _Self(p_vector, offset.get_pos() - op);
570 _Self operator + (size_type op)
const
572 return _Self(p_vector, offset.get_pos() + op);
575 _Self & operator -= (size_type op)
581 _Self & operator += (size_type op)
587 const_reference operator * ()
const
589 return p_vector->const_element(offset);
592 const_pointer operator -> ()
const
594 return &(p_vector->const_element(offset));
597 const_reference operator [] (size_type op)
const
599 return p_vector->const_element(offset.get_pos() + op);
604 p_vector->touch(offset);
607 _Self & operator ++ ()
612 _Self operator ++ (
int)
618 _Self & operator -- ()
623 _Self operator -- (
int)
629 bool operator == (
const _Self & a)
const
631 assert(p_vector == a.p_vector);
632 return offset == a.offset;
634 bool operator != (
const _Self & a)
const
636 assert(p_vector == a.p_vector);
637 return offset != a.offset;
639 bool operator < (
const _Self & a)
const
641 assert(p_vector == a.p_vector);
642 return offset < a.offset;
644 bool operator <= (
const _Self & a)
const
646 assert(p_vector == a.p_vector);
647 return offset <= a.offset;
649 bool operator > (
const _Self & a)
const
651 assert(p_vector == a.p_vector);
652 return offset > a.offset;
654 bool operator >= (
const _Self & a)
const
656 assert(p_vector == a.p_vector);
657 return offset >= a.offset;
660 bool operator == (
const iterator & a)
const
662 assert(p_vector == a.p_vector);
663 return offset == a.offset;
665 bool operator != (
const iterator & a)
const
667 assert(p_vector == a.p_vector);
668 return offset != a.offset;
670 bool operator < (
const iterator & a)
const
672 assert(p_vector == a.p_vector);
673 return offset < a.offset;
675 bool operator <= (
const iterator & a)
const
677 assert(p_vector == a.p_vector);
678 return offset <= a.offset;
680 bool operator > (
const iterator & a)
const
682 assert(p_vector == a.p_vector);
683 return offset > a.offset;
685 bool operator >= (
const iterator & a)
const
687 assert(p_vector == a.p_vector);
688 return offset >= a.offset;
696 std::ostream & operator << (std::ostream & o)
const
698 o <<
"vectorpointer: " << ((
void *)p_vector) <<
" offset: " << offset;
722 unsigned BlkSize_ = STXXL_DEFAULT_BLOCK_SIZE(Tp_),
723 typename AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY,
724 typename SzTp_ = stxxl::uint64
729 typedef Tp_ value_type;
730 typedef value_type & reference;
731 typedef const value_type & const_reference;
732 typedef value_type * pointer;
733 typedef SzTp_ size_type;
734 typedef stxxl::int64 difference_type;
735 typedef const value_type * const_pointer;
737 typedef PgTp_ pager_type;
738 typedef AllocStr_ alloc_strategy;
741 block_size = BlkSize_,
743 n_pages = pager_type::n_pages,
748 difference_type, block_size, pager_type, page_size>
iterator;
749 friend class vector_iterator<value_type, alloc_strategy, size_type, difference_type, block_size, pager_type, page_size>;
751 size_type, difference_type, block_size, pager_type, page_size>
const_iterator;
752 friend class const_vector_iterator<value_type, alloc_strategy, size_type, difference_type, block_size, pager_type, page_size>;
754 typedef bid_vector<block_size> bids_container_type;
755 typedef typename bids_container_type::
756 iterator bids_container_iterator;
757 typedef typename bids_container_type::
758 const_iterator const_bids_container_iterator;
763 alloc_strategy _alloc_strategy;
765 bids_container_type _bids;
767 mutable pager_type pager;
769 enum { uninitialized = 1, dirty = 2 };
770 mutable std::vector<unsigned char> _page_status;
771 mutable std::vector<int_type> _last_page;
772 mutable simple_vector<int_type> _page_no;
773 mutable std::queue<int_type> _free_pages;
774 mutable simple_vector<block_type> _cache;
779 size_type size_from_file_length(stxxl::uint64 file_length)
784 return (cur_size + rest / stxxl::uint64(
sizeof(value_type)));
786 stxxl::uint64 file_length()
788 size_type cur_size = size();
791 stxxl::uint64 full_blocks_length = size_type(_bids.size() - 1) * size_type(
block_type::raw_size);
792 size_type rest = cur_size - size_type(_bids.size() - 1) * size_type(
block_type::size);
793 return full_blocks_length + rest * size_type(
sizeof(value_type));
802 _page_status(div_and_round_up(_bids.size(), page_size)),
803 _last_page(div_and_round_up(_bids.size(), page_size)),
805 _cache(n_pages * page_size),
808 bm = block_manager::get_instance();
809 cfg = config::get_instance();
811 int_type all_pages = div_and_round_up(_bids.size(), page_size);
813 for ( ; i < all_pages; ++i)
815 _page_status[i] = uninitialized;
816 _last_page[i] = on_disk;
819 for (i = 0; i < n_pages; ++i)
823 bm->
new_blocks(_alloc_strategy, _bids.begin(),
829 std::swap(_alloc_strategy, obj._alloc_strategy);
830 std::swap(_size, obj._size);
831 std::swap(_bids, obj._bids);
832 std::swap(pager, obj.pager);
833 std::swap(_page_status, obj._page_status);
834 std::swap(_last_page, obj._last_page);
835 std::swap(_page_no, obj._page_no);
836 std::swap(_free_pages, obj._free_pages);
837 std::swap(_cache, obj._cache);
838 std::swap(_from, obj._from);
840 size_type capacity()
const
844 void reserve(size_type n)
850 unsigned_type old_bids_size = _bids.size();
852 unsigned_type new_pages = div_and_round_up(new_bids_size, page_size);
853 _page_status.resize(new_pages, uninitialized);
854 _last_page.resize(new_pages, on_disk);
856 _bids.resize(new_bids_size);
859 _bids.begin() + old_bids_size, _bids.end());
864 bids_container_iterator it = _bids.begin() + old_bids_size;
867 (*it).storage = _from;
868 (*it).offset = offset;
870 STXXL_VERBOSE1(
"vector::reserve(): Changing size of file " << ((
void *)_from) <<
" to "
875 void resize(size_type n)
877 #ifndef STXXL_FREE_EXTMEMORY_ON_VECTOR_RESIZE
880 unsigned_type old_bids_size = _bids.size();
884 if (new_bids_size > old_bids_size)
888 else if (new_bids_size < old_bids_size)
890 bm->
delete_blocks(_bids.begin() + new_bids_size, _bids.end());
891 _bids.resize(new_bids_size);
893 unsigned_type first_page_to_evict = div_and_round_up(new_bids_size, page_size);
894 std::fill(_page_status.begin() + first_page_to_evict,
895 _page_status.end(), 0);
908 _page_status.clear();
910 while (!_free_pages.empty())
914 for (int_type i = 0; i < n_pages; ++i)
917 void push_back(const_reference obj)
919 size_type old_size = _size;
920 resize(old_size + 1);
921 element(old_size) = obj;
929 return element(_size - 1);
935 const_reference back()
const
937 return const_element(_size - 1);
939 const_reference front()
const
941 return const_element(0);
950 _size(size_from_file_length(from->size())),
951 _bids(div_and_round_up(_size, size_type(
block_type::size))),
952 _page_status(div_and_round_up(_bids.size(), page_size)),
953 _last_page(div_and_round_up(_bids.size(), page_size)),
955 _cache(n_pages * page_size),
959 assert(from->get_id() == -1);
961 if (block_type::has_filler)
963 std::ostringstream str_;
964 str_ <<
"The block size for the vector, mapped to a file must me a multiple of the element size (" <<
965 sizeof(value_type) <<
") and the page size (4096).";
966 throw std::runtime_error(str_.str());
969 bm = block_manager::get_instance();
970 cfg = config::get_instance();
972 int_type all_pages = div_and_round_up(_bids.size(), page_size);
974 for ( ; i < all_pages; ++i)
977 _last_page[i] = on_disk;
980 for (i = 0; i < n_pages; ++i)
984 size_type offset = 0;
985 bids_container_iterator it = _bids.begin();
988 (*it).storage = from;
989 (*it).offset = offset;
996 _bids(div_and_round_up(obj.size(), block_type::size)),
997 _page_status(div_and_round_up(_bids.size(), page_size)),
998 _last_page(div_and_round_up(_bids.size(), page_size)),
1000 _cache(n_pages * page_size),
1003 bm = block_manager::get_instance();
1004 cfg = config::get_instance();
1006 int_type all_pages = div_and_round_up(_bids.size(), page_size);
1008 for ( ; i < all_pages; ++i)
1010 _page_status[i] = uninitialized;
1011 _last_page[i] = on_disk;
1014 for (i = 0; i < n_pages; ++i)
1015 _free_pages.push(i);
1018 bm->
new_blocks(_alloc_strategy, _bids.begin(),
1021 const_iterator inbegin = obj.begin();
1022 const_iterator inend = obj.end();
1023 std::copy(inbegin, inend, begin());
1036 size_type size()
const
1046 return iterator(
this, 0);
1048 const_iterator begin()
const
1050 return const_iterator(
this, 0);
1052 const_iterator cbegin()
const
1058 return iterator(
this, _size);
1060 const_iterator end()
const
1062 return const_iterator(
this, _size);
1064 const_iterator cend()
const
1068 reference operator [] (size_type offset)
1070 return element(offset);
1072 const_reference operator [] (size_type offset)
const
1074 return const_element(offset);
1079 simple_vector<bool> non_free_pages(n_pages);
1081 for ( ; i < n_pages; i++)
1082 non_free_pages[i] =
true;
1085 while (!_free_pages.empty())
1087 non_free_pages[_free_pages.front()] =
false;
1091 for (i = 0; i < n_pages; i++)
1093 _free_pages.push(i);
1094 int_type page_no = _page_no[i];
1095 if (non_free_pages[i])
1097 STXXL_VERBOSE1(
"vector: flushing page " << i <<
" address: " << (int64(page_no) *
1099 if (_page_status[page_no] & dirty)
1100 write_page(page_no, i);
1103 _last_page[page_no] = on_disk;
1104 _page_status[page_no] = 0;
1116 STXXL_VERBOSE(
"An exception in the ~vector()");
1123 STXXL_VERBOSE1(
"~vector(): Changing size of file " << ((
void *)_from) <<
" to "
1125 STXXL_VERBOSE1(
"~vector(): size of the vector is " << size());
1131 bids_container_iterator bid(
const size_type & offset)
1133 return (_bids.begin() +
1134 static_cast<typename bids_container_type::size_type
>
1137 bids_container_iterator bid(
const double_blocked_index<PgSz_, block_type::size> & offset)
1139 return (_bids.begin() +
1140 static_cast<typename bids_container_type::size_type
>
1141 (offset.get_block2() * PgSz_ + offset.get_block1()));
1143 const_bids_container_iterator bid(
const size_type & offset)
const
1145 return (_bids.begin() +
1146 static_cast<typename bids_container_type::size_type
>
1149 const_bids_container_iterator bid(
const double_blocked_index<PgSz_, block_type::size> & offset)
const
1151 return (_bids.begin() +
1152 static_cast<typename bids_container_type::size_type
>
1153 (offset.get_block2() * PgSz_ + offset.get_block1()));
1155 void read_page(int_type page_no, int_type cache_page)
const
1157 STXXL_VERBOSE1(
"vector " <<
this <<
": reading page_no=" << page_no <<
" cache_page=" << cache_page);
1159 int_type block_no = page_no * page_size;
1160 int_type last_block = STXXL_MIN(block_no + page_size, int_type(_bids.size()));
1161 int_type i = cache_page * page_size, j = 0;
1162 for ( ; block_no < last_block; ++block_no, ++i, ++j)
1164 reqs[j] = _cache[i].read(_bids[block_no]);
1166 assert(last_block - page_no * page_size > 0);
1167 wait_all(reqs, last_block - page_no * page_size);
1170 void write_page(int_type page_no, int_type cache_page)
const
1172 STXXL_VERBOSE1(
"vector " <<
this <<
": writing page_no=" << page_no <<
" cache_page=" << cache_page);
1174 int_type block_no = page_no * page_size;
1175 int_type last_block = STXXL_MIN(block_no + page_size, int_type(_bids.size()));
1176 int_type i = cache_page * page_size, j = 0;
1177 for ( ; block_no < last_block; ++block_no, ++i, ++j)
1179 reqs[j] = _cache[i].write(_bids[block_no]);
1181 assert(last_block - page_no * page_size > 0);
1182 wait_all(reqs, last_block - page_no * page_size);
1185 reference element(size_type offset)
1187 return element(double_blocked_index<PgSz_, block_type::size>(offset));
1190 reference element(
const double_blocked_index<PgSz_, block_type::size> & offset)
1192 int_type page_no = offset.get_block2();
1193 assert(page_no < int_type(_last_page.size()));
1194 int_type last_page = _last_page[page_no];
1197 if (_free_pages.empty())
1199 int_type kicked_page = pager.kick();
1200 pager.hit(kicked_page);
1201 int_type old_page_no = _page_no[kicked_page];
1202 _last_page[page_no] = kicked_page;
1203 _last_page[old_page_no] = on_disk;
1204 _page_no[kicked_page] = page_no;
1207 if (_page_status[old_page_no] & dirty)
1210 write_page(old_page_no, kicked_page);
1213 if (_page_status[page_no] != uninitialized)
1215 read_page(page_no, kicked_page);
1218 _page_status[page_no] = dirty;
1220 return _cache[kicked_page * page_size + offset.get_block1()][offset.get_offset()];
1224 int_type free_page = _free_pages.front();
1226 pager.hit(free_page);
1227 _last_page[page_no] = free_page;
1228 _page_no[free_page] = page_no;
1230 if (_page_status[page_no] != uninitialized)
1232 read_page(page_no, free_page);
1235 _page_status[page_no] = dirty;
1237 return _cache[free_page * page_size + offset.get_block1()][offset.get_offset()];
1242 _page_status[page_no] = dirty;
1243 pager.hit(last_page);
1244 return _cache[last_page * page_size + offset.get_block1()][offset.get_offset()];
1247 void touch(size_type offset)
const
1254 void touch(
const double_blocked_index<PgSz_, block_type::size> & offset)
const
1257 assert(offset.get_block2() < _page_status.size());
1258 _page_status[offset.get_block2()] = 0;
1261 const_reference const_element(size_type offset)
const
1263 return const_element(double_blocked_index<PgSz_, block_type::size>(offset));
1266 const_reference const_element(
const double_blocked_index<PgSz_, block_type::size> & offset)
const
1268 int_type page_no = offset.get_block2();
1269 assert(page_no < int_type(_last_page.size()));
1270 int_type last_page = _last_page[page_no];
1273 if (_free_pages.empty())
1275 int_type kicked_page = pager.kick();
1276 pager.hit(kicked_page);
1277 int_type old_page_no = _page_no[kicked_page];
1278 _last_page[page_no] = kicked_page;
1279 _last_page[old_page_no] = on_disk;
1280 _page_no[kicked_page] = page_no;
1283 if (_page_status[old_page_no] & dirty)
1286 write_page(old_page_no, kicked_page);
1289 if (_page_status[page_no] != uninitialized)
1291 read_page(page_no, kicked_page);
1294 _page_status[page_no] = 0;
1296 return _cache[kicked_page * page_size + offset.get_block1()][offset.get_offset()];
1300 int_type free_page = _free_pages.front();
1302 pager.hit(free_page);
1303 _last_page[page_no] = free_page;
1304 _page_no[free_page] = page_no;
1306 if (_page_status[page_no] != uninitialized)
1308 read_page(page_no, free_page);
1311 _page_status[page_no] = 0;
1313 return _cache[free_page * page_size + offset.get_block1()][offset.get_offset()];
1318 pager.hit(last_page);
1319 return _cache[last_page * page_size + offset.get_block1()][offset.get_offset()];
1331 inline bool operator == (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1332 AllocStr_, SzTp_> & a,
1333 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1334 AllocStr_, SzTp_> & b)
1336 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
1346 inline bool operator != (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1347 AllocStr_, SzTp_> & a,
1348 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1349 AllocStr_, SzTp_> & b)
1361 inline bool operator < (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1362 AllocStr_, SzTp_> & a,
1363 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1364 AllocStr_, SzTp_> & b)
1366 return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
1376 inline bool operator > (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1377 AllocStr_, SzTp_> & a,
1378 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1379 AllocStr_, SzTp_> & b)
1391 inline bool operator <= (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1392 AllocStr_, SzTp_> & a,
1393 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1394 AllocStr_, SzTp_> & b)
1406 inline bool operator >= (stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1407 AllocStr_, SzTp_> & a,
1408 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_,
1409 AllocStr_, SzTp_> & b)
1419 template <
typename Tp_,
typename AllocStr_,
typename SzTp_,
typename DiffTp_,
1420 unsigned BlkSize_,
typename PgTp_,
unsigned PgSz_>
1422 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __first,
1423 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __last)
1425 return is_sorted_helper(
1426 stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__first),
1427 stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__last));
1430 template <
typename Tp_,
typename AllocStr_,
typename SzTp_,
typename DiffTp_,
1431 unsigned BlkSize_,
typename PgTp_,
unsigned PgSz_,
typename _StrictWeakOrdering>
1433 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __first,
1434 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> __last,
1435 _StrictWeakOrdering __comp)
1437 return is_sorted_helper(
1438 stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__first),
1439 stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>(__last),
1475 unsigned Pages_ = 8,
1476 unsigned BlkSize_ = STXXL_DEFAULT_BLOCK_SIZE(Tp_),
1477 typename AllocStr_ = STXXL_DEFAULT_ALLOC_STRATEGY,
1478 pager_type Pager_ = lru
1482 typedef typename IF<Pager_ == lru,
1491 __STXXL_END_NAMESPACE
1503 void swap(stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_> & a,
1504 stxxl::vector<Tp_, PgSz_, PgTp_, BlkSize_, AllocStr_, SzTp_> & b)
1510 #endif // !STXXL_VECTOR_HEADER