Line data Source code
1 : /*
2 : * Implementation of a vector optimized for the case where only a small number of elements
3 : * are stored.
4 : * The vector starts out storing elements in an inline storage buffer of size N. If the vector size
5 : * grows beyond N elements, the vector stores the elements in a dynamically allocated buffer.
6 : * The implementation of small_vector is largely inspired by the SmallVector class implementation from
7 : * the LLVM framework codebase.
8 : * Link to the implementation of SmallVector in the LLVM codebase :
9 : * https://github.com/llvm/llvm-project/blob/master/llvm/include/llvm/ADT/SmallVector.h
10 : * The implementation of the function nextPowerOfTwo has been largely inspired by the implementation of
11 : * the function NextPowerOf2 from the LLVM codebase :
12 : * Link to the implementation of NextPowerOf2 in the LLVM codebase:
13 : * https://github.com/llvm/llvm-project/blob/master/llvm/include/llvm/Support/MathExtras.h
14 : */
15 :
16 : #ifndef SMALL_VECTOR_HPP
17 : #define SMALL_VECTOR_HPP
18 :
19 : #include <cstddef>
20 : #include <cstdlib>
21 : #include <iterator>
22 : #include <limits>
23 : #include <cassert>
24 : #include <memory>
25 : #include <stdexcept>
26 : #include <iostream>
27 : #include <algorithm>
28 :
29 : inline uint64_t nextPowerOfTwo(uint64_t n);
30 :
31 : class small_vector_common_base {
32 : protected:
33 : size_t capacity_;
34 : size_t originalCapacity_;
35 : size_t size_;
36 : void *beginPtr_;
37 :
38 : small_vector_common_base() = delete;
39 16353 : small_vector_common_base(size_t originalCapacity, void *beginPtr)
40 16353 : : capacity_(originalCapacity), originalCapacity_(originalCapacity), size_(0), beginPtr_(beginPtr) {}
41 : };
42 :
43 : template <typename T>
44 : struct small_vector_internal_storage_offset_computation_structure {
45 : alignas(small_vector_common_base) char base[sizeof(small_vector_common_base)];
46 : alignas(T) char firstElt[sizeof(T)];
47 : };
48 :
49 : template <typename T>
50 : class small_vector_base : public small_vector_common_base {
51 : public:
52 :
53 : using size_type = size_t;
54 : using difference_type = ptrdiff_t;
55 : using value_type = T;
56 : using iterator = T *;
57 : using const_iterator = const T *;
58 :
59 : using reverse_iterator = std::reverse_iterator<iterator>;
60 : using const_reverse_iterator = std::reverse_iterator<const_iterator>;
61 :
62 : using reference = T &;
63 : using const_reference = const T &;
64 : using pointer = T *;
65 : using const_pointer = const T *;
66 :
67 : private:
68 29 : void grow_capacity_to_a_minimum_of(size_type minCapacity) {
69 29 : assert(minCapacity <= UINT32_MAX);
70 :
71 29 : size_type newCapacity = std::min(std::max(minCapacity, size_t(nextPowerOfTwo(capacity()))), size_t(UINT32_MAX));
72 :
73 29 : void *p = std::malloc(newCapacity*sizeof(T));
74 :
75 29 : std::uninitialized_copy(std::move_iterator<iterator>(begin()), std::move_iterator<iterator>(end()), static_cast<iterator>(p));
76 :
77 29 : std::destroy(rbegin(), rend());
78 :
79 29 : if(!is_small()) {
80 0 : std::free(beginPtr_);
81 : }
82 :
83 29 : beginPtr_ = p;
84 29 : capacity_ = newCapacity;
85 29 : }
86 :
87 : protected:
88 : small_vector_base() = delete;
89 16372 : small_vector_base(size_t originalCapacity)
90 16372 : : small_vector_common_base(originalCapacity, getPointerToInternalStorage()) {}
91 :
92 : public:
93 : template<typename InputItTy,
94 : typename = typename std::enable_if<std::is_convertible<
95 : typename std::iterator_traits<InputItTy>::iterator_category,
96 : std::input_iterator_tag>::value>::type>
97 3404 : void assign(InputItTy first, InputItTy last) {
98 3404 : size_t nbEltsInRange = std::distance(first, last);
99 :
100 3404 : if(capacity() >= nbEltsInRange) {
101 3404 : if(nbEltsInRange <= size()) {
102 0 : std::copy(first, last, begin());
103 :
104 0 : if(nbEltsInRange < size()) {
105 0 : std::destroy(rbegin(), reverse_iterator(begin() + nbEltsInRange));
106 : }
107 : }else {
108 3404 : iterator i2 = begin();
109 3404 : InputItTy i = first;
110 :
111 3404 : for(size_t nb = size(); nb > 0; --nb, ++i, ++i2) {
112 0 : *i2 = *i;
113 : }
114 :
115 6963 : for(; i != last; ++i2, ++i) {
116 3559 : new (static_cast<void *>(std::addressof(*i2))) T(*i);
117 : }
118 : }
119 : }else {
120 0 : clear();
121 0 : grow_capacity_to_a_minimum_of(nbEltsInRange);
122 0 : std::uninitialized_copy(first, last, begin());
123 : }
124 :
125 3404 : set_size(nbEltsInRange);
126 3404 : }
127 :
128 1106 : void assign(size_type count, const T &value) {
129 :
130 1106 : if(capacity() >= count) {
131 1078 : if(count <= size()) {
132 957 : std::fill_n(begin(), count, value);
133 :
134 957 : if(count < size()) {
135 0 : std::destroy(rbegin(), reverse_iterator(begin() + count));
136 : }
137 : }else {
138 121 : std::fill_n(begin(), size(), value);
139 121 : std::uninitialized_fill(end(), begin() + count, value);
140 : }
141 :
142 : } else {
143 28 : clear();
144 28 : grow_capacity_to_a_minimum_of(count);
145 28 : std::uninitialized_fill_n(begin(), count, value);
146 : }
147 :
148 1106 : set_size(count);
149 1106 : }
150 :
151 3404 : void assign(std::initializer_list<T> il) {
152 3404 : assign(il.begin(), il.end());
153 3404 : }
154 :
155 696 : small_vector_base &operator=(const small_vector_base &rhs) {
156 696 : if(this == std::addressof(rhs)) {
157 0 : return *this;
158 : }
159 :
160 696 : size_type rhsSize = rhs.size();
161 :
162 696 : if(size() >= rhsSize) {
163 0 : if(rhsSize > 0) {
164 0 : std::copy(rhs.begin(), rhs.end(), begin());
165 : }
166 :
167 0 : std::destroy(rbegin(), reverse_iterator(begin() + rhsSize));
168 :
169 0 : set_size(rhsSize);
170 0 : return *this;
171 : }
172 :
173 696 : if(capacity() < rhsSize) {
174 0 : clear();
175 0 : grow_capacity_to_a_minimum_of(rhsSize);
176 696 : }else if(size() > 0) {
177 0 : std::copy(rhs.begin(), rhs.begin() + size(), begin());
178 : }
179 :
180 696 : std::uninitialized_copy(rhs.begin() + size(), rhs.end(), begin() + size());
181 696 : set_size(rhsSize);
182 696 : return *this;
183 : }
184 :
185 161 : small_vector_base &operator=(small_vector_base &&rhs) {
186 161 : if(this == std::addressof(rhs)) {
187 0 : return *this;
188 : }
189 :
190 161 : if(!rhs.is_small()) {
191 0 : clear();
192 :
193 0 : if(!is_small()) {
194 0 : std::free(beginPtr_);
195 : }
196 :
197 0 : beginPtr_ = rhs.begin();
198 0 : size_ = rhs.size();
199 0 : capacity_ = rhs.capacity();
200 0 : rhs.reset_to_small();
201 :
202 0 : return *this;
203 : }
204 :
205 161 : size_type rhsSize = rhs.size();
206 :
207 161 : if(size() >= rhsSize) {
208 0 : if(rhsSize > 0) {
209 0 : std::move(rhs.begin(), rhs.end(), begin());
210 : }
211 :
212 0 : std::destroy(rbegin(), reverse_iterator(begin() + rhsSize));
213 0 : set_size(rhsSize);
214 0 : rhs.clear();
215 0 : return *this;
216 : }
217 :
218 161 : if(capacity() < rhsSize) {
219 0 : clear();
220 0 : grow_capacity_to_a_minimum_of(rhsSize);
221 161 : }else if(size() > 0) {
222 0 : std::move(rhs.begin(), rhs.begin() + size(), begin());
223 : }
224 :
225 161 : std::uninitialized_copy(std::move_iterator<iterator>(rhs.begin() + size()),
226 : std::move_iterator<iterator>(rhs.end()),
227 161 : begin() + size());
228 161 : set_size(rhsSize);
229 161 : rhs.clear();
230 161 : return *this;
231 : }
232 :
233 : reference at(size_type index) {
234 : if(index < size()) {
235 : return begin()[index];
236 : } else {
237 : throw std::out_of_range("small_vector::at(size_type index) std::out_or_range exception");
238 : }
239 : }
240 :
241 52836 : reference operator[](size_type index) {
242 52836 : return begin()[index];
243 : }
244 :
245 99630 : const_reference operator[](size_type index) const {
246 99630 : return begin()[index];
247 : }
248 :
249 : reference front() {
250 : assert(!empty());
251 : return begin()[0];
252 : }
253 :
254 1073 : const_reference front() const {
255 1073 : assert(!empty());
256 1073 : return begin()[0];
257 : }
258 :
259 8284 : reference back() {
260 8284 : assert(!empty());
261 8284 : return end()[-1];
262 : }
263 :
264 : const_reference back() const {
265 : assert(!empty());
266 : return end()[-1];
267 : }
268 :
269 : pointer data() {
270 : return pointer(begin());
271 : }
272 :
273 : const_pointer data() const {
274 : return const_pointer(begin());
275 : }
276 :
277 143945 : iterator begin() { return static_cast<iterator>(beginPtr_); }
278 125855 : const_iterator begin() const { return static_cast<const_iterator>(beginPtr_); }
279 : const_iterator cbegin() const { return static_cast<const_iterator>(beginPtr_); }
280 :
281 55662 : iterator end() { return begin() + size(); }
282 16044 : const_iterator end() const { return begin() + size(); }
283 : const_iterator cend() const { return begin() + size(); }
284 :
285 18295 : reverse_iterator rbegin() { return reverse_iterator(end()); }
286 : const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
287 : const_reverse_iterator crbegin() const { return const_reverse_iterator(end()); }
288 :
289 18089 : reverse_iterator rend() { return reverse_iterator(begin()); }
290 : const_reverse_iterator rend() const { return reverse_iterator(begin()); }
291 : const_reverse_iterator crend() const { return reverse_iterator(begin()); }
292 :
293 12694 : bool empty() const {
294 12694 : return size_ == 0;
295 : }
296 :
297 182166 : size_type size() const {
298 182166 : return size_;
299 : }
300 :
301 : size_type max_size() const {
302 : return size_type(-1) / sizeof(T);
303 : }
304 :
305 1057 : void reserve(size_type capacity) {
306 1057 : if(capacity > capacity_) {
307 0 : grow_capacity_to_a_minimum_of(capacity);
308 : }
309 1057 : }
310 :
311 41703 : size_type capacity() const {
312 41703 : return capacity_;
313 : }
314 :
315 22428 : void set_size(size_type size) {
316 22428 : assert(size <= capacity());
317 22427 : size_ = size;
318 22427 : }
319 :
320 1688 : void clear() {
321 1688 : std::destroy(rbegin(), rend());
322 1688 : set_size(0);
323 1688 : }
324 :
325 1 : iterator insert(const_iterator pos, T &&value) {
326 1 : iterator it = const_cast<iterator>(pos);
327 1 : if(it == end()) {
328 0 : push_back(value);
329 0 : return end()-1;
330 : }
331 :
332 1 : assert(it >= begin() && it <= end() && "small_vector::insert iterator is out of bounds.");
333 :
334 1 : if(size() == capacity()) {
335 0 : size_t index = std::distance(begin(), it);
336 0 : grow_capacity_to_a_minimum_of(size()+1);
337 0 : it = begin() + index;
338 : }
339 :
340 1 : new (static_cast<void *>(end())) T(std::move(back()));
341 1 : std::move_backward(it, end()-1, end());
342 :
343 1 : const_iterator itElt = std::addressof(value);
344 :
345 1 : if(itElt >= it && itElt < end()) {
346 0 : ++itElt;
347 : }
348 :
349 1 : *it = std::move(*itElt);
350 :
351 1 : set_size(size()+1);
352 :
353 1 : return it;
354 : }
355 :
356 41 : iterator insert(const_iterator pos, const T &value) {
357 41 : iterator it = const_cast<iterator>(pos);
358 41 : if(it == end()) {
359 0 : push_back(value);
360 0 : return end()-1;
361 : }
362 :
363 41 : assert(it >= begin() && it <= end() && "small_vector::insert iterator is out of bounds.");
364 :
365 41 : if(size() == capacity()) {
366 0 : size_t index = std::distance(begin(), it);
367 0 : grow_capacity_to_a_minimum_of(size()+1);
368 0 : it = begin() + index;
369 : }
370 :
371 41 : new (static_cast<void *>(end())) T(std::move(back()));
372 41 : std::move_backward(it, end()-1, end());
373 :
374 41 : const_iterator itElt = std::addressof(value);
375 :
376 41 : if(itElt >= it && itElt < end()) {
377 41 : ++itElt;
378 : }
379 :
380 41 : *it = *itElt;
381 :
382 41 : set_size(size()+1);
383 :
384 41 : return it;
385 : }
386 :
387 : iterator insert(const_iterator pos, size_type count, const T &value) {
388 : iterator it = const_cast<iterator>(pos);
389 : size_t index = std::distance(begin(), it);
390 :
391 : if(it == end()) {
392 : reserve(size() + count);
393 : std::uninitialized_fill_n(end(), count, value);
394 : set_size(size()+count);
395 : return begin() + index;
396 : }
397 :
398 : assert(it >= begin() && it <= end() && "small_vector::insert iterator is out of bounds.");
399 :
400 : reserve(size() + count);
401 :
402 : it = begin() + index;
403 :
404 : size_t nbEltsInRange = std::distance(it, end());
405 :
406 : if(count <= nbEltsInRange) {
407 : std::uninitialized_copy(std::move_iterator<iterator>(end() - count),
408 : std::move_iterator<iterator>(end()), end());
409 : std::move_backward(it, end() - count, end());
410 : set_size(size()+count);
411 : std::fill_n(it, count, value);
412 : return it;
413 : }
414 :
415 : iterator oldEnd = end();
416 : set_size(size() + count);
417 : size_t nbOverwrittenElts = std::distance(it, oldEnd);
418 : std::uninitialized_copy(std::move_iterator<iterator>(it), std::move_iterator<iterator>(oldEnd), end() - nbOverwrittenElts);
419 :
420 : std::fill_n(it, nbOverwrittenElts, value);
421 :
422 : std::uninitialized_fill_n(oldEnd, count - nbOverwrittenElts, value);
423 :
424 : return it;
425 : }
426 :
427 : template<typename InputItTy,
428 : typename = typename std::enable_if<std::is_convertible<
429 : typename std::iterator_traits<InputItTy>::iterator_category,
430 : std::input_iterator_tag>::value>::type>
431 109 : iterator insert(const_iterator pos, InputItTy first, InputItTy last) {
432 109 : iterator it = const_cast<iterator>(pos);
433 :
434 109 : size_t index = std::distance(begin(), it);
435 109 : size_t nbEltsInInputRange = std::distance(first, last);
436 :
437 109 : if(it == end()) {
438 109 : reserve(size() + nbEltsInInputRange);
439 109 : std::uninitialized_copy(first, last, end());
440 109 : set_size(size() + nbEltsInInputRange);
441 109 : return begin() + index;
442 : }
443 :
444 0 : assert(it >= begin() && it <= end() && "small_vector::insert iterator is out of bounds.");
445 :
446 0 : reserve(size() + nbEltsInInputRange);
447 :
448 0 : it = begin() + index;
449 :
450 0 : size_t nbEltsInRangeItToEnd = std::distance(it, end());
451 :
452 0 : if(nbEltsInInputRange <= nbEltsInRangeItToEnd) {
453 0 : std::uninitialized_copy(std::move_iterator<iterator>(end() - nbEltsInInputRange),
454 : std::move_iterator<iterator>(end()), end());
455 0 : std::move_backward(it, end() - nbEltsInInputRange, end());
456 0 : std::copy(first, last, it);
457 0 : set_size(size() + nbEltsInInputRange);
458 0 : return it;
459 : }
460 :
461 0 : size_t rangeSizeDifference = nbEltsInInputRange - nbEltsInRangeItToEnd;
462 :
463 0 : std::uninitialized_move(it, end(), end() + rangeSizeDifference);
464 :
465 0 : for(iterator i = it; i != it + nbEltsInRangeItToEnd; ++it, ++first) {
466 0 : *i = *first;
467 : }
468 :
469 0 : std::uninitialized_copy(first, last, end());
470 :
471 0 : set_size(size() + nbEltsInInputRange);
472 :
473 0 : return it;
474 : }
475 :
476 8165 : void push_back(const T &value) {
477 8165 : if(size() >= capacity()) {
478 0 : grow_capacity_to_a_minimum_of(capacity()+1);
479 : }
480 :
481 8165 : new (static_cast<void *>(end())) T(value);
482 :
483 8165 : set_size(size()+1);
484 8165 : }
485 :
486 2 : iterator erase(const_iterator pos) {
487 2 : iterator it = const_cast<iterator>(pos);
488 :
489 2 : assert(it >= this->begin() && it < this->end() && "small_vector::erase iterator to erase from is out of bounds.");
490 :
491 2 : std::move(it+1, end(), it);
492 2 : pop_back();
493 :
494 2 : return it;
495 : }
496 :
497 206 : iterator erase(const_iterator first, const_iterator last) {
498 206 : iterator itFirst = const_cast<iterator>(first);
499 206 : iterator itLast = const_cast<iterator>(last);
500 :
501 206 : assert(itFirst <= itLast && "small_vector::erase trying to erase invalid range.");
502 206 : assert(itFirst >= this->begin() && itLast <= this->end() && "small_vector::erase range to erase is out of bounds.");
503 :
504 206 : iterator it = std::move(itLast, end(), itFirst);
505 206 : std::destroy(rbegin(), reverse_iterator(it));
506 206 : this->set_size(std::distance(begin(), it));
507 :
508 206 : return itFirst;
509 : }
510 :
511 779 : void push_back(T &&value) {
512 779 : if(size() >= capacity()) {
513 0 : grow_capacity_to_a_minimum_of(capacity()+1);
514 : }
515 :
516 779 : new (static_cast<void *>(end())) T(std::move(value));
517 :
518 779 : set_size(size()+1);
519 779 : }
520 :
521 : template <typename... Args>
522 4891 : reference emplace_back(Args &&... args) {
523 4891 : if(size() >= capacity()) {
524 1 : grow_capacity_to_a_minimum_of(capacity()+1);
525 : }
526 :
527 4891 : new (static_cast<void *>(end())) T(std::forward<Args>(args)...);
528 :
529 4891 : set_size(size()+1);
530 :
531 4891 : return back();
532 : }
533 :
534 1179 : void pop_back() {
535 1179 : assert(!empty());
536 1179 : set_size(size()-1);
537 1179 : end()->~T();
538 1179 : }
539 :
540 2 : void resize(size_type count) {
541 2 : if(count < size()) {
542 0 : std::destroy(rbegin(), reverse_iterator(begin() + count));
543 2 : }else if(count > size()) {
544 2 : if(capacity() < count) {
545 0 : grow_capacity_to_a_minimum_of(count);
546 : }
547 2 : std::uninitialized_value_construct(end(), begin() + count);
548 : }
549 2 : set_size(count);
550 2 : }
551 :
552 : void resize(size_type count, const value_type &value) {
553 : if(count < size()) {
554 : std::destroy(rbegin(), reverse_iterator(begin() + count));
555 : }else if(count > size()) {
556 : if(capacity() < count) {
557 : grow_capacity_to_a_minimum_of(count);
558 : }
559 : std::uninitialized_fill(end(), begin() + count, value);
560 : }
561 : set_size(count);
562 : }
563 :
564 : void swap(small_vector_base &rhs) {
565 : if(this == std::addressof(rhs)) {
566 : return;
567 : }
568 :
569 : if(!is_small() && !rhs.is_small()) {
570 : std::swap(capacity_, rhs.capacity_);
571 : std::swap(size_, rhs.size_);
572 : std::swap(beginPtr_, rhs.beginPtr_);
573 : return;
574 : }
575 :
576 : if(rhs.capacity() < size()) {
577 : rhs.grow_capacity_to_a_minimum_of(size());
578 : }
579 :
580 : if(capacity() < rhs.size()) {
581 : grow_capacity_to_a_minimum_of(rhs.size());
582 : }
583 :
584 : size_type minSize = std::min(size(), rhs.size());
585 :
586 : std::swap_ranges(begin(), begin() + minSize, rhs.begin());
587 :
588 : if(size() > rhs.size()) {
589 : size_type nbEltsDiff = size() - rhs.size();
590 : std::uninitialized_copy(begin() + minSize, end(), rhs.end());
591 : rhs.set_size(rhs.size() + nbEltsDiff);
592 : set_size(minSize);
593 : }else if(rhs.size() > size()) {
594 : size_type nbEltsDiff = rhs.size() - size();
595 : std::uninitialized_copy(rhs.begin() + minSize, rhs.end(), end());
596 : set_size(size() + nbEltsDiff);
597 : rhs.set_size(minSize);
598 : }
599 : }
600 :
601 : bool operator==(const small_vector_base &rhs) {
602 : return size() == rhs.size() && std::equal(begin(), end(), rhs.begin());
603 : }
604 :
605 16562 : bool is_small() const {
606 16562 : return beginPtr_ == getPointerToInternalStorage();
607 : }
608 :
609 32934 : void *getPointerToInternalStorage() const {
610 : return const_cast<void *>(reinterpret_cast<const void *>(reinterpret_cast<const char *>(this) +
611 32934 : offsetof(small_vector_internal_storage_offset_computation_structure<T>, firstElt)));
612 : }
613 :
614 0 : void reset_to_small() {
615 0 : beginPtr_ = getPointerToInternalStorage();
616 0 : capacity_ = originalCapacity_;
617 0 : size_ = 0;
618 0 : }
619 : };
620 :
621 : template <typename T, size_t N>
622 : struct small_vector_storage {
623 : alignas(T) char smallBuffer_[sizeof(T)*N];
624 : };
625 :
626 : template <typename T>
627 : struct alignas(T) small_vector_storage<T, 0> { };
628 :
629 : template <typename T, size_t N = 64>
630 : class small_vector : public small_vector_base<T>, public small_vector_storage<T, N> {
631 : public:
632 : using typename small_vector_base<T>::size_type;
633 : using typename small_vector_base<T>::difference_type;
634 : using typename small_vector_base<T>::value_type;
635 : using typename small_vector_base<T>::iterator;
636 : using typename small_vector_base<T>::const_iterator;
637 :
638 : using typename small_vector_base<T>::reverse_iterator;
639 : using typename small_vector_base<T>::const_reverse_iterator;
640 :
641 : using typename small_vector_base<T>::reference;
642 : using typename small_vector_base<T>::const_reference;
643 : using typename small_vector_base<T>::pointer;
644 : using typename small_vector_base<T>::const_pointer;
645 :
646 16372 : small_vector() : small_vector_base<T>(N) {}
647 :
648 1106 : explicit small_vector(size_t count, const T &value = T()) : small_vector() {
649 1106 : this->assign(count, value);
650 1106 : }
651 :
652 696 : small_vector(const small_vector &rhs) : small_vector() {
653 696 : if(!rhs.empty()) {
654 696 : small_vector_base<T>::operator=(rhs);
655 : }
656 696 : }
657 :
658 64 : small_vector(small_vector &&rhs) : small_vector() {
659 64 : if(!rhs.empty()) {
660 0 : small_vector_base<T>::operator=(std::move(rhs));
661 : }
662 64 : }
663 :
664 : template<typename InputItTy,
665 : typename = typename std::enable_if<std::is_convertible<
666 : typename std::iterator_traits<InputItTy>::iterator_category,
667 : std::input_iterator_tag>::value>::type>
668 : small_vector(InputItTy first, InputItTy last) : small_vector() {
669 : this->assign(first, last);
670 : }
671 :
672 3404 : small_vector(std::initializer_list<T> il) : small_vector() {
673 3404 : this->assign(il);
674 3404 : }
675 :
676 16372 : ~small_vector() {
677 16372 : std::destroy(this->rbegin(), this->rend());
678 16372 : if(!this->is_small()) {
679 29 : std::free(this->begin());
680 : }
681 16372 : }
682 :
683 : small_vector &operator=(const small_vector &rhs) {
684 : small_vector_base<T>::operator=(rhs);
685 : return *this;
686 : }
687 :
688 : small_vector &operator=(const small_vector_base<T> &rhs) {
689 : small_vector_base<T>::operator=(rhs);
690 : return *this;
691 : }
692 :
693 : small_vector &operator=(small_vector &&rhs) {
694 : small_vector_base<T>::operator=(std::move(rhs));
695 : return *this;
696 : }
697 :
698 161 : small_vector &operator=(small_vector_base<T> &&rhs) {
699 161 : small_vector_base<T>::operator=(std::move(rhs));
700 161 : return *this;
701 : }
702 :
703 : small_vector &operator=(std::initializer_list<T> il) {
704 : this->assign(il);
705 : return *this;
706 : }
707 : };
708 :
709 29 : inline uint64_t nextPowerOfTwo(uint64_t n) {
710 29 : n |= (n >> 1);
711 29 : n |= (n >> 2);
712 29 : n |= (n >> 4);
713 29 : n |= (n >> 8);
714 29 : n |= (n >> 16);
715 29 : n |= (n >> 32);
716 :
717 29 : return n + 1;
718 : }
719 :
720 : namespace std {
721 : template <typename T, size_t N>
722 : inline void swap(small_vector<T, N> &lhs, small_vector<T, N> &rhs) {
723 : lhs.swap(rhs);
724 : }
725 :
726 : template <typename T>
727 : inline void swap(small_vector_base<T> &lhs, small_vector_base<T> &rhs) {
728 : lhs.swap(rhs);
729 : }
730 : }
731 :
732 : template <typename T>
733 : struct is_instantiation_of_small_vector : std::false_type {};
734 :
735 : template <typename T, size_t N>
736 : struct is_instantiation_of_small_vector<small_vector<T, N>> : std::true_type {};
737 :
738 : #endif
|
