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

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

cpp: added mostly functioning version of std::vector, but inserts currently reallocate everytime
  • Property mode set to 100644
File size: 20.3 KB
Line 
1/*
2 * Copyright (c) 2017 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 // TODO: implement
156 return *this;
157 }
158
159 vector& operator=(initializer_list<T> init)
160 {
161 vector tmp{init, allocator_};
162 swap(tmp);
163
164 return *this;
165 }
166
167 template<class InputIterator>
168 void assign(InputIterator first, InputIterator last)
169 {
170 vector tmp{first, last};
171 swap(tmp);
172 }
173
174 void assign(size_type size, const T& val)
175 {
176 // Parenthesies required to avoid initializer list
177 // construction.
178 vector tmp(size, val);
179 swap(tmp);
180 }
181
182 void assign(initializer_list<T> init)
183 {
184 vector tmp{init};
185 swap(tmp);
186 }
187
188 allocator_type get_allocator() const noexcept
189 {
190 return allocator_type{};
191 }
192
193 iterator begin() noexcept
194 {
195 return &data_[0];
196 }
197
198 const_iterator begin() const noexcept
199 {
200 return &data_[0];
201 }
202
203 iterator end() noexcept
204 {
205 return begin() + size_;
206 }
207
208 const_iterator end() const noexcept
209 {
210 return begin() + size_;
211 }
212
213 reverse_iterator rbegin() noexcept
214 {
215 return make_reverse_iterator(begin());
216 }
217
218 const_reverse_iterator rbegin() const noexcept
219 {
220 return make_reverse_iterator(cbegin());
221 }
222
223 reverse_iterator rend() noexcept
224 {
225 return make_reverse_iterator(end());
226 }
227
228 const_reverse_iterator rend() const noexcept
229 {
230 return make_reverse_iterator(cend());
231 }
232
233 const_iterator cbegin() const noexcept
234 {
235 return &data_[0];
236 }
237
238 const_iterator cend() const noexcept
239 {
240 return cbegin() + size_;
241 }
242
243 const_reverse_iterator rcbegin() const noexcept
244 {
245 return rbegin();
246 }
247
248 const_reverse_iterator rcend() const noexcept
249 {
250 return rend();
251 }
252
253 size_type size() const noexcept
254 {
255 return size_;
256 }
257
258 size_type max_size() const noexcept
259 {
260 return std::allocator_traits<Allocator>::max_size(allocator_);
261 }
262
263 void resize(size_type sz)
264 {
265 resize_with_copy_(size_, capacity_);
266 }
267
268 void resize(size_type sz, const value_type& val)
269 {
270 auto old_size = size_;
271 resize_with_copy_(sz, capacity_);
272
273 for (size_type i = old_size - 1; i < size_; ++i)
274 data_[i] = val;
275 }
276
277 size_type capacity() const noexcept
278 {
279 return capacity_;
280 }
281
282 bool empty() const noexcept
283 {
284 return size_ == 0;
285 }
286
287 void reserve(size_type new_capacity)
288 {
289 // TODO: if new_capacity > max_size() throw
290 // length_error (this function shall have no
291 // effect in such case)
292 if (new_capacity > capacity_)
293 resize_with_copy_(size_, new_capacity);
294 }
295
296 void shrink_to_fit()
297 {
298 resize_with_copy_(size_, size_);
299 }
300
301 reference operator[](size_type idx)
302 {
303 return data_[idx];
304 }
305
306 const_reference operator[](size_type idx) const
307 {
308 return data_[idx];
309 }
310
311 reference at(size_type idx)
312 {
313 // TODO: bounds checking
314 return data_[idx];
315 }
316
317 const_reference at(size_type idx) const
318 {
319 // TODO: bounds checking
320 return data_[idx];
321 }
322
323 reference front()
324 {
325 /**
326 * Note: Calling front/back on an empty container
327 * is undefined, we opted for at-like
328 * behavior to provide our users with means
329 * to protect their programs from accidental
330 * accesses to an empty vector.
331 */
332 return at(0);
333 }
334
335 const_reference front() const
336 {
337 return at(0);
338 }
339
340 reference back()
341 {
342 return at(size_ - 1);
343 }
344
345 const_reference back() const
346 {
347 return at(size - 1);
348 }
349
350 T* data() noexcept
351 {
352 return data_;
353 }
354
355 const T* data() const noexcept
356 {
357 return data_;
358 }
359
360 template<class... Args>
361 reference emplace_back(Args&&... args)
362 {
363 if (size_ >= capacity_)
364 resize_with_copy_(size_, next_capacity_());
365
366 allocator_traits<Allocator>::construct(begin() + size_, forward<Args>(args)...);
367
368 return back();
369 }
370
371 // TODO: assert CopyInstertable etc with enable_if!
372 void push_back(const T& x)
373 {
374 if (size_ >= capacity_)
375 resize_with_copy_(size_, next_capacity_());
376 data_[size_++] = x;
377 }
378
379 void push_back(T&& x)
380 {
381 if (size_ >= capacity_)
382 resize_with_copy_(size_, next_capacity_());
383 data_[size_++] = forward<T>(x);
384 }
385
386 void pop_back()
387 {
388 destroy_from_end_until_(end() - 1);
389 }
390
391 template<class... Args>
392 iterator emplace(const_iterator position, Args&&... args)
393 {
394 auto idx = shift_right_(position, 1);
395 allocator_.construct(data_ + idx, std::forward<Args>(args)...);
396
397 return begin() + idx;
398 }
399
400 iterator insert(const_iterator position, const value_type& x)
401 {
402 /**
403 * Note: The reason that all insert functions are done in this weird
404 * way with an auxiliary vector instead of just shifting
405 * the elements is that we need to provide strong exception
406 * guarantee - in the case of exception our vector needs to
407 * stay in its pre-instert state and this swap method guarantees
408 * that.
409 * TODO: Avoid reallocation if it still fits!
410 */
411 size_type idx = static_cast<size_type>(position - cbegin());
412
413 vector tmp{};
414 tmp.resize_without_copy_(max(size_ + 1, capacity_));
415
416 // Copy before insertion index.
417 tmp.copy_(0, begin(), begin() + idx);
418
419 // Insertion.
420 tmp.data_[idx] = x;
421
422 // Copy after insertion index.
423 tmp.copy_(idx + 1, begin() + idx + 1, end());
424 tmp.size_ = size_ + 1;
425 swap(tmp);
426
427 return begin() + idx;
428 }
429
430 iterator insert(const_iterator position, value_type&& x)
431 {
432 size_type idx = static_cast<size_type>(position - cbegin());
433
434 vector tmp{};
435 tmp.resize_without_copy_(max(size_ + 1, capacity_));
436
437 // Copy before insertion index.
438 tmp.copy_(0, begin(), begin() + idx);
439
440 // Insertion.
441 tmp.data_[idx] = std::forward<value_type>(x);
442
443 // Copy after insertion index.
444 tmp.copy_(idx + 1, begin() + idx + 1, end());
445 tmp.size_ = size_ + 1;
446 swap(tmp);
447
448 return begin() + idx;
449 }
450
451 iterator insert(const_iterator position, size_type count, const value_type& x)
452 {
453 size_type idx = static_cast<size_type>(position - cbegin());
454
455 vector tmp{};
456 tmp.resize_without_copy_(max(size_ + 1, capacity_));
457
458 // Copy before insertion index.
459 tmp.copy_(0, begin(), begin() + idx);
460
461 // Insertion.
462 auto tmp_idx = idx;
463 for (size_type i = 0; i < count; ++i, ++tmp_idx)
464 tmp.data_[tmp_idx] = x;
465
466 // Copy after insertion index.
467 tmp.copy_(tmp_idx, begin() + idx, end());
468 tmp.size_ = size_ + count;
469 swap(tmp);
470
471 return begin() + idx;
472 }
473
474 template<class InputIterator>
475 iterator insert(const_iterator position, InputIterator first,
476 InputIterator last)
477 {
478 size_type idx = static_cast<size_type>(position - cbegin());
479 size_type count = static_cast<size_type>(last - first);
480
481 return insert_(idx, count, first, last);
482 }
483
484 iterator insert(const_iterator position, initializer_list<T> init)
485 {
486 size_type idx = static_cast<size_type>(position - cbegin());
487 size_type count = init.size();
488
489 return insert_(idx, count, init.begin(), init.end());
490 }
491
492 iterator erase(const_iterator position)
493 {
494 iterator pos = const_cast<iterator>(position);
495 copy(position + 1, cend(), pos);
496 --size_;
497
498 return pos;
499 }
500
501 iterator erase(const_iterator first, const_iterator last)
502 {
503 iterator pos = const_cast<iterator>(first);
504 copy(last, cend(), pos);
505 size_ -= static_cast<size_type>(last - first);
506
507 return pos;
508 }
509
510 void swap(vector& other)
511 noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value ||
512 allocator_traits<Allocator>::is_always_equal::value)
513 {
514 std::swap(data_, other.data_);
515 std::swap(size_, other.size_);
516 std::swap(capacity_, other.capacity_);
517 }
518
519 void clear() noexcept
520 {
521 // Note: Capacity remains unchanged.
522 destroy_from_end_until_(begin());
523 size_ = 0;
524 }
525
526 private:
527 value_type* data_;
528 size_type size_;
529 size_type capacity_;
530 Allocator allocator_;
531
532 void resize_without_copy_(size_type capacity)
533 {
534 if (data_)
535 allocator_.deallocate(data_, capacity_);
536
537 data_ = allocator_.allocate(capacity);
538 size_ = 0;
539 capacity_ = capacity;
540 }
541
542 void resize_with_copy_(size_type size, size_type capacity)
543 {
544 if (size < size_)
545 destroy_from_end_until_(begin() + size);
546
547 if(capacity_ == 0 || capacity_ < capacity)
548 {
549 auto new_data = allocator_.allocate(capacity);
550
551 auto to_copy = min(size, size_);
552 for (size_type i = 0; i < to_copy; ++i)
553 new_data[i] = move(data_[i]);
554
555 std::swap(data_, new_data);
556
557 allocator_.deallocate(new_data, capacity_);
558 }
559
560 capacity_ = capacity;
561 size_ = size;
562 }
563
564 void destroy_from_end_until_(iterator target)
565 {
566 if (!empty())
567 {
568 auto last = end();
569 while(last != target)
570 allocator_traits<Allocator>::destroy(allocator_, --last);
571 }
572 }
573
574 size_type next_capacity_(size_type hint = 0) const noexcept
575 {
576 if (hint != 0)
577 return max(capacity_ * 2, hint);
578 else
579 return max(capacity_ * 2, 2ul);
580 }
581
582 template<class Iterator>
583 void copy_(size_type idx, Iterator first, Iterator last)
584 {
585 for (size_type i = idx; first != last; ++i, ++first)
586 data_[i] = *first;
587 }
588
589 template<class Iterator>
590 iterator insert_(size_type idx, size_type count, Iterator first, Iterator last)
591 {
592 vector tmp{};
593 tmp.resize_without_copy_(max(size_ + count, capacity_));
594
595 // Copy before insertion index.
596 tmp.copy_(0, begin(), begin() + idx);
597
598 // Insertion.
599 tmp.copy_(idx, first, last);
600
601 // Copy after insertion index.
602 tmp.copy_(idx + count, begin() + idx, end());
603 tmp.size_ = size_ + count;
604 swap(tmp);
605
606 return begin() + idx;
607 }
608 };
609
610 template<class T, class Alloc>
611 bool operator==(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
612 {
613 // TODO: implement
614 return false;
615 }
616
617 template<class T, class Alloc>
618 bool operator<(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
619 {
620 // TODO: implement
621 return false;
622 }
623
624 template<class T, class Alloc>
625 bool operator!=(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
626 {
627 return !(lhs == rhs);
628 }
629
630 template<class T, class Alloc>
631 bool operator>(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
632 {
633 // TODO: implement
634 return false;
635 }
636
637 template<class T, class Alloc>
638 bool operator>=(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
639 {
640 // TODO: implement
641 return false;
642 }
643
644 template<class T, class Alloc>
645 bool operator<=(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
646 {
647 // TODO: implement
648 return false;
649 }
650
651 /**
652 * 23.3.6.6, specialized algorithms:
653 */
654 template<class T, class Alloc>
655 void swap(vector<T, Alloc>& lhs, vector<T, Alloc>& rhs)
656 noexcept(noexcept(lhs.swap(rhs)))
657 {
658 lhs.swap(rhs);
659 }
660}
661
662#endif
Note: See TracBrowser for help on using the repository browser.