49class multi_type_vector
52 using size_type = std::size_t;
53 using block_funcs =
typename Traits::block_funcs;
75 struct block_slot_type
81 block_slot_type()
noexcept(std::is_fundamental_v<size_type>)
83 block_slot_type(size_type _position, size_type _size)
noexcept(std::is_fundamental_v<size_type>)
90 std::vector<size_type> positions;
91 std::vector<size_type> sizes;
92 std::vector<base_element_block*> element_blocks;
94 static constexpr bool nothrow_default_constructible_v =
95 std::is_nothrow_default_constructible_v<std::vector<size_type>> &&
96 std::is_nothrow_default_constructible_v<std::vector<base_element_block*>>;
98 static constexpr bool nothrow_move_constructible_v =
99 std::is_nothrow_move_constructible_v<std::vector<size_type>> &&
100 std::is_nothrow_move_constructible_v<std::vector<base_element_block*>>;
102 static constexpr bool nothrow_value_swappable_v =
103 noexcept(std::swap(std::declval<size_type&>(), std::declval<size_type&>())) &&
104 noexcept(std::swap(std::declval<base_element_block*&>(), std::declval<base_element_block*&>()));
106 static constexpr bool nothrow_swappable_v = std::is_nothrow_swappable_v<std::vector<size_type>> &&
107 std::is_nothrow_swappable_v<std::vector<base_element_block*>>;
109 blocks_type() noexcept(nothrow_default_constructible_v);
112 blocks_type(mtv::detail::clone_construction_type, const blocks_type& other, CVs&... cloners);
114 blocks_type(const blocks_type& other);
115 blocks_type(blocks_type&& other) noexcept(nothrow_move_constructible_v);
119 positions.pop_back();
121 element_blocks.pop_back();
126 positions.push_back(pos);
127 sizes.push_back(
size);
128 element_blocks.push_back(data);
131 void push_back(
const block_slot_type& slot)
133 positions.push_back(slot.position);
134 sizes.push_back(slot.size);
135 element_blocks.push_back(slot.element_block);
138 void erase(size_type index);
139 void erase(size_type index, size_type
size);
140 void insert(size_type index, size_type
size);
141 void insert(size_type index, size_type pos, size_type
size, base_element_block* data);
142 void insert(size_type index,
const blocks_type& new_blocks);
150 void calc_block_position(size_type index);
152 size_type calc_next_block_position(size_type index);
154 void swap(size_type index1, size_type index2)
noexcept(nothrow_value_swappable_v);
156 void swap(blocks_type& other)
noexcept(nothrow_swappable_v);
158 void reserve(size_type n);
160 bool equals(
const blocks_type& other)
const;
164 void check_integrity()
const;
167 struct blocks_to_transfer
170 size_type insert_index = 0;
173 struct iterator_trait
175 using parent = multi_type_vector;
176 using positions_type = std::vector<size_type>;
177 using sizes_type = std::vector<size_type>;
178 using element_blocks_type = std::vector<base_element_block*>;
180 using positions_iterator_type =
typename positions_type::iterator;
181 using sizes_iterator_type =
typename sizes_type::iterator;
182 using element_blocks_iterator_type =
typename element_blocks_type::iterator;
184 using private_data_update = mdds::detail::mtv::private_data_forward_update<multi_type_vector, size_type>;
187 struct const_iterator_trait
189 using parent = multi_type_vector;
190 using positions_type = std::vector<size_type>;
191 using sizes_type = std::vector<size_type>;
192 using element_blocks_type = std::vector<base_element_block*>;
194 using positions_iterator_type =
typename positions_type::const_iterator;
195 using sizes_iterator_type =
typename sizes_type::const_iterator;
196 using element_blocks_iterator_type =
typename element_blocks_type::const_iterator;
198 using private_data_update = mdds::detail::mtv::private_data_forward_update<multi_type_vector, size_type>;
201 struct reverse_iterator_trait
203 using parent = multi_type_vector;
204 using positions_type = std::vector<size_type>;
205 using sizes_type = std::vector<size_type>;
206 using element_blocks_type = std::vector<base_element_block*>;
208 using positions_iterator_type =
typename positions_type::reverse_iterator;
209 using sizes_iterator_type =
typename sizes_type::reverse_iterator;
210 using element_blocks_iterator_type =
typename element_blocks_type::reverse_iterator;
212 using private_data_update = mdds::detail::mtv::private_data_no_update<multi_type_vector, size_type>;
215 struct const_reverse_iterator_trait
217 using parent = multi_type_vector;
218 using positions_type = std::vector<size_type>;
219 using sizes_type = std::vector<size_type>;
220 using element_blocks_type = std::vector<base_element_block*>;
222 using positions_iterator_type =
typename positions_type::const_reverse_iterator;
223 using sizes_iterator_type =
typename sizes_type::const_reverse_iterator;
224 using element_blocks_iterator_type =
typename element_blocks_type::const_reverse_iterator;
226 using private_data_update = mdds::detail::mtv::private_data_no_update<multi_type_vector, size_type>;
229 struct element_block_deleter
231 void operator()(
const base_element_block* p)
233 block_funcs::delete_block(p);
237 static constexpr bool nothrow_default_constructible_v = std::is_nothrow_default_constructible_v<event_func> &&
238 std::is_nothrow_default_constructible_v<blocks_type> &&
239 std::is_nothrow_default_constructible_v<size_type>;
241 static constexpr bool nothrow_move_constructible_v = std::is_nothrow_move_constructible_v<event_func> &&
242 std::is_nothrow_move_constructible_v<blocks_type> &&
243 std::is_nothrow_move_constructible_v<size_type>;
245 static constexpr bool nothrow_swappable_v = std::is_nothrow_swappable_v<event_func> &&
246 std::is_nothrow_swappable_v<size_type> &&
247 std::is_nothrow_swappable_v<blocks_type>;
249 static constexpr bool nothrow_move_assignable_v = nothrow_move_constructible_v && nothrow_swappable_v;
251 template<stateful_clone_value... CVs>
252 multi_type_vector(mtv::detail::clone_construction_type,
const multi_type_vector& other, CVs&... cloners);
254 template<stateful_clone_value... CVs>
256 mtv::detail::clone_construction_type,
const multi_type_vector& other,
event_func hdl, CVs&... cloners);
259 using iterator = detail::iterator_base<iterator_trait>;
260 using const_iterator = detail::const_iterator_base<const_iterator_trait, iterator>;
262 using reverse_iterator = detail::iterator_base<reverse_iterator_trait>;
263 using const_reverse_iterator = detail::const_iterator_base<const_reverse_iterator_trait, reverse_iterator>;
265 using position_type = std::pair<iterator, size_type>;
266 using const_position_type = std::pair<const_iterator, size_type>;
335 static size_type
logical_position(
const const_position_type& pos)
noexcept(std::is_fundamental_v<size_type>);
345 template<
typename _Blk>
346 static typename _Blk::value_type
get(
const const_position_type& pos);
365 multi_type_vector() noexcept(nothrow_default_constructible_v);
390 multi_type_vector(size_type init_size);
402 multi_type_vector(size_type init_size, const T& value);
418 multi_type_vector(size_type init_size, const T& it_begin, const T& it_end);
425 multi_type_vector(const multi_type_vector& other);
432 multi_type_vector(multi_type_vector&& other) noexcept(nothrow_move_constructible_v);
437 ~multi_type_vector();
510 multi_type_vector
clone(CVs&... cloners) const;
658 iterator
transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
693 position_hint pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
712 iterator
set(size_type pos, const T& value);
775 iterator
set(size_type pos, const T& it_begin, const T& it_end);
866 template<typename T, typename... Args>
891 iterator
insert(size_type pos, const T& it_begin, const T& it_end);
972 iterator
set_empty(size_type start_pos, size_type end_pos);
1022 void erase(size_type start_pos, size_type end_pos);
1133 template<typename T>
1134 void get(size_type pos, T& value) const;
1147 template<typename T>
1170 template<typename T>
1195 template<typename T>
1227 template<typename T>
1357 const_iterator
begin() const;
1358 const_iterator
end() const;
1360 const_iterator cbegin() const;
1361 const_iterator cend() const;
1394 const_reverse_iterator
rbegin() const;
1395 const_reverse_iterator
rend() const;
1397 const_reverse_iterator crbegin() const;
1398 const_reverse_iterator crend() const;
1414 void swap(multi_type_vector& other) noexcept(nothrow_swappable_v);
1424 void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
1499 bool operator==(const multi_type_vector& other) const;
1501 multi_type_vector& operator=(const multi_type_vector& other);
1502 multi_type_vector& operator=(multi_type_vector&& other) noexcept(nothrow_move_assignable_v);
1511 template<typename T>
1514#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1515 void dump_blocks(std::ostream& os)
const;
1517 void check_block_integrity()
const;
1521 iterator make_begin();
1522 iterator make_end();
1523 reverse_iterator make_rbegin();
1524 reverse_iterator make_rend();
1526 void delete_element_block(size_type block_index);
1528 void delete_element_blocks(size_type start, size_type
end);
1530 template<
typename T>
1531 void get_impl(size_type pos, T& value)
const;
1533 template<
typename T>
1534 bool set_cells_precheck(size_type row,
const T& it_begin,
const T& it_end, size_type& end_pos);
1536 template<
typename T>
1537 iterator set_impl(size_type pos, size_type block_index,
const T& value);
1539 template<
typename T>
1540 iterator release_impl(size_type pos, size_type block_index, T& value);
1543 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1544 size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1546 void swap_single_block(
1547 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1548 size_type other_block_index);
1550 void swap_single_to_multi_blocks(
1551 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1552 size_type dst_block_index1, size_type dst_block_index2);
1554 void swap_multi_to_multi_blocks(
1555 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1556 size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1558 template<
typename T>
1559 iterator insert_cells_impl(size_type row, size_type block_index,
const T& it_begin,
const T& it_end);
1561 void resize_impl(size_type new_size);
1567 iterator transfer_multi_blocks(
1568 size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2, multi_type_vector& dest,
1569 size_type dest_pos);
1579 iterator set_empty_impl(size_type start_pos, size_type end_pos, size_type block_index1,
bool overwrite);
1581 iterator set_empty_in_single_block(size_type start_row, size_type end_row, size_type block_index,
bool overwrite);
1592 iterator set_empty_in_multi_blocks(
1593 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
bool overwrite);
1595 void erase_impl(size_type start_pos, size_type end_pos);
1596 void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_index);
1603 iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1605 void insert_blocks_at(size_type
position, size_type insert_pos, blocks_type& new_blocks);
1607 void prepare_blocks_to_transfer(
1608 blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2,
1611 iterator set_whole_block_empty(size_type block_index,
bool overwrite);
1613 template<
typename T>
1614 iterator push_back_impl(T&& value);
1616 template<
typename T,
typename... Args>
1617 iterator emplace_back_impl(Args&&... args);
1619 template<
typename T>
1620 iterator set_cells_impl(
1621 size_type row, size_type end_row, size_type block_index1,
const T& it_begin,
const T& it_end);
1623 template<
typename T>
1624 iterator set_cells_to_single_block(
1625 size_type start_row, size_type end_row, size_type block_index,
const T& it_begin,
const T& it_end);
1627 template<
typename T>
1628 iterator set_cells_to_multi_blocks(
1629 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
const T& it_begin,
1632 template<
typename T>
1633 iterator set_cells_to_multi_blocks_block1_non_equal(
1634 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
const T& it_begin,
1637 template<
typename T>
1638 iterator set_cells_to_multi_blocks_block1_non_empty(
1639 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
const T& it_begin,
1642 template<
typename T>
1643 iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block,
const T& cell);
1645 template<
typename T>
1646 iterator set_cell_to_non_empty_block_of_size_one(size_type block_index,
const T& cell);
1657 size_type get_block_position(size_type row, size_type start_block_index = 0)
const;
1664 size_type get_block_position(
const position_hint& pos_hint, size_type row)
const;
1666 template<
typename T>
1667 void create_new_block_with_new_cell(size_type block_index, T&& cell);
1669 template<
typename T,
typename... Args>
1670 void create_new_block_with_emplace_back(size_type block_index,
const T& t, Args&&... args);
1672 template<
typename T>
1673 void append_cell_to_block(size_type block_index,
const T& cell);
1682 template<
typename T>
1683 bool append_to_prev_block(
1684 size_type block_index, element_t cat, size_type length,
const T& it_begin,
const T& it_end);
1686 template<
typename T>
1687 void insert_cells_to_middle(size_type row, size_type block_index,
const T& it_begin,
const T& it_end);
1689 template<
typename T>
1690 iterator set_cell_to_middle_of_block(size_type block_index, size_type pos_in_block,
const T& cell);
1697 template<
typename T>
1698 void set_cell_to_top_of_data_block(size_type block_index,
const T& cell);
1700 template<
typename T>
1701 void set_cell_to_bottom_of_data_block(size_type block_index,
const T& cell);
1703 iterator transfer_impl(
1704 size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);
1709 iterator transfer_single_block(
1710 size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);
1720 size_type merge_with_adjacent_blocks(size_type block_index);
1729 bool merge_with_next_block(size_type block_index);
1744 size_type set_new_block_to_middle(
1745 size_type block_index, size_type offset, size_type new_block_size,
bool overwrite);
1756 bool is_previous_block_of_type(size_type block_index, element_t cat)
const;
1767 bool is_next_block_of_type(size_type block_index, element_t cat)
const;
1791 const base_element_block& src_data, size_type src_offset, size_type dst_index, size_type dst_offset,
1794 void exchange_elements(
1795 const base_element_block& src_blk, size_type src_offset, size_type dst_index1, size_type dst_offset1,
1796 size_type dst_index2, size_type dst_offset2, size_type len, blocks_type& new_blocks);
1798 bool append_empty(size_type len);
1800 inline iterator get_iterator(size_type block_index)
1802 auto iter_pos = m_block_store.positions.begin();
1803 std::advance(iter_pos, block_index);
1804 auto iter_size = m_block_store.sizes.begin();
1805 std::advance(iter_size, block_index);
1806 auto iter_elem = m_block_store.element_blocks.begin();
1807 std::advance(iter_elem, block_index);
1810 {iter_pos, iter_size, iter_elem},
1811 {m_block_store.positions.end(), m_block_store.sizes.end(), m_block_store.element_blocks.end()},
this,
1815 inline const_iterator get_const_iterator(size_type block_index)
const
1817 auto iter_pos = m_block_store.positions.cbegin();
1818 std::advance(iter_pos, block_index);
1819 auto iter_size = m_block_store.sizes.cbegin();
1820 std::advance(iter_size, block_index);
1821 auto iter_elem = m_block_store.element_blocks.cbegin();
1822 std::advance(iter_elem, block_index);
1824 return const_iterator(
1825 {iter_pos, iter_size, iter_elem},
1826 {m_block_store.positions.cend(), m_block_store.sizes.cend(), m_block_store.element_blocks.cend()},
this,
1830#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1831 void debug_check_full(std::string_view location);
1841 struct shared_element_blocks
1843 std::vector<base_element_block*> blocks;
1845 ~shared_element_blocks()
1847 for (base_element_block* p : blocks)
1848 block_funcs::delete_block(p);
1861 template<stateful_clone_value... CVs>
1862 void detach_impl(CVs&... cloners);
1864 using adjust_block_positions_func = detail::adjust_block_positions<blocks_type, Traits::loop_unrolling>;
1867 blocks_type m_block_store;
1868 size_type m_cur_size;
1870 container_id_t m_id = mtv::detail::next_container_id();
1878 [[no_unique_address]]
mutable std::conditional_t<
1879 Traits::enable_cow, std::shared_ptr<shared_element_blocks>, mtv::detail::empty_cow_store> m_cow_store;
1881#ifdef MDDS_MULTI_TYPE_VECTOR_TRACE
1882 mutable int m_trace_call_depth = 0;