source: mainline/uspace/lib/cpp/include/impl/vector.hpp@ a1c35cc

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

cpp: fixed typos in vector reverse iterator getters
  • Property mode set to 100644
File size: 19.8 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_VECTOR
30#define LIBCPP_VECTOR
31
32#include <algorithm>
33#include <initializer_list>
34#include <iterator>
35#include <memory>
36#include <utility>
37
38namespace std
39{
40 /**
41 * 23.3.6, vector:
42 */
43
44 template<class T, class Allocator = allocator<T>>
45 class vector
46 {
47 public:
48 using value_type = T;
49 using reference = value_type&;
50 using const_reference = const value_type&;
51 using allocator_type = Allocator;
52 using size_type = size_t;
53 using difference_type = ptrdiff_t;
54 using pointer = typename allocator_traits<Allocator>::pointer;
55 using const_pointer = typename allocator_traits<Allocator>::pointer;
56 using iterator = pointer;
57 using const_iterator = const_pointer;
58 using reverse_iterator = std::reverse_iterator<iterator>;
59 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
60
61 vector() noexcept
62 : vector{Allocator{}}
63 { /* DUMMY BODY */ }
64
65 explicit vector(const Allocator& alloc)
66 : data_{nullptr}, size_{}, capacity_{},
67 allocator_{alloc}
68 { /* DUMMY BODY */ }
69
70 explicit vector(size_type n, const Allocator& alloc = Allocator{})
71 : data_{}, size_{n}, capacity_{n}, allocator_{alloc}
72 {
73 data_ = allocator_.allocate(capacity_);
74
75 for (size_type i = 0; i < size_; ++i)
76 allocator_traits<Allocator>::construct(allocator_, data_ + i);
77 }
78
79 vector(size_type n, const T& val, const Allocator& alloc = Allocator{})
80 : data_{}, size_{n}, capacity_{n}, allocator_{alloc}
81 {
82 data_ = allocator_.allocate(capacity_);
83
84 for (size_type i = 0; i < size_; ++i)
85 data_[i] = val;
86 }
87
88 template<class InputIterator>
89 vector(InputIterator first, InputIterator last,
90 const Allocator& alloc = Allocator{})
91 {
92 // TODO: research constraints and provide multiple
93 // implementations via enable_if
94 }
95
96 vector(const vector& other)
97 : data_{nullptr}, size_{other.size_}, capacity_{other.capacity_},
98 allocator_{other.allocator_}
99 {
100 data_ = allocator_.allocate(capacity_);
101
102 for (size_type i = 0; i < size_; ++i)
103 data_[i] = other.data_[i];
104 }
105
106 vector(vector&& other) noexcept
107 : data_{other.data_}, size_{other.size_}, capacity_{other.capacity_},
108 allocator_{move(other.allocator_)}
109 {
110 // other is guaranteed to be empty()
111 other.size_ = other.capacity_ = 0;
112 other.data_ = nullptr;
113 }
114
115 vector(const vector& other, const Allocator& alloc)
116 : data_{nullptr}, size_{other.size_}, capacity_{other.capacity_},
117 allocator_{alloc}
118 {
119 data_ = allocator_.allocate(capacity_);
120
121 for (size_type i = 0; i < size_; ++i)
122 data_[i] = other.data_[i];
123 }
124
125 vector(initializer_list<T> init, const Allocator& alloc = Allocator{})
126 : data_{nullptr}, size_{init.size()}, capacity_{init.size()},
127 allocator_{alloc}
128 {
129 data_ = allocator_.allocate(capacity_);
130
131 auto it = init.begin();
132 for (size_type i = 0; it != init.end(); ++i, ++it)
133 {
134 data_[i] = *it;
135 }
136 }
137
138 ~vector()
139 {
140 allocator_.deallocate(data_, capacity_);
141 }
142
143 vector& operator=(const vector& other)
144 {
145 vector tmp{other};
146 swap(tmp);
147
148 return *this;
149 }
150
151 vector& operator=(vector&& other)
152 noexcept(allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
153 allocator_traits<Allocator>::is_always_equal::value)
154 {
155 if (data_)
156 allocator_.deallocate(data_, capacity_);
157
158 // TODO: test this
159 data_ = other.data_;
160 size_ = other.size_;
161 capacity_ = other.capacity_;
162 allocator_ = move(other.allocator_);
163
164 other.data_ = nullptr;
165 other.size_ = size_type{};
166 other.capacity_ = size_type{};
167 other.allocator_ = allocator_type{};
168 return *this;
169 }
170
171 vector& operator=(initializer_list<T> init)
172 {
173 vector tmp{init, allocator_};
174 swap(tmp);
175
176 return *this;
177 }
178
179 template<class InputIterator>
180 void assign(InputIterator first, InputIterator last)
181 {
182 vector tmp{first, last};
183 swap(tmp);
184 }
185
186 void assign(size_type size, const T& val)
187 {
188 // Parenthesies required to avoid initializer list
189 // construction.
190 vector tmp(size, val);
191 swap(tmp);
192 }
193
194 void assign(initializer_list<T> init)
195 {
196 vector tmp{init};
197 swap(tmp);
198 }
199
200 allocator_type get_allocator() const noexcept
201 {
202 return allocator_type{allocator_};
203 }
204
205 iterator begin() noexcept
206 {
207 return &data_[0];
208 }
209
210 const_iterator begin() const noexcept
211 {
212 return &data_[0];
213 }
214
215 iterator end() noexcept
216 {
217 return begin() + size_;
218 }
219
220 const_iterator end() const noexcept
221 {
222 return begin() + size_;
223 }
224
225 reverse_iterator rbegin() noexcept
226 {
227 return make_reverse_iterator(end());
228 }
229
230 const_reverse_iterator rbegin() const noexcept
231 {
232 return make_reverse_iterator(cend());
233 }
234
235 reverse_iterator rend() noexcept
236 {
237 return make_reverse_iterator(begin());
238 }
239
240 const_reverse_iterator rend() const noexcept
241 {
242 return make_reverse_iterator(cbegin());
243 }
244
245 const_iterator cbegin() const noexcept
246 {
247 return &data_[0];
248 }
249
250 const_iterator cend() const noexcept
251 {
252 return cbegin() + size_;
253 }
254
255 const_reverse_iterator crbegin() const noexcept
256 {
257 return rbegin();
258 }
259
260 const_reverse_iterator crend() const noexcept
261 {
262 return rend();
263 }
264
265 size_type size() const noexcept
266 {
267 return size_;
268 }
269
270 size_type max_size() const noexcept
271 {
272 return std::allocator_traits<Allocator>::max_size(allocator_);
273 }
274
275 void resize(size_type sz)
276 {
277 resize_with_copy_(size_, capacity_);
278 }
279
280 void resize(size_type sz, const value_type& val)
281 {
282 auto old_size = size_;
283 resize_with_copy_(sz, capacity_);
284
285 for (size_type i = old_size - 1; i < size_; ++i)
286 data_[i] = val;
287 }
288
289 size_type capacity() const noexcept
290 {
291 return capacity_;
292 }
293
294 bool empty() const noexcept
295 {
296 return size_ == 0;
297 }
298
299 void reserve(size_type new_capacity)
300 {
301 // TODO: if new_capacity > max_size() throw
302 // length_error (this function shall have no
303 // effect in such case)
304 if (new_capacity > capacity_)
305 resize_with_copy_(size_, new_capacity);
306 }
307
308 void shrink_to_fit()
309 {
310 resize_with_copy_(size_, size_);
311 }
312
313 reference operator[](size_type idx)
314 {
315 return data_[idx];
316 }
317
318 const_reference operator[](size_type idx) const
319 {
320 return data_[idx];
321 }
322
323 reference at(size_type idx)
324 {
325 // TODO: bounds checking
326 return data_[idx];
327 }
328
329 const_reference at(size_type idx) const
330 {
331 // TODO: bounds checking
332 return data_[idx];
333 }
334
335 reference front()
336 {
337 /**
338 * Note: Calling front/back on an empty container
339 * is undefined, we opted for at-like
340 * behavior to provide our users with means
341 * to protect their programs from accidental
342 * accesses to an empty vector.
343 */
344 return at(0);
345 }
346
347 const_reference front() const
348 {
349 return at(0);
350 }
351
352 reference back()
353 {
354 return at(size_ - 1);
355 }
356
357 const_reference back() const
358 {
359 return at(size - 1);
360 }
361
362 T* data() noexcept
363 {
364 return data_;
365 }
366
367 const T* data() const noexcept
368 {
369 return data_;
370 }
371
372 template<class... Args>
373 reference emplace_back(Args&&... args)
374 {
375 if (size_ >= capacity_)
376 resize_with_copy_(size_, next_capacity_());
377
378 allocator_traits<Allocator>::construct(allocator_,
379 begin() + size_, forward<Args>(args)...);
380
381 return back();
382 }
383
384 void push_back(const T& x)
385 {
386 if (size_ >= capacity_)
387 resize_with_copy_(size_, next_capacity_());
388 data_[size_++] = x;
389 }
390
391 void push_back(T&& x)
392 {
393 if (size_ >= capacity_)
394 resize_with_copy_(size_, next_capacity_());
395 data_[size_++] = forward<T>(x);
396 }
397
398 void pop_back()
399 {
400 destroy_from_end_until_(end() - 1);
401 --size_;
402 }
403
404 template<class... Args>
405 iterator emplace(const_iterator position, Args&&... args)
406 {
407 auto pos = const_cast<iterator>(position);
408
409 pos = shift_(pos, 1);
410 allocator_.construct(pos, forward<Args>(args)...);
411
412 return pos;
413 }
414
415 iterator insert(const_iterator position, const value_type& x)
416 {
417 auto pos = const_cast<iterator>(position);
418
419 pos = shift_(pos, 1);
420 *pos = x;
421
422 return pos;
423 }
424
425 iterator insert(const_iterator position, value_type&& x)
426 {
427 auto pos = const_cast<iterator>(position);
428
429 pos = shift_(pos, 1);
430 *pos = forward<value_type>(x);
431
432 return pos;
433 }
434
435 iterator insert(const_iterator position, size_type count, const value_type& x)
436 {
437 auto pos = const_cast<iterator>(position);
438
439 pos = shift_(pos, count);
440 auto copy_target = pos;
441 for (size_type i = 0; i < count; ++i)
442 *copy_target++ = x;
443
444 return pos;
445 }
446
447 template<class InputIterator>
448 iterator insert(const_iterator position, InputIterator first,
449 InputIterator last)
450 {
451 auto pos = const_cast<iterator>(position);
452 auto count = static_cast<size_type>(last - first);
453
454 pos = shift_(pos, count);
455 copy(first, last, pos);
456
457 return pos;
458 }
459
460 iterator insert(const_iterator position, initializer_list<T> init)
461 {
462 auto pos = const_cast<iterator>(position);
463
464 pos = shift_(pos, init.size());
465 copy(init.begin(), init.end(), pos);
466
467 return pos;
468 }
469
470 iterator erase(const_iterator position)
471 {
472 iterator pos = const_cast<iterator>(position);
473 copy(position + 1, cend(), pos);
474 --size_;
475
476 return pos;
477 }
478
479 iterator erase(const_iterator first, const_iterator last)
480 {
481 iterator pos = const_cast<iterator>(first);
482 copy(last, cend(), pos);
483 size_ -= static_cast<size_type>(last - first);
484
485 return pos;
486 }
487
488 void swap(vector& other)
489 noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value ||
490 allocator_traits<Allocator>::is_always_equal::value)
491 {
492 std::swap(data_, other.data_);
493 std::swap(size_, other.size_);
494 std::swap(capacity_, other.capacity_);
495 }
496
497 void clear() noexcept
498 {
499 // Note: Capacity remains unchanged.
500 destroy_from_end_until_(begin());
501 size_ = 0;
502 }
503
504 private:
505 value_type* data_;
506 size_type size_;
507 size_type capacity_;
508 allocator_type allocator_;
509
510 void resize_without_copy_(size_type capacity)
511 {
512 if (data_)
513 allocator_.deallocate(data_, capacity_);
514
515 data_ = allocator_.allocate(capacity);
516 size_ = 0;
517 capacity_ = capacity;
518 }
519
520 void resize_with_copy_(size_type size, size_type capacity)
521 {
522 if (size < size_)
523 destroy_from_end_until_(begin() + size);
524
525 if(capacity_ == 0 || capacity_ < capacity)
526 {
527 auto new_data = allocator_.allocate(capacity);
528
529 auto to_copy = min(size, size_);
530 for (size_type i = 0; i < to_copy; ++i)
531 new_data[i] = move(data_[i]);
532
533 std::swap(data_, new_data);
534
535 allocator_.deallocate(new_data, capacity_);
536 }
537
538 capacity_ = capacity;
539 size_ = size;
540 }
541
542 void destroy_from_end_until_(iterator target)
543 {
544 if (!empty())
545 {
546 auto last = end();
547 while(last != target)
548 allocator_traits<Allocator>::destroy(allocator_, --last);
549 }
550 }
551
552 size_type next_capacity_(size_type hint = 0) const noexcept
553 {
554 if (hint != 0)
555 return max(capacity_ * 2, hint);
556 else
557 return max(capacity_ * 2, 2ul);
558 }
559
560 iterator shift_(iterator position, size_type count)
561 {
562 if (size_ + count < capacity_)
563 {
564 copy_backward(position, end(), end() + count);
565 size_ += count;
566
567 return position;
568 }
569 else
570 {
571 auto start_idx = static_cast<size_type>(position - begin());
572 auto end_idx = start_idx + count;
573 auto new_size = size_ + count;
574
575 // Auxiliary vector for easier swap.
576 vector tmp{};
577 tmp.resize_without_copy_(max(new_size, capacity_));
578 tmp.size_ = new_size;
579
580 // Copy before insertion index.
581 copy(begin(), begin() + start_idx, tmp.begin());
582
583 // Copy after insertion index.
584 copy(begin() + start_idx, end(), tmp.begin() + end_idx);
585
586 swap(tmp);
587
588 // Position was invalidated!
589 return begin() + start_idx;
590 }
591 }
592 };
593
594 template<class T, class Alloc>
595 bool operator==(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
596 {
597 if (lhs.size() != rhs.size())
598 return false;
599
600 for (decltype(lhs.size()) i = 0; i < lhs.size(); ++i)
601 {
602 if (lhs[i] != rhs[i])
603 return false;
604 }
605
606 return true;
607 }
608
609 template<class T, class Alloc>
610 bool operator<(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
611 {
612 auto min_size = min(lhs.size(), rhs.size());
613 for (decltype(lhs.size()) i = 0; i < min_size; ++i)
614 {
615 if (lhs[i] >= rhs[i])
616 return false;
617 }
618
619 if (lhs.size() == rhs.size())
620 return true;
621 else
622 return lhs.size() < rhs.size();
623 }
624
625 template<class T, class Alloc>
626 bool operator!=(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
627 {
628 return !(lhs == rhs);
629 }
630
631 template<class T, class Alloc>
632 bool operator>(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
633 {
634 return rhs < lhs;
635 }
636
637 template<class T, class Alloc>
638 bool operator>=(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
639 {
640 return !(lhs < rhs);
641 }
642
643 template<class T, class Alloc>
644 bool operator<=(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
645 {
646 return !(rhs < lhs);
647 }
648
649 /**
650 * 23.3.6.6, specialized algorithms:
651 */
652 template<class T, class Alloc>
653 void swap(vector<T, Alloc>& lhs, vector<T, Alloc>& rhs)
654 noexcept(noexcept(lhs.swap(rhs)))
655 {
656 lhs.swap(rhs);
657 }
658
659 /**
660 * 23.3.7, class vector<bool>:
661 */
662
663 // TODO: implement
664}
665
666#endif
Note: See TracBrowser for help on using the repository browser.