1 /* 2 * Copyright 2014 Google Inc. All rights reserved. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef FRUIT_FIXED_SIZE_VECTOR_H 18 #define FRUIT_FIXED_SIZE_VECTOR_H 19 20 #include <cstdlib> 21 #include <memory> 22 23 namespace fruit { 24 namespace impl { 25 26 /** 27 * Similar to std::vector<T>, but the capacity is fixed at construction time, and no reallocations ever happen. 28 * The type T must be trivially copyable. 29 */ 30 template <typename T, typename Allocator = std::allocator<T>> 31 class FixedSizeVector { 32 private: 33 // This is not yet implemented in libstdc++ (the STL implementation) shipped with GCC (checked until version 4.9.1). 34 // static_assert(std::is_trivially_copyable<T>::value, "T must be trivially copyable."); 35 36 // v_end is before v_begin here, because it's the most commonly accessed field. 37 T* v_end; 38 T* v_begin; 39 40 std::size_t capacity; 41 Allocator allocator; 42 43 public: 44 using iterator = T*; 45 using const_iterator = const T*; 46 47 FixedSizeVector(std::size_t capacity = 0, Allocator allocator = Allocator()); 48 // Creates a vector with the specified size (and equal capacity) initialized with the specified value. 49 FixedSizeVector(std::size_t size, const T& value, Allocator allocator = Allocator()); 50 ~FixedSizeVector(); 51 52 // Copy construction is not allowed, you need to specify the capacity in order to construct the copy. 53 FixedSizeVector(const FixedSizeVector& other) = delete; 54 FixedSizeVector(const FixedSizeVector& other, std::size_t capacity); 55 56 FixedSizeVector(FixedSizeVector&& other); 57 58 FixedSizeVector& operator=(const FixedSizeVector& other) = delete; 59 FixedSizeVector& operator=(FixedSizeVector&& other); 60 61 std::size_t size() const; 62 63 T& operator[](std::size_t i); 64 const T& operator[](std::size_t i) const; 65 66 // This yields undefined behavior (instead of reallocating) if the vector's capacity is exceeded. 67 void push_back(T x); 68 69 void swap(FixedSizeVector& x); 70 71 // Removes all elements, so size() becomes 0 (but maintains the capacity). 72 void clear(); 73 74 T* data(); 75 iterator begin(); 76 iterator end(); 77 78 const T* data() const; 79 const_iterator begin() const; 80 const_iterator end() const; 81 }; 82 83 } // namespace impl 84 } // namespace fruit 85 86 #include <fruit/impl/data_structures/fixed_size_vector.defn.h> 87 88 #endif // FRUIT_FIXED_SIZE_VECTOR_H 89