19 #ifndef VECTOR_BASE_HPP
20 #define VECTOR_BASE_HPP
30 #include <type_traits>
31 #include "globals.hpp"
33 #include "timezone/interval.hpp"
35 #include "type_utils.hpp"
36 #include "allocator.hpp"
52 const size_t VECTOR_INITIAL_ALLOC = 1024;
53 using VECTOR_ALLOC_GROWTH = std::ratio<4,3>;
60 constexpr
rsv_t rsv{};
74 inline T getInitValue() {
78 inline size_t growCapacity(
size_t n) {
79 static_assert(VECTOR_ALLOC_GROWTH::num > VECTOR_ALLOC_GROWTH::den,
80 "vector alloc growth multiplier must be > 1.0");
81 if (n > 0 && n > std::numeric_limits<size_t>::max() / VECTOR_ALLOC_GROWTH::num) {
83 return std::numeric_limits<size_t>::max();
86 return n < VECTOR_INITIAL_ALLOC/2 ? VECTOR_INITIAL_ALLOC :
87 n * VECTOR_ALLOC_GROWTH::num / VECTOR_ALLOC_GROWTH::den;
93 inline size_t getTotalSize(
size_t n) {
94 if (n > 0 && n > std::numeric_limits<size_t>::max() /
sizeof(T) -
sizeof(RawVector<T>)) {
96 return std::numeric_limits<size_t>::max();
98 return n*
sizeof(T) +
sizeof(RawVector<T>);
102 template<
typename T,
typename O=std::less<T>>
104 typedef T value_type;
105 typedef O comparator;
111 template<
typename U,
typename UO>
114 template <
typename U,
typename UO>
115 friend void setv(
Vector<U,UO>& v,
size_t i,
const U& t);
116 template <
typename U,
typename UO>
117 friend void setv_checkbefore(
Vector<U,UO>& v,
size_t i,
const U& t);
118 template <
typename U,
typename UO>
119 friend void setv_nocheck(
Vector<U,UO>& v,
size_t i,
const U& t);
132 std::unique_ptr<baseallocator>&& alloc_p=std::make_unique<memallocator>())
133 : alloc(std::move(alloc_p)), capacity(v.capacity)
137 throw std::invalid_argument(
"Vector<T>: null allocator");
139 c =
new (alloc->allocate(getTotalSize<T>(capacity))) RawVector<T>;
140 memcpy((
void*)c, v.c,
sizeof(RawVector<T>));
141 for (
size_t j=0; j<v.c->n; ++j) {
148 const T& value=getInitValue<T>(),
149 std::unique_ptr<baseallocator>&& alloc_p=std::make_unique<memallocator>())
150 : alloc(std::move(alloc_p))
153 throw std::invalid_argument(
"Vector<T>: null allocator");
155 capacity = growCapacity(n);
156 c =
new (alloc->allocate(getTotalSize<T>(capacity)))
RawVector<T>;
159 for (
size_t i=0; i<n; ++i) {
160 new (&c->v[i]) T(value);
162 c->ordered = n > 1 ? O()(value, value) :
true;
167 std::unique_ptr<baseallocator>&& alloc_p=std::make_unique<memallocator>())
168 : alloc(std::move(alloc_p))
171 throw std::invalid_argument(
"Vector<T,O>: null allocator");
173 capacity = growCapacity(n);
174 c =
new (alloc->allocate(getTotalSize<T>(capacity)))
RawVector<T>;
183 std::unique_ptr<baseallocator>&& alloc_p=std::make_unique<memallocator>())
184 : alloc(std::move(alloc_p))
187 throw std::invalid_argument(
"Vector<T,O>: null allocator");
189 capacity = growCapacity(n);
190 c =
new (alloc->allocate(getTotalSize<T>(capacity)))
RawVector<T>;
197 template <
class InputIterator>
199 const InputIterator& e,
200 std::unique_ptr<baseallocator>&& alloc_p=std::make_unique<memallocator>())
201 : alloc(std::move(alloc_p))
204 throw std::invalid_argument(
"Vector<T,O>: null allocator");
207 capacity = growCapacity(n);
208 c =
new (alloc->allocate(getTotalSize<T>(capacity)))
RawVector<T>;
215 for (
auto iter=b+1; iter!=e; ++iter) {
217 if (!O()(c->v[i-1], c->v[i])) {
225 Vector(std::initializer_list<T> l,
226 std::unique_ptr<baseallocator>&& alloc_p=std::make_unique<memallocator>())
227 : alloc(std::move(alloc_p))
230 throw std::invalid_argument(
"Vector<T,O>: null allocator");
233 capacity = growCapacity(n);
234 c =
new (alloc->allocate(getTotalSize<T>(capacity))) RawVector<T>;
235 c->typenumber = TypeNumber<T>::n;
240 c->v[i++] = *l.begin();
241 for (
auto iter=l.begin()+1; iter!=l.end(); ++iter) {
243 if (!O()(c->v[i-1], c->v[i])) c->ordered =
false;
250 Vector(std::unique_ptr<baseallocator>&& alloc_p) : alloc(std::move(alloc_p)) {
252 throw std::invalid_argument(
"Vector<T,O>: null allocator");
255 capacity = alloc->size();
259 std::swap(alloc, o.alloc);
261 std::swap(capacity, o.capacity);
264 Vector& operator=(Vector<T,O> other) {
269 size_t getBufferSize()
const {
270 return sizeof(RawVector<T>) + size()*
sizeof(T);
273 size_t to_buffer(
char* buf)
const {
275 memcpy(buf, c,
sizeof(RawVector<T>));
276 size_t offset =
sizeof(RawVector<T>);
278 size_t copysz = size()*
sizeof(T);
279 memcpy(buf + offset, c->v, copysz);
280 return offset + copysz;
283 T& operator[](
size_t i) {
284 if (!c || i > size() - 1) {
285 throw std::out_of_range(
"subscript out of bounds");
290 const T& operator[](
size_t i)
const {
291 if (!c || i > size() - 1) {
292 throw std::out_of_range(
"subscript out of bounds");
297 void push_back(
const T& value) {
298 if (c->n + 1 > capacity) {
300 throw std::range_error(
"vector::push_back: cannot reallocate with null allocator");
302 capacity = growCapacity(c->n);
303 auto mem = alloc->reallocate(c, getTotalSize<T>(capacity));
304 c =
static_cast<RawVector<T>*
>(mem);
306 new (&c->v[c->n]) T(value);
307 c->ordered = c->n > 0 ? c->ordered & O()(c->v[c->n-1], c->v[c->n]) :
true;
312 template <
class InputIterator>
313 vector_iterator<T,O> insert(vector_iterator<T,O> position,
314 const InputIterator first,
315 const InputIterator last) {
316 auto ordered = c->ordered;
319 auto diff = last - first;
323 auto oldbegin = begin();
325 resize(size() +
static_cast<size_t>(diff));
327 if (oldbegin != oldend && oldend - 1 - position > 0) {
328 for (
auto iter = end(); iter != position; --iter) {
329 *(iter) = *(iter - diff);
334 if (position != begin()) {
337 ordered &= O()(*(position-1), *position);
340 for (
auto iter = first+1; iter != last; ++iter) {
342 if (c->ordered && !O()(*(position-1), *position)) {
347 if (position != end()) {
350 ordered &= O()(*(position-1), *position);
352 c->ordered = ordered;
356 vector_iterator<T,O> erase(
const vector_iterator<T,O>& position) {
357 for (
auto iter = position; iter != end()-1; ++iter) {
364 vector_iterator<T,O> erase(
const vector_iterator<T,O>& first,
const vector_iterator<T,O>& last) {
365 auto diff = last - first;
366 for (
auto iter = first; iter + diff != end(); ++iter) {
367 *iter = *(iter + diff);
373 explicit operator std::vector<T>()
const {
374 return std::vector<T>(&c->v[0], &c->v[c->n]);
377 const T& front()
const {
379 throw std::range_error(
"front on empty Vector");
384 const T& back()
const {
386 throw std::range_error(
"front on empty Vector");
391 size_t size()
const {
if (c)
return c->n;
else return 0; }
392 bool isOrdered()
const {
if (c)
return c->ordered;
else return false; }
393 void forceOrdered() {
if (c) c->ordered =
true; }
394 void forceUnOrdered() {
if (c) c->ordered =
false; }
395 void setOrdered(
bool val) {
if (c) c->ordered =
val; }
397 bool checkAndSetOrdered() {
398 for (
size_t j=1; j<size(); ++j) {
399 if (!O()(c->v[j-1], c->v[j])) {
408 Vector<T,O>& init(
size_t count,
const T& value) {
410 for (
size_t j=0; j<count; ++j) {
413 c->ordered = count > 1 ? O()(value, value) :
true;
418 Vector<T,O>& resize(
size_t n,
size_t from=0) {
420 throw std::out_of_range(
"resize from out of bounds");
422 if (from || n != c->n) {
424 throw std::range_error(
"vector::resize: cannot reallocate with null allocator");
426 capacity = growCapacity(n);
427 RawVector<T> rv = *c;
428 c =
new (alloc->reallocate((
char*)c + from*
sizeof(T), memsize(capacity))) RawVector<T>;
429 memcpy((
void*)c, &rv,
sizeof(RawVector<T>));
435 Vector<T,O>& resize(
size_t n,
size_t from,
const T& v) {
437 throw std::out_of_range(
"resize from out of bounds");
439 size_t start_fill = c->n - from;
441 for (
size_t i = start_fill; i < n; ++i) {
451 size_t append(
const char* buf,
const size_t len) {
453 if (len <
sizeof(RawVector<T>)) {
454 throw std::out_of_range(
"invalid append buffer: too short");
456 auto appendvec =
reinterpret_cast<const RawVector<T>*
>(buf);
458 const size_t totalsz =
sizeof(RawVector<T>) + appendvec->n *
sizeof(T);
460 throw std::out_of_range(
"missing data");
464 if (TypeNumber<T>::n != appendvec->typenumber) {
465 throw std::out_of_range(
"incorrect type");
469 resize(c->n + appendvec->n);
470 memcpy(&c->v[old_n], appendvec->v, appendvec->n*
sizeof(T));
473 c->ordered &= appendvec->ordered;
475 c->ordered &= O()(c->v[old_n-1], c->v[old_n]);
481 template <
typename AO=O>
483 if (std::is_same<AO, O>::value && c->ordered)
return *
this;
485 std::sort(begin(), end(), AO());
490 if (std::is_same<AO, O>::value) {
497 template<
typename U,
typename AO=O>
498 Vector<U> sort_idx(
size_t base=0)
const {
499 Vector<U> idx(rsv, this->size());
500 for (
size_t j=0; j<size(); ++j) idx.push_back(j+base);
501 std::sort(idx.begin(), idx.end(),
502 [
this, base](
size_t a,
size_t b) {
503 return AO()((*this)[a-base], (*this)[b-base]); });
507 template<
typename F,
typename ...U>
508 Vector& apply(
const U&... u) {
513 for (
size_t i=0; i<size(); ++i) {
514 setv_checkbefore(*
this, i, F()((*
this)[i], u[i]...));
519 template<
typename F,
typename U>
520 Vector& apply_scalar_post(
const U& u) {
522 for (
size_t i=0; i<size(); ++i) {
523 setv_checkbefore(*
this, i, F()((*
this)[i], u));
529 alloc->deallocate(c, c->n);
534 vector_iterator<T,O> begin() {
return vector_iterator<T,O>(*
this, 0); }
535 vector_iterator<T,O> end() {
return vector_iterator<T,O>(*
this, c->n); }
536 vector_const_iterator<T,O> begin()
const {
return vector_const_iterator<T,O>(*
this, 0); }
537 vector_const_iterator<T,O> end()
const {
return vector_const_iterator<T,O>(*
this, c->n); }
538 vector_const_iterator<T,O> cbegin()
const {
return vector_const_iterator<T,O>(*
this, 0); }
539 vector_const_iterator<T,O> cend()
const {
return vector_const_iterator<T,O>(*
this, c->n); }
545 const RawVector<T>* getRawVectorPtr()
const {
return c; }
555 T* c_ptr() {
return c ? c->v :
nullptr; }
556 const T* c_ptr()
const {
return c ? c->v :
nullptr; }
557 const baseallocator* getAllocator()
const {
return alloc.get(); }
560 std::unique_ptr<baseallocator> alloc;
564 T& at(
size_t i) {
return c->v[i]; }
566 static inline size_t memsize(
size_t n) {
return n*
sizeof(T) +
sizeof(RawVector<T>); }
570 inline size_t getTypeNumber(
const std::string& filename) {
571 mmapallocator alloc(filename);
572 size_t* tp =
static_cast<size_t*
>(alloc.initialize());
578 template<
typename T,
typename O>
580 if (v1.c->n != v2.c->n)
return false;
581 for (
size_t i=0; i<v1.c->n; ++i) {
582 if (!(v1.c->v[i] == v2.c->v[i])) {
594 if (v1.c->n != v2.c->n)
return false;
595 return memcmp(v1.c->v, v2.c->v, v1.c->n *
sizeof(
double)) == 0;
598 template<
typename T,
typename O>
599 bool operator!=(
const Vector<T,O>& v1,
const Vector<T,O>& v2) {
603 template<
typename T,
typename O>
604 struct vector_iterator {
605 typedef std::random_access_iterator_tag iterator_category;
606 typedef vector_iterator<T,O> iterator;
607 typedef std::ptrdiff_t difference_type;
608 typedef size_t size_type;
609 typedef T value_type;
611 typedef T& reference;
613 vector_iterator(Vector<T,O>& v_p,
size_t pos_p = 0) : v(v_p), pos(pos_p) { }
614 vector_iterator(
const vector_iterator& i) : v(i.v), pos(i.pos) { }
615 ~vector_iterator() { }
617 vector_iterator& operator=(
const vector_iterator& i) { pos = i.pos;
return *
this; }
618 bool operator==(
const vector_iterator& i)
const {
return &v==&i.v && pos==i.pos; }
619 bool operator!=(
const vector_iterator& i)
const {
return &v!=&i.v || pos!=i.pos; }
620 bool operator< (
const vector_iterator& i)
const {
return pos < i.pos; }
621 bool operator<=(
const vector_iterator& i)
const {
return pos <= i.pos; }
622 bool operator> (
const vector_iterator& i)
const {
return pos > i.pos; }
623 bool operator>=(
const vector_iterator& i)
const {
return pos >= i.pos; }
625 vector_iterator operator+(
size_t n)
const {
626 return vector_iterator<T,O>(v, pos + n);
628 vector_iterator& operator+=(
size_t n) {
632 vector_iterator operator-(
size_t n)
const {
633 return vector_iterator<T,O>(v, pos - n);
636 difference_type operator-(
const vector_iterator& i)
const {
640 vector_iterator& operator++() { ++pos;
return *
this; }
641 vector_iterator operator++(
int)
643 return vector_iterator<T,O>(v, pos++);
645 vector_iterator& operator--() { --pos;
return *
this; }
646 vector_iterator operator--(
int)
648 return vector_iterator<T,O>(v, pos--);
651 reference operator*()
const {
655 pointer operator->()
const {
660 explicit operator size_t()
const {
669 template<
typename T,
typename O>
670 struct vector_const_iterator {
671 typedef std::random_access_iterator_tag iterator_category;
672 typedef vector_const_iterator<T,O> iterator;
673 typedef std::ptrdiff_t difference_type;
674 typedef size_t size_type;
675 typedef T value_type;
676 typedef const T* pointer;
677 typedef const T& reference;
679 vector_const_iterator(
const Vector<T,O>& v_p,
size_t pos_p = 0) : v(v_p), pos(pos_p) { }
680 vector_const_iterator(
const vector_const_iterator& i) : v(i.v), pos(i.pos) { }
681 ~vector_const_iterator() { }
683 vector_const_iterator& operator=(
const vector_const_iterator& i) { pos = i.pos;
return *
this; }
684 bool operator==(
const vector_const_iterator& i)
const {
return &v==&i.v && pos==i.pos; }
685 bool operator!=(
const vector_const_iterator& i)
const {
return &v!=&i.v || pos!=i.pos; }
686 vector_const_iterator operator+(
size_t n)
const {
687 return vector_const_iterator<T,O>(v, pos + n);
689 vector_const_iterator& operator+=(
size_t n) {
693 vector_const_iterator operator-(
size_t n)
const {
694 return vector_const_iterator<T,O>(v, pos - n);
696 difference_type operator-(
const vector_const_iterator& i)
const {
700 vector_const_iterator& operator++() { ++pos;
return *
this; }
701 vector_const_iterator operator++(
int)
703 return vector_const_iterator<T,O>(v, pos++);
705 vector_const_iterator& operator--() { --pos;
return *
this; }
706 vector_const_iterator operator--(
int)
708 return vector_const_iterator<T,O>(v, pos--);
711 reference operator*()
const {
return v[pos]; }
712 pointer operator->()
const {
return &v[pos]; }
714 size_t getpos()
const {
return pos; }
717 const Vector<T,O>& v;
722 template <
typename T,
typename O>
723 void setv(Vector<T,O>& v,
size_t i,
const T& t) {
724 if (i >= v.size())
throw std::range_error(
"subscript out of bounds");
726 if (i > 0) v.c->ordered = O()(v[i-1], t);
727 if (i < v.size()-1) v.c->ordered = v.c->ordered && O()(t, v[i+1]);
731 template <
typename T,
typename O>
732 void setv_checkbefore(Vector<T,O>& v,
size_t i,
const T& t) {
733 if (i >= v.size())
throw std::range_error(
"subscript out of bounds");
736 if (i > 0) v.c->ordered = O()(v.c->v[i-1], t);
740 template <
typename T,
typename O>
741 void setv_nocheck(Vector<T,O>& v,
size_t i,
const T& t) {