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

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

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