75 using size_type = std::size_t;
78 using element_category_type = mdds::mtv::element_t;
79 using block_funcs =
typename Traits::block_funcs;
101 struct block_slot_type
103 size_type position = 0;
109 block_slot_type(size_type _position, size_type _size) : position(_position), size(_size)
115 std::vector<size_type> positions;
116 std::vector<size_type> sizes;
117 std::vector<element_block_type*> element_blocks;
120 blocks_type(
const blocks_type& other);
121 blocks_type(blocks_type&& other);
125 positions.pop_back();
127 element_blocks.pop_back();
130 void push_back(size_type pos, size_type
size, element_block_type* data)
132 positions.push_back(pos);
133 sizes.push_back(
size);
134 element_blocks.push_back(data);
137 void push_back(
const block_slot_type& slot)
139 positions.push_back(slot.position);
140 sizes.push_back(slot.size);
141 element_blocks.push_back(slot.element_block);
144 void erase(size_type index);
145 void erase(size_type index, size_type
size);
146 void insert(size_type index, size_type
size);
147 void insert(size_type index, size_type pos, size_type
size, element_block_type* data);
148 void insert(size_type index,
const blocks_type& new_blocks);
156 void calc_block_position(size_type index);
158 size_type calc_next_block_position(size_type index);
160 void swap(size_type index1, size_type index2);
162 void swap(blocks_type& other);
164 void reserve(size_type n);
166 bool equals(
const blocks_type& other)
const;
170 void check_integrity()
const;
173 struct blocks_to_transfer
176 size_type insert_index = 0;
179 struct iterator_trait
182 using positions_type = std::vector<size_type>;
183 using sizes_type = std::vector<size_type>;
184 using element_blocks_type = std::vector<element_block_type*>;
186 using positions_iterator_type =
typename positions_type::iterator;
187 using sizes_iterator_type =
typename sizes_type::iterator;
188 using element_blocks_iterator_type =
typename element_blocks_type::iterator;
193 struct const_iterator_trait
196 using positions_type = std::vector<size_type>;
197 using sizes_type = std::vector<size_type>;
198 using element_blocks_type = std::vector<element_block_type*>;
200 using positions_iterator_type =
typename positions_type::const_iterator;
201 using sizes_iterator_type =
typename sizes_type::const_iterator;
202 using element_blocks_iterator_type =
typename element_blocks_type::const_iterator;
207 struct reverse_iterator_trait
210 using positions_type = std::vector<size_type>;
211 using sizes_type = std::vector<size_type>;
212 using element_blocks_type = std::vector<element_block_type*>;
214 using positions_iterator_type =
typename positions_type::reverse_iterator;
215 using sizes_iterator_type =
typename sizes_type::reverse_iterator;
216 using element_blocks_iterator_type =
typename element_blocks_type::reverse_iterator;
221 struct const_reverse_iterator_trait
224 using positions_type = std::vector<size_type>;
225 using sizes_type = std::vector<size_type>;
226 using element_blocks_type = std::vector<element_block_type*>;
228 using positions_iterator_type =
typename positions_type::const_reverse_iterator;
229 using sizes_iterator_type =
typename sizes_type::const_reverse_iterator;
230 using element_blocks_iterator_type =
typename element_blocks_type::const_reverse_iterator;
235 struct element_block_deleter
237 void operator()(
const element_block_type* p)
239 block_funcs::delete_block(p);
244 using iterator = detail::iterator_base<iterator_trait>;
245 using const_iterator = detail::const_iterator_base<const_iterator_trait, iterator>;
247 using reverse_iterator = detail::iterator_base<reverse_iterator_trait>;
248 using const_reverse_iterator = detail::const_iterator_base<const_reverse_iterator_trait, reverse_iterator>;
250 using position_type = std::pair<iterator, size_type>;
251 using const_position_type = std::pair<const_iterator, size_type>;
330 template<
typename _Blk>
331 static typename _Blk::value_type
get(
const const_position_type& pos);
704 template<
typename T,
typename... Args>
854 void erase(size_type start_pos, size_type end_pos);
962 void get(size_type pos, T& value)
const;
976 T
get(size_type pos)
const;
1011 template<
typename T>
1033 template<
typename T>
1151 template<
typename T>
1154#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1155 void dump_blocks(std::ostream& os)
const;
1157 void check_block_integrity()
const;
1161 void delete_element_block(size_type block_index);
1163 void delete_element_blocks(size_type start, size_type end);
1165 template<
typename T>
1166 void get_impl(size_type pos, T& value)
const;
1168 template<
typename T>
1169 bool set_cells_precheck(size_type row,
const T& it_begin,
const T& it_end, size_type& end_pos);
1171 template<
typename T>
1172 iterator set_impl(size_type pos, size_type block_index,
const T& value);
1174 template<
typename T>
1175 iterator release_impl(size_type pos, size_type block_index, T& value);
1178 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1179 size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1181 void swap_single_block(
1182 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1183 size_type other_block_index);
1185 void swap_single_to_multi_blocks(
1186 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1187 size_type dst_block_index1, size_type dst_block_index2);
1189 void swap_multi_to_multi_blocks(
1190 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1191 size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1193 template<
typename T>
1194 iterator insert_cells_impl(size_type row, size_type block_index,
const T& it_begin,
const T& it_end);
1196 void resize_impl(size_type new_size);
1203 size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2,
multi_type_vector& dest,
1204 size_type dest_pos);
1214 iterator set_empty_impl(size_type start_pos, size_type end_pos, size_type block_index1,
bool overwrite);
1216 iterator set_empty_in_single_block(size_type start_row, size_type end_row, size_type block_index,
bool overwrite);
1227 iterator set_empty_in_multi_blocks(
1228 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
bool overwrite);
1230 void erase_impl(size_type start_pos, size_type end_pos);
1231 void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_index);
1238 iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1240 void insert_blocks_at(size_type
position, size_type insert_pos, blocks_type& new_blocks);
1242 void prepare_blocks_to_transfer(
1243 blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2,
1246 iterator set_whole_block_empty(size_type block_index,
bool overwrite);
1248 template<
typename T>
1249 iterator push_back_impl(T&& value);
1251 template<
typename T,
typename... Args>
1252 iterator emplace_back_impl(Args&&... args);
1254 template<
typename T>
1256 size_type row, size_type end_row, size_type block_index1,
const T& it_begin,
const T& it_end);
1258 template<
typename T>
1259 iterator set_cells_to_single_block(
1260 size_type start_row, size_type end_row, size_type block_index,
const T& it_begin,
const T& it_end);
1262 template<
typename T>
1263 iterator set_cells_to_multi_blocks(
1264 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
const T& it_begin,
1267 template<
typename T>
1268 iterator set_cells_to_multi_blocks_block1_non_equal(
1269 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
const T& it_begin,
1272 template<
typename T>
1273 iterator set_cells_to_multi_blocks_block1_non_empty(
1274 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
const T& it_begin,
1277 template<
typename T>
1278 iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block,
const T& cell);
1280 template<
typename T>
1281 iterator set_cell_to_non_empty_block_of_size_one(size_type block_index,
const T& cell);
1292 size_type get_block_position(size_type row, size_type start_block_index = 0)
const;
1300 template<
typename T>
1301 void create_new_block_with_new_cell(size_type block_index, T&& cell);
1303 template<
typename T,
typename... Args>
1304 void create_new_block_with_emplace_back(size_type block_index,
const T& t, Args&&... args);
1306 template<
typename T>
1307 void append_cell_to_block(size_type block_index,
const T& cell);
1316 template<
typename T>
1317 bool append_to_prev_block(
1318 size_type block_index, element_category_type cat, size_type length,
const T& it_begin,
const T& it_end);
1320 template<
typename T>
1321 void insert_cells_to_middle(size_type row, size_type block_index,
const T& it_begin,
const T& it_end);
1323 template<
typename T>
1324 iterator set_cell_to_middle_of_block(size_type block_index, size_type pos_in_block,
const T& cell);
1331 template<
typename T>
1332 void set_cell_to_top_of_data_block(size_type block_index,
const T& cell);
1334 template<
typename T>
1335 void set_cell_to_bottom_of_data_block(size_type block_index,
const T& cell);
1338 size_type start_pos, size_type end_pos, size_type block_index1,
multi_type_vector& dest, size_type dest_pos);
1344 size_type start_pos, size_type end_pos, size_type block_index1,
multi_type_vector& dest, size_type dest_pos);
1354 size_type merge_with_adjacent_blocks(size_type block_index);
1363 bool merge_with_next_block(size_type block_index);
1378 size_type set_new_block_to_middle(
1379 size_type block_index, size_type offset, size_type new_block_size,
bool overwrite);
1390 bool is_previous_block_of_type(size_type block_index, element_category_type cat)
const;
1401 bool is_next_block_of_type(size_type block_index, element_category_type cat)
const;
1425 const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset,
1428 void exchange_elements(
1429 const element_block_type& src_blk, size_type src_offset, size_type dst_index1, size_type dst_offset1,
1430 size_type dst_index2, size_type dst_offset2, size_type len, blocks_type& new_blocks);
1432 bool append_empty(size_type len);
1434 inline iterator get_iterator(size_type block_index)
1436 auto iter_pos = m_block_store.positions.begin();
1437 std::advance(iter_pos, block_index);
1438 auto iter_size = m_block_store.sizes.begin();
1439 std::advance(iter_size, block_index);
1440 auto iter_elem = m_block_store.element_blocks.begin();
1441 std::advance(iter_elem, block_index);
1444 {iter_pos, iter_size, iter_elem},
1445 {m_block_store.positions.end(), m_block_store.sizes.end(), m_block_store.element_blocks.end()},
this,
1449 inline const_iterator get_const_iterator(size_type block_index)
const
1451 auto iter_pos = m_block_store.positions.cbegin();
1452 std::advance(iter_pos, block_index);
1453 auto iter_size = m_block_store.sizes.cbegin();
1454 std::advance(iter_size, block_index);
1455 auto iter_elem = m_block_store.element_blocks.cbegin();
1456 std::advance(iter_elem, block_index);
1458 return const_iterator(
1459 {iter_pos, iter_size, iter_elem},
1460 {m_block_store.positions.cend(), m_block_store.sizes.cend(), m_block_store.element_blocks.cend()},
this,
1465 using adjust_block_positions_func = detail::adjust_block_positions<blocks_type, Traits::loop_unrolling>;
1468 blocks_type m_block_store;
1469 size_type m_cur_size;
1471#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1472 mutable int m_trace_call_depth = 0;