source: mainline/uspace/lib/cpp/include/impl/deque.hpp@ cf51eae

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since cf51eae was 0e5e8bf9, checked in by Dzejrou <dzejrou@…>, 7 years ago

cpp: fixed bugs found by deque tests
  • Property mode set to 100644
File size: 37.7 KB
Line 
1/*
2 * Copyright (c) 2018 Jaroslav Jindrak
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#ifndef LIBCPP_DEQUE
30#define LIBCPP_DEQUE
31
32#include <algorithm>
33#include <initializer_list>
34#include <internal/insert_iterator.hpp>
35#include <iterator>
36#include <memory>
37
38namespace std
39{
40 template<class T, class Allocator = allocator<T>>
41 class deque;
42
43 namespace aux
44 {
45 /**
46 * Note: We decided that these iterators contain a
47 * reference to the container and an index, which
48 * allows us to use the already implemented operator[]
49 * on deque and also allows us to conform to the requirement
50 * of the standard that functions such as push_back
51 * invalidate the .end() iterator.
52 */
53
54 template<class T, class Allocator>
55 class deque_iterator;
56
57 template<class T, class Allocator>
58 class deque_const_iterator
59 {
60 public:
61 using size_type = typename deque<T, Allocator>::size_type;
62 using value_type = typename deque<T, Allocator>::value_type;
63 using reference = typename deque<T, Allocator>::const_reference;
64 using difference_type = size_type;
65 using pointer = const value_type*;
66 using iterator_category = random_access_iterator_tag;
67
68 deque_const_iterator(const deque<T, Allocator>& deq, size_type idx)
69 : deq_{deq}, idx_{idx}
70 { /* DUMMY BODY */ }
71
72 deque_const_iterator(const deque_const_iterator& other)
73 : deq_{other.deq_}, idx_{other.idx_}
74 { /* DUMMY BODY */ }
75
76 deque_const_iterator& operator=(const deque_const_iterator& other)
77 {
78 deq_ = other.deq_;
79 idx_ = other.idx_;
80
81 return *this;
82 }
83
84 reference operator*() const
85 {
86 return deq_[idx_];
87 }
88
89 pointer operator->() const
90 {
91 return addressof(deq_[idx_]);
92 }
93
94 deque_const_iterator& operator++()
95 {
96 ++idx_;
97
98 return *this;
99 }
100
101 deque_const_iterator operator++(int)
102 {
103 return deque_const_iterator{deq_, idx_++};
104 }
105
106 deque_const_iterator& operator--()
107 {
108 --idx_;
109
110 return *this;
111 }
112
113 deque_const_iterator operator--(int)
114 {
115 return deque_const_iterator{deq_, idx_--};
116 }
117
118 deque_const_iterator operator+(difference_type n)
119 {
120 return deque_const_iterator{deq_, idx_ + n};
121 }
122
123 deque_const_iterator& operator+=(difference_type n)
124 {
125 idx_ += n;
126
127 return *this;
128 }
129
130 deque_const_iterator operator-(difference_type n)
131 {
132 return deque_const_iterator{deq_, idx_ - n};
133 }
134
135 deque_const_iterator& operator-=(difference_type n)
136 {
137 idx_ -= n;
138
139 return *this;
140 }
141
142 reference operator[](difference_type n) const
143 {
144 return deq_[idx_ + n];
145 }
146
147 difference_type operator-(const deque_const_iterator& rhs)
148 {
149 return idx_ - rhs.idx_;
150 }
151
152 size_type idx() const
153 {
154 return idx_;
155 }
156
157 operator deque_iterator<T, Allocator>()
158 {
159 return deque_iterator{
160 const_cast<deque<T, Allocator>&>(deq_), idx_
161 };
162 }
163
164 private:
165 const deque<T, Allocator>& deq_;
166 size_type idx_;
167 };
168
169 template<class T, class Allocator>
170 bool operator==(const deque_const_iterator<T, Allocator>& lhs,
171 const deque_const_iterator<T, Allocator>& rhs)
172 {
173 return lhs.idx() == rhs.idx();
174 }
175
176 template<class T, class Allocator>
177 bool operator!=(const deque_const_iterator<T, Allocator>& lhs,
178 const deque_const_iterator<T, Allocator>& rhs)
179 {
180 return !(lhs == rhs);
181 }
182
183 template<class T, class Allocator>
184 class deque_iterator
185 {
186 public:
187 using size_type = typename deque<T, Allocator>::size_type;
188 using value_type = typename deque<T, Allocator>::value_type;
189 using reference = typename deque<T, Allocator>::reference;
190 using difference_type = size_type;
191 using pointer = value_type*;
192 using iterator_category = random_access_iterator_tag;
193
194 deque_iterator(deque<T, Allocator>& deq, size_type idx)
195 : deq_{deq}, idx_{idx}
196 { /* DUMMY BODY */ }
197
198 deque_iterator(const deque_iterator& other)
199 : deq_{other.deq_}, idx_{other.idx_}
200 { /* DUMMY BODY */ }
201
202 deque_iterator(const deque_const_iterator<T, Allocator>& other)
203 : deq_{other.deq_}, idx_{other.idx_}
204 { /* DUMMY BODY */ }
205
206 deque_iterator& operator=(const deque_iterator& other)
207 {
208 deq_ = other.deq_;
209 idx_ = other.idx_;
210
211 return *this;
212 }
213
214 deque_iterator& operator=(const deque_const_iterator<T, Allocator>& other)
215 {
216 deq_ = other.deq_;
217 idx_ = other.idx_;
218
219 return *this;
220 }
221
222 reference operator*()
223 {
224 return deq_[idx_];
225 }
226
227 pointer operator->()
228 {
229 return addressof(deq_[idx_]);
230 }
231
232 deque_iterator& operator++()
233 {
234 ++idx_;
235
236 return *this;
237 }
238
239 deque_iterator operator++(int)
240 {
241 return deque_iterator{deq_, idx_++};
242 }
243
244 deque_iterator& operator--()
245 {
246 --idx_;
247
248 return *this;
249 }
250
251 deque_iterator operator--(int)
252 {
253 return deque_iterator{deq_, idx_--};
254 }
255
256 deque_iterator operator+(difference_type n)
257 {
258 return deque_iterator{deq_, idx_ + n};
259 }
260
261 deque_iterator& operator+=(difference_type n)
262 {
263 idx_ += n;
264
265 return *this;
266 }
267
268 deque_iterator operator-(difference_type n)
269 {
270 return deque_iterator{deq_, idx_ - n};
271 }
272
273 deque_iterator& operator-=(difference_type n)
274 {
275 idx_ -= n;
276
277 return *this;
278 }
279
280 reference operator[](difference_type n) const
281 {
282 return deq_[idx_ + n];
283 }
284
285 difference_type operator-(const deque_iterator& rhs)
286 {
287 return idx_ - rhs.idx_;
288 }
289
290 size_type idx() const
291 {
292 return idx_;
293 }
294
295 operator deque_const_iterator<T, Allocator>()
296 {
297 return deque_const_iterator{deq_, idx_};
298 }
299
300 private:
301 deque<T, Allocator>& deq_;
302 size_type idx_;
303 };
304
305 template<class T, class Allocator>
306 bool operator==(const deque_iterator<T, Allocator>& lhs,
307 const deque_iterator<T, Allocator>& rhs)
308 {
309 return lhs.idx() == rhs.idx();
310 }
311
312 template<class T, class Allocator>
313 bool operator!=(const deque_iterator<T, Allocator>& lhs,
314 const deque_iterator<T, Allocator>& rhs)
315 {
316 return !(lhs == rhs);
317 }
318 }
319
320 /**
321 * 23.3.3 deque:
322 */
323
324 template<class T, class Allocator>
325 class deque
326 {
327 public:
328 using allocator_type = Allocator;
329 using value_type = T;
330 using reference = value_type&;
331 using const_reference = const value_type&;
332
333 using iterator = aux::deque_iterator<T, Allocator>;
334 using const_iterator = aux::deque_const_iterator<T, Allocator>;
335 using reverse_iterator = std::reverse_iterator<iterator>;
336 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
337
338 using size_type = typename allocator_traits<allocator_type>::size_type;
339 using difference_type = typename allocator_traits<allocator_type>::difference_type;
340 using pointer = typename allocator_traits<allocator_type>::pointer;
341 using const_pointer = typename allocator_traits<allocator_type>::const_pointer;
342
343 /**
344 * 23.3.3.2, construct/copy/destroy:
345 */
346
347 deque()
348 : deque{allocator_type{}}
349 { /* DUMMY BODY */ }
350
351 explicit deque(const allocator_type& alloc)
352 : allocator_{alloc}, front_bucket_idx_{bucket_size_},
353 back_bucket_idx_{0}, front_bucket_{default_front_},
354 back_bucket_{default_back_}, bucket_count_{default_bucket_count_},
355 bucket_capacity_{default_bucket_capacity_}, size_{}, data_{}
356 {
357 init_();
358 }
359
360 explicit deque(size_type n, const allocator_type& alloc = allocator_type{})
361 : allocator_{alloc}, front_bucket_idx_{bucket_size_}, back_bucket_idx_{},
362 front_bucket_{}, back_bucket_{}, bucket_count_{},
363 bucket_capacity_{}, size_{n}, data_{}
364 {
365 prepare_for_size_(n);
366 init_();
367
368 for (size_type i = 0; i < size_; ++i)
369 allocator_.construct(&(*this)[i]);
370 back_bucket_idx_ = size_ % bucket_size_;
371 }
372
373 deque(size_type n, const value_type& value, const allocator_type& alloc = allocator_type{})
374 : allocator_{alloc}, front_bucket_idx_{bucket_size_}, back_bucket_idx_{},
375 front_bucket_{}, back_bucket_{}, bucket_count_{},
376 bucket_capacity_{}, size_{n}, data_{}
377 {
378 prepare_for_size_(n);
379 init_();
380
381 for (size_type i = 0; i < size_; ++i)
382 (*this)[i] = value;
383 back_bucket_idx_ = size_ % bucket_size_;
384 }
385
386 template<class InputIterator>
387 deque(InputIterator first, InputIterator last,
388 const allocator_type& alloc = allocator_type{})
389 : allocator_{alloc}, front_bucket_idx_{bucket_size_},
390 back_bucket_idx_{}, front_bucket_{}, back_bucket_{},
391 bucket_count_{}, bucket_capacity_{}, size_{},
392 data_{}
393 {
394 copy_from_range_(first, last);
395 }
396
397 deque(const deque& other)
398 : deque{other.begin(), other.end(), other.allocator_}
399 { /* DUMMY BODY */ }
400
401 deque(deque&& other)
402 : allocator_{move(other.allocator_)},
403 front_bucket_idx_{other.front_bucket_idx_},
404 back_bucket_idx_{other.back_bucket_idx_},
405 front_bucket_{other.front_bucket_},
406 back_bucket_{other.back_bucket_},
407 bucket_count_{other.bucket_count_},
408 bucket_capacity_{other.bucket_capacity_},
409 size_{other.size_}, data_{other.data_}
410 {
411 other.data_ = nullptr;
412 other.clear();
413 }
414
415 deque(const deque& other, const allocator_type& alloc)
416 : deque{other.begin(), other.end(), alloc}
417 { /* DUMMY BODY */ }
418
419 deque(deque&& other, const allocator_type& alloc)
420 : allocator_{alloc},
421 front_bucket_idx_{other.front_bucket_idx_},
422 back_bucket_idx_{other.front_bucket_idx_},
423 front_bucket_{other.front_bucket_},
424 back_bucket_{other.back_bucket_},
425 bucket_count_{other.bucket_count_},
426 bucket_capacity_{other.bucket_capacity_},
427 size_{other.size_}, data_{other.data_}
428 {
429 other.data_ = nullptr;
430 other.clear();
431 }
432
433 deque(initializer_list<T> init, const allocator_type& alloc = allocator_type{})
434 : allocator_{alloc}, front_bucket_idx_{bucket_size_},
435 back_bucket_idx_{}, front_bucket_{}, back_bucket_{},
436 bucket_count_{}, bucket_capacity_{}, size_{},
437 data_{}
438 {
439 copy_from_range_(init.begin(), init.end());
440 }
441
442 ~deque()
443 {
444 fini_();
445 }
446
447 deque& operator=(const deque& other)
448 {
449 if (data_)
450 fini_();
451
452 copy_from_range_(other.begin(), other.end());
453
454 return *this;
455 }
456
457 deque& operator=(deque&& other)
458 noexcept(allocator_traits<allocator_type>::is_always_equal::value)
459 {
460 swap(other);
461 other.clear();
462
463 return *this;
464 }
465
466 deque& operator=(initializer_list<T> init)
467 {
468 if (data_)
469 fini_();
470
471 copy_from_range_(init.begin(), init.end());
472
473 return *this;
474 }
475
476 template<class InputIterator>
477 void assign(InputIterator first, InputIterator last)
478 {
479 copy_from_range_(first, last);
480 }
481
482 void assign(size_type n, const T& value)
483 {
484 prepare_for_size_(n);
485 init_();
486 size_ = n;
487
488 auto it = begin();
489 for (size_type i = size_type{}; i < n; ++i)
490 *it++ = value;
491 }
492
493 void assign(initializer_list<T> init)
494 {
495 copy_from_range_(init.begin(), init.end());
496 }
497
498 allocator_type get_allocator() const noexcept
499 {
500 return allocator_;
501 }
502
503 iterator begin() noexcept
504 {
505 return aux::deque_iterator{*this, 0};
506 }
507
508 const_iterator begin() const noexcept
509 {
510 return aux::deque_const_iterator{*this, 0};
511 }
512
513 iterator end() noexcept
514 {
515 return aux::deque_iterator{*this, size_};
516 }
517
518 const_iterator end() const noexcept
519 {
520 return aux::deque_const_iterator{*this, size_};
521 }
522
523 reverse_iterator rbegin() noexcept
524 {
525 return make_reverse_iterator(end());
526 }
527
528 const_reverse_iterator rbegin() const noexcept
529 {
530 return make_reverse_iterator(cend());
531 }
532
533 reverse_iterator rend() noexcept
534 {
535 return make_reverse_iterator(begin());
536 }
537
538 const_reverse_iterator rend() const noexcept
539 {
540 return make_reverse_iterator(cbegin());
541 }
542
543 const_iterator cbegin() const noexcept
544 {
545 return aux::deque_const_iterator{*this, 0};
546 }
547
548 const_iterator cend() const noexcept
549 {
550 return aux::deque_const_iterator{*this, size_};
551 }
552
553 const_reverse_iterator crbegin() const noexcept
554 {
555 return make_reverse_iterator(cend());
556 }
557
558 const_reverse_iterator crend() const noexcept
559 {
560 return make_reverse_iterator(cbegin());
561 }
562
563 /**
564 * 23.3.3.3, capacity:
565 */
566
567 size_type size() const noexcept
568 {
569 return size_;
570 }
571
572 size_type max_size() const noexcept
573 {
574 return allocator_traits<allocator_type>::max_size(allocator_);
575 }
576
577 void resize(size_type sz)
578 {
579 if (sz <= size_)
580 {
581 auto count = size_ - sz;
582 for (size_type i = 0; i < count; ++i)
583 pop_back();
584 }
585 else
586 {
587 value_type value{};
588 auto count = sz - size_;
589 for (size_type i = 0; i < count; ++i)
590 push_back(value);
591 }
592 }
593
594 void resize(size_type sz, const value_type& value)
595 {
596 if (sz <= size_)
597 {
598 auto count = size_ - sz;
599 for (size_type i = 0; i < count; ++i)
600 pop_back();
601 }
602 else
603 {
604 auto count = sz - size_;
605 for (size_type i = 0; i < count; ++i)
606 push_back(value);
607 }
608 }
609
610 void shrink_to_fit()
611 {
612 /**
613 * We lazily allocate buckets and eagerily deallocate them.
614 * We cannot go into smaller pieces as buckets have fixed size.
615 * Because of this, shrink_to_fit has no effect (as permitted
616 * by the standard).
617 */
618 }
619
620 bool empty() const noexcept
621 {
622 return size_ == size_type{};
623 }
624
625 reference operator[](size_type idx)
626 {
627 return data_[get_bucket_index_(idx)][get_element_index_(idx)];
628 }
629
630 const_reference operator[](size_type idx) const
631 {
632 return data_[get_bucket_index_(idx)][get_element_index_(idx)];
633 }
634
635 reference at(size_type idx)
636 {
637 // TODO: bounds checking
638 return operator[](idx);
639 }
640
641 const_reference at(size_type idx) const
642 {
643 // TODO: bounds checking
644 return operator[](idx);
645 }
646
647 reference front()
648 {
649 return *begin();
650 }
651
652 const_reference front() const
653 {
654 return *cbegin();
655 }
656
657 reference back()
658 {
659 auto tmp = end();
660
661 return *(--tmp);
662 }
663
664 const_reference back() const
665 {
666 auto tmp = cend();
667
668 return *(--tmp);
669 }
670
671 /**
672 * 23.3.3.4, modifiers:
673 */
674
675 template<class... Args>
676 void emplace_front(Args&&... args)
677 {
678 if (front_bucket_idx_ == 0)
679 add_new_bucket_front_();
680
681 allocator_traits<allocator_type>::construct(
682 allocator_,
683 &data_[front_bucket_][--front_bucket_idx_],
684 forward<Args>(args)...
685 );
686
687 ++size_;
688 }
689
690 template<class... Args>
691 void emplace_back(Args&&... args)
692 {
693 allocator_traits<allocator_type>::construct(
694 allocator_,
695 &data_[back_bucket_][back_bucket_idx_++],
696 forward<Args>(args)...
697 );
698
699 ++size_;
700
701 if (back_bucket_idx_ >= bucket_size_)
702 add_new_bucket_back_();
703 }
704
705 template<class... Args>
706 iterator emplace(const_iterator position, Args&&... args)
707 {
708 auto idx = position.idx();
709 shift_right_(idx, 1);
710
711 allocator_traits<allocator_type>::construct(
712 allocator_,
713 &data_[get_bucket_index_(idx)][get_element_index_(idx)],
714 forward<Args>(args)...
715 );
716 ++size_;
717
718 return iterator{*this, idx};
719 }
720
721 void push_front(const value_type& value)
722 {
723 if (front_bucket_idx_ == 0)
724 add_new_bucket_front_();
725
726 data_[front_bucket_][--front_bucket_idx_] = value;
727 ++size_;
728 }
729
730 void push_front(value_type&& value)
731 {
732 if (front_bucket_idx_ == 0)
733 add_new_bucket_front_();
734
735 data_[front_bucket_][--front_bucket_idx_] = forward<value_type>(value);
736 ++size_;
737 }
738
739 void push_back(const value_type& value)
740 {
741 data_[back_bucket_][back_bucket_idx_++] = value;
742 ++size_;
743
744 if (back_bucket_idx_ >= bucket_size_)
745 add_new_bucket_back_();
746 }
747
748 void push_back(value_type&& value)
749 {
750 data_[back_bucket_][back_bucket_idx_++] = forward<value_type>(value);
751 ++size_;
752
753 if (back_bucket_idx_ >= bucket_size_)
754 add_new_bucket_back_();
755 }
756
757 iterator insert(const_iterator position, const value_type& value)
758 {
759 auto idx = position.idx();
760 shift_right_(idx, 1);
761
762 /**
763 * Note: One may notice that when working with the deque
764 * iterator, we use its index without any checks.
765 * This is because a valid iterator will always have
766 * a valid index as functions like pop_back or erase
767 * invalidate iterators.
768 */
769 data_[get_bucket_index_(idx)][get_element_index_(idx)] = value;
770 ++size_;
771
772 return iterator{*this, idx};
773 }
774
775 iterator insert(const_iterator position, value_type&& value)
776 {
777 auto idx = position.idx();
778 shift_right_(idx, 1);
779
780 data_[get_bucket_index_(idx)][get_element_index_(idx)] = forward<value_type>(value);
781 ++size_;
782
783 return iterator{*this, idx};
784 }
785
786 iterator insert(const_iterator position, size_type n, const value_type& value)
787 {
788 return insert(
789 position,
790 aux::insert_iterator<int>{0u, value},
791 aux::insert_iterator<int>{n}
792 );
793 }
794
795 template<class InputIterator>
796 iterator insert(const_iterator position, InputIterator first, InputIterator last)
797 {
798 auto idx = position.idx();
799 auto count = distance(first, last);
800
801 if (idx < size_ / 2)
802 {
803 shift_left_(idx, count);
804
805 iterator it{*this, idx - 1};
806 while (first != last)
807 *it++ = *first++;
808 }
809 else
810 {
811 shift_right_(idx, count);
812
813 iterator it{*this, idx};
814 while (first != last)
815 *it++ = *first++;
816 }
817
818 size_ += count;
819
820 return iterator{*this, idx};
821 }
822
823 iterator insert(const_iterator position, initializer_list<value_type> init)
824 {
825 return insert(position, init.begin(), init.end());
826 }
827
828 void pop_back()
829 {
830 if (empty())
831 return;
832
833 if (back_bucket_idx_ == 0)
834 { // Means we gotta pop data_[back_bucket_ - 1][bucket_size_ - 1]!
835 if (data_[back_bucket_])
836 allocator_.deallocate(data_[back_bucket_], bucket_size_);
837
838 --back_bucket_;
839 back_bucket_idx_ = bucket_size_ - 1;
840 }
841 else
842 --back_bucket_idx_;
843
844 allocator_.destroy(&data_[back_bucket_][back_bucket_idx_]);
845 --size_;
846 }
847
848 void pop_front()
849 {
850 if (empty())
851 return;
852
853 if (front_bucket_idx_ >= bucket_size_)
854 { // Means we gotta pop data_[front_bucket_ + 1][0]!
855 if (data_[front_bucket_])
856 allocator_.deallocate(data_[front_bucket_], bucket_size_);
857
858 ++front_bucket_;
859 front_bucket_idx_ = 1;
860
861 allocator_.destroy(&data_[front_bucket_][0]);
862 }
863 else
864 {
865 allocator_.destroy(&data_[front_bucket_][front_bucket_idx_]);
866
867 ++front_bucket_idx_;
868 }
869
870 --size_;
871 }
872
873 iterator erase(const_iterator position)
874 {
875 auto idx = position.idx();
876 copy(
877 iterator{*this, idx + 1},
878 end(),
879 iterator{*this, idx}
880 );
881
882 /**
883 * Note: We need to not only decrement size,
884 * but also take care of any issues caused
885 * by decrement bucket indices, which pop_back
886 * does for us.
887 */
888 pop_back();
889
890 return iterator{*this, idx};
891 }
892
893 iterator erase(const_iterator first, const_iterator last)
894 {
895 if (first == last)
896 return first;
897
898 auto first_idx = first.idx();
899 auto last_idx = last.idx();
900 auto count = distance(first, last);
901
902 copy(
903 iterator{*this, last_idx},
904 end(),
905 iterator{*this, first_idx}
906 );
907
908 for (size_type i = 0; i < count; ++i)
909 pop_back();
910
911 return iterator{*this, first_idx};
912 }
913
914 void swap(deque& other)
915 noexcept(allocator_traits<allocator_type>::is_always_equal::value)
916 {
917 std::swap(allocator_, other.allocator_);
918 std::swap(front_bucket_idx_, other.front_bucket_idx_);
919 std::swap(back_bucket_idx_, other.back_bucket_idx_);
920 std::swap(front_bucket_, other.front_bucket_);
921 std::swap(back_bucket_, other.back_bucket_);
922 std::swap(bucket_count_, other.bucket_count_);
923 std::swap(bucket_capacity_, other.bucket_capacity_);
924 std::swap(size_, other.size_);
925 std::swap(data_, other.data_);
926 }
927
928 void clear() noexcept
929 {
930 if (data_)
931 fini_();
932
933 front_bucket_ = default_front_;
934 back_bucket_ = default_back_;
935 bucket_count_ = default_bucket_count_;
936 bucket_capacity_ = default_bucket_capacity_;
937 size_ = size_type{};
938
939 init_();
940 }
941
942 private:
943 allocator_type allocator_;
944
945 /**
946 * Note: In our implementation, front_bucket_idx_
947 * points at the first element and back_bucket_idx_
948 * points at the one past last element. Because of this,
949 * some operations may be done in inverse order
950 * depending on the side they are applied to.
951 */
952 size_type front_bucket_idx_;
953 size_type back_bucket_idx_;
954 size_type front_bucket_;
955 size_type back_bucket_;
956
957 static constexpr size_type bucket_size_{16};
958 static constexpr size_type default_bucket_count_{2};
959 static constexpr size_type default_bucket_capacity_{4};
960 static constexpr size_type default_front_{1};
961 static constexpr size_type default_back_{2};
962
963 size_type bucket_count_;
964 size_type bucket_capacity_;
965 size_type size_{};
966
967 value_type** data_;
968
969 void init_()
970 {
971 data_ = new value_type*[bucket_capacity_];
972
973 for (size_type i = front_bucket_; i <= back_bucket_; ++i)
974 data_[i] = allocator_.allocate(bucket_size_);
975 }
976
977 void prepare_for_size_(size_type size)
978 {
979 if (data_)
980 fini_();
981
982 bucket_count_ = bucket_capacity_ = size / bucket_size_ + 2;
983
984 front_bucket_ = 0;
985 back_bucket_ = bucket_capacity_ - 1;
986
987 front_bucket_idx_ = bucket_size_;
988 back_bucket_idx_ = size % bucket_size_;
989 }
990
991 template<class Iterator>
992 void copy_from_range_(Iterator first, Iterator last)
993 {
994 size_ = distance(first, last);
995 prepare_for_size_(size_);
996 init_();
997
998 auto it = begin();
999 while (first != last)
1000 *it++ = *first++;
1001 }
1002
1003 void ensure_space_front_(size_type idx, size_type count)
1004 {
1005 auto free_space = bucket_size_ - elements_in_front_bucket_();
1006 if (front_bucket_idx_ == 0)
1007 free_space = 0;
1008
1009 if (count <= free_space)
1010 {
1011 front_bucket_idx_ -= count;
1012 return;
1013 }
1014
1015 count -= free_space;
1016
1017 auto buckets_needed = count / bucket_size_;
1018 if (count % bucket_size_ != 0)
1019 ++buckets_needed;
1020
1021 for (size_type i = size_type{}; i < buckets_needed; ++i)
1022 add_new_bucket_front_();
1023
1024 front_bucket_idx_ = bucket_size_ - (count % bucket_size_);
1025 }
1026
1027 void ensure_space_back_(size_type idx, size_type count)
1028 {
1029 auto free_space = bucket_size_ - back_bucket_idx_;
1030 if (count < free_space)
1031 return;
1032
1033 count -= free_space;
1034 auto buckets_needed = count / bucket_size_;
1035 if (count % bucket_size_ != 0)
1036 ++buckets_needed;
1037
1038 for (size_type i = size_type{}; i < buckets_needed; ++i)
1039 add_new_bucket_back_();
1040
1041 back_bucket_idx_ = (back_bucket_idx_ + count) % bucket_size_;
1042 }
1043
1044 void shift_right_(size_type idx, size_type count)
1045 {
1046 ensure_space_back_(idx, count);
1047
1048 iterator it{*this, idx};
1049 copy_backward(it, end(), end() + count - 1);
1050
1051 }
1052
1053 void shift_left_(size_type idx, size_type count)
1054 {
1055 ensure_space_front_(idx, count);
1056
1057 copy(
1058 iterator{*this, count},
1059 iterator{*this, idx + count - 1},
1060 iterator{*this, 0}
1061 );
1062 }
1063
1064 void fini_()
1065 {
1066 for (size_type i = front_bucket_; i <= back_bucket_; ++i)
1067 allocator_.deallocate(data_[i], bucket_size_);
1068
1069 delete[] data_;
1070 data_ = nullptr;
1071 }
1072
1073 bool has_bucket_space_back_() const
1074 {
1075 return back_bucket_ < bucket_capacity_ - 1;
1076 }
1077
1078 bool has_bucket_space_front_() const
1079 {
1080 return front_bucket_ > 0;
1081 }
1082
1083 void add_new_bucket_back_()
1084 {
1085 if (!has_bucket_space_back_())
1086 expand_();
1087
1088 ++back_bucket_;
1089 ++bucket_count_;
1090 data_[back_bucket_] = allocator_.allocate(bucket_size_);
1091 back_bucket_idx_ = size_type{};
1092 }
1093
1094 void add_new_bucket_front_()
1095 {
1096 if (!has_bucket_space_front_())
1097 expand_();
1098
1099 --front_bucket_;
1100 ++bucket_count_;
1101 data_[front_bucket_] = allocator_.allocate(bucket_size_);
1102 front_bucket_idx_ = bucket_size_;
1103 }
1104
1105 void expand_()
1106 {
1107 bucket_capacity_ *= 2;
1108 value_type** new_data = new value_type*[bucket_capacity_];
1109
1110 /**
1111 * Note: This currently expands both sides whenever one reaches
1112 * its limit. Might be better to expand only one (or both when
1113 * the other is near its limit)?
1114 */
1115 size_type new_front = bucket_capacity_ / 4;
1116 size_type new_back = new_front + bucket_count_ - 1;
1117
1118 for (size_type i = new_front, j = front_bucket_; i <= new_back; ++i, ++j)
1119 new_data[i] = move(data_[j]);
1120 std::swap(data_, new_data);
1121
1122 delete[] new_data;
1123 front_bucket_ = new_front;
1124 back_bucket_ = new_back;
1125 }
1126
1127 size_type get_bucket_index_(size_type idx) const
1128 {
1129 if (idx < elements_in_front_bucket_())
1130 return front_bucket_;
1131
1132 idx -= elements_in_front_bucket_();
1133 return idx / bucket_size_ + front_bucket_ + 1;
1134 }
1135
1136 size_type get_element_index_(size_type idx) const
1137 {
1138 if (idx < elements_in_front_bucket_())
1139 return bucket_size_ - elements_in_front_bucket_() + idx;
1140
1141 idx -= elements_in_front_bucket_();
1142 return idx % bucket_size_;
1143 }
1144
1145 size_type elements_in_front_bucket_() const
1146 {
1147 return bucket_size_ - front_bucket_idx_;
1148 }
1149 };
1150
1151 template<class T, class Allocator>
1152 bool operator==(const deque<T, Allocator>& lhs, const deque<T, Allocator>& rhs)
1153 {
1154 if (lhs.size() != rhs.size())
1155 return false;
1156
1157 for (decltype(lhs.size()) i = 0; i < lhs.size(); ++i)
1158 {
1159 if (lhs[i] != rhs[i])
1160 return false;
1161 }
1162
1163 return true;
1164 }
1165
1166 template<class T, class Allocator>
1167 bool operator<(const deque<T, Allocator>& lhs, const deque<T, Allocator>& rhs)
1168 {
1169 auto min_size = min(lhs.size(), rhs.size());
1170 for (decltype(lhs.size()) i = 0; i < min_size; ++i)
1171 {
1172 if (lhs[i] >= rhs[i])
1173 return false;
1174 }
1175
1176 if (lhs.size() == rhs.size())
1177 return true;
1178 else
1179 return lhs.size() < rhs.size();
1180 }
1181
1182 template<class T, class Allocator>
1183 bool operator!=(const deque<T, Allocator>& lhs, const deque<T, Allocator>& rhs)
1184 {
1185 return !(lhs == rhs);
1186 }
1187
1188 template<class T, class Allocator>
1189 bool operator>(const deque<T, Allocator>& lhs, const deque<T, Allocator>& rhs)
1190 {
1191 return rhs < lhs;
1192 }
1193
1194 template<class T, class Allocator>
1195 bool operator<=(const deque<T, Allocator>& lhs, const deque<T, Allocator>& rhs)
1196 {
1197 return !(rhs < lhs);
1198 }
1199
1200 template<class T, class Allocator>
1201 bool operator>=(const deque<T, Allocator>& lhs, const deque<T, Allocator>& rhs)
1202 {
1203 return !(lhs < rhs);
1204 }
1205
1206 /**
1207 * 23.3.3.5, deque specialized algorithms:
1208 */
1209
1210 template<class T, class Allocator>
1211 void swap(deque<T, Allocator>& lhs, deque<T, Allocator>& rhs)
1212 noexcept(noexcept(lhs.swap(rhs)))
1213 {
1214 lhs.swap(rhs);
1215 }
1216}
1217
1218#endif
Note: See TracBrowser for help on using the repository browser.