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

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

cpp: fixed non-shrinking vector issue
  • Property mode set to 100644
File size: 19.0 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{allocator_};
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(end());
216 }
217
218 const_reverse_iterator rbegin() const noexcept
219 {
220 return make_reverse_iterator(cend());
221 }
222
223 reverse_iterator rend() noexcept
224 {
225 return make_reverse_iterator(begin());
226 }
227
228 const_reverse_iterator rend() const noexcept
229 {
230 return make_reverse_iterator(cbegin());
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(allocator_,
367 begin() + size_, forward<Args>(args)...);
368
369 return back();
370 }
371
372 // TODO: assert CopyInstertable etc with enable_if!
373 void push_back(const T& x)
374 {
375 if (size_ >= capacity_)
376 resize_with_copy_(size_, next_capacity_());
377 data_[size_++] = x;
378 }
379
380 void push_back(T&& x)
381 {
382 if (size_ >= capacity_)
383 resize_with_copy_(size_, next_capacity_());
384 data_[size_++] = forward<T>(x);
385 }
386
387 void pop_back()
388 {
389 destroy_from_end_until_(end() - 1);
390 --size_;
391 }
392
393 template<class... Args>
394 iterator emplace(const_iterator position, Args&&... args)
395 {
396 auto pos = const_cast<iterator>(position);
397
398 pos = shift_(pos, 1);
399 allocator_.construct(pos, forward<Args>(args)...);
400
401 return pos;
402 }
403
404 iterator insert(const_iterator position, const value_type& x)
405 {
406 auto pos = const_cast<iterator>(position);
407
408 pos = shift_(pos, 1);
409 *pos = x;
410
411 return pos;
412 }
413
414 iterator insert(const_iterator position, value_type&& x)
415 {
416 auto pos = const_cast<iterator>(position);
417
418 pos = shift_(pos, 1);
419 *pos = forward<value_type>(x);
420
421 return pos;
422 }
423
424 iterator insert(const_iterator position, size_type count, const value_type& x)
425 {
426 auto pos = const_cast<iterator>(position);
427
428 pos = shift_(pos, count);
429 auto copy_target = pos;
430 for (size_type i = 0; i < count; ++i)
431 *copy_target++ = x;
432
433 return pos;
434 }
435
436 template<class InputIterator>
437 iterator insert(const_iterator position, InputIterator first,
438 InputIterator last)
439 {
440 auto pos = const_cast<iterator>(position);
441 auto count = static_cast<size_type>(last - first);
442
443 pos = shift_(pos, count);
444 copy(first, last, pos);
445
446 return pos;
447 }
448
449 iterator insert(const_iterator position, initializer_list<T> init)
450 {
451 auto pos = const_cast<iterator>(position);
452
453 pos = shift_(pos, init.size());
454 copy(init.begin(), init.end(), pos);
455
456 return pos;
457 }
458
459 iterator erase(const_iterator position)
460 {
461 iterator pos = const_cast<iterator>(position);
462 copy(position + 1, cend(), pos);
463 --size_;
464
465 return pos;
466 }
467
468 iterator erase(const_iterator first, const_iterator last)
469 {
470 iterator pos = const_cast<iterator>(first);
471 copy(last, cend(), pos);
472 size_ -= static_cast<size_type>(last - first);
473
474 return pos;
475 }
476
477 void swap(vector& other)
478 noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value ||
479 allocator_traits<Allocator>::is_always_equal::value)
480 {
481 std::swap(data_, other.data_);
482 std::swap(size_, other.size_);
483 std::swap(capacity_, other.capacity_);
484 }
485
486 void clear() noexcept
487 {
488 // Note: Capacity remains unchanged.
489 destroy_from_end_until_(begin());
490 size_ = 0;
491 }
492
493 private:
494 value_type* data_;
495 size_type size_;
496 size_type capacity_;
497 allocator_type allocator_;
498
499 void resize_without_copy_(size_type capacity)
500 {
501 if (data_)
502 allocator_.deallocate(data_, capacity_);
503
504 data_ = allocator_.allocate(capacity);
505 size_ = 0;
506 capacity_ = capacity;
507 }
508
509 void resize_with_copy_(size_type size, size_type capacity)
510 {
511 if (size < size_)
512 destroy_from_end_until_(begin() + size);
513
514 if(capacity_ == 0 || capacity_ < capacity)
515 {
516 auto new_data = allocator_.allocate(capacity);
517
518 auto to_copy = min(size, size_);
519 for (size_type i = 0; i < to_copy; ++i)
520 new_data[i] = move(data_[i]);
521
522 std::swap(data_, new_data);
523
524 allocator_.deallocate(new_data, capacity_);
525 }
526
527 capacity_ = capacity;
528 size_ = size;
529 }
530
531 void destroy_from_end_until_(iterator target)
532 {
533 if (!empty())
534 {
535 auto last = end();
536 while(last != target)
537 allocator_traits<Allocator>::destroy(allocator_, --last);
538 }
539 }
540
541 size_type next_capacity_(size_type hint = 0) const noexcept
542 {
543 if (hint != 0)
544 return max(capacity_ * 2, hint);
545 else
546 return max(capacity_ * 2, 2ul);
547 }
548
549 iterator shift_(iterator position, size_type count)
550 {
551 if (size_ + count < capacity_)
552 {
553 copy_backward(position, end(), end() + count);
554 size_ += count;
555
556 return position;
557 }
558 else
559 {
560 auto start_idx = static_cast<size_type>(position - begin());
561 auto end_idx = start_idx + count;
562 auto new_size = size_ + count;
563
564 // Auxiliary vector for easier swap.
565 vector tmp{};
566 tmp.resize_without_copy_(max(new_size, capacity_));
567 tmp.size_ = new_size;
568
569 // Copy before insertion index.
570 copy(begin(), begin() + start_idx, tmp.begin());
571
572 // Copy after insertion index.
573 copy(begin() + start_idx, end(), tmp.begin() + end_idx);
574
575 swap(tmp);
576
577 // Position was invalidated!
578 return begin() + start_idx;
579 }
580 }
581 };
582
583 template<class T, class Alloc>
584 bool operator==(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
585 {
586 // TODO: implement
587 return false;
588 }
589
590 template<class T, class Alloc>
591 bool operator<(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
592 {
593 // TODO: implement
594 return false;
595 }
596
597 template<class T, class Alloc>
598 bool operator!=(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
599 {
600 return !(lhs == rhs);
601 }
602
603 template<class T, class Alloc>
604 bool operator>(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
605 {
606 // TODO: implement
607 return false;
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 /**
625 * 23.3.6.6, specialized algorithms:
626 */
627 template<class T, class Alloc>
628 void swap(vector<T, Alloc>& lhs, vector<T, Alloc>& rhs)
629 noexcept(noexcept(lhs.swap(rhs)))
630 {
631 lhs.swap(rhs);
632 }
633}
634
635#endif
Note: See TracBrowser for help on using the repository browser.