38 #ifndef LIBPMEMOBJ_CPP_VECTOR_HPP
39 #define LIBPMEMOBJ_CPP_VECTOR_HPP
51 #include <libpmemobj/base.h>
73 using size_type = std::size_t;
74 using difference_type = std::ptrdiff_t;
75 using reference = value_type &;
76 using const_reference =
const value_type &;
77 using pointer = value_type *;
78 using const_pointer =
const value_type *;
80 using const_iterator = const_pointer;
81 using reverse_iterator = std::reverse_iterator<iterator>;
82 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
86 using for_each_ptr_function =
91 vector(size_type count,
const value_type &value);
92 explicit vector(size_type count);
93 template <
typename InputIt,
94 typename std::enable_if<
96 InputIt>::type * =
nullptr>
97 vector(InputIt first, InputIt last);
100 vector(std::initializer_list<T> init);
101 vector(
const std::vector<T> &other);
110 void assign(size_type count,
const T &value);
111 template <
typename InputIt,
112 typename std::enable_if<
114 InputIt>::type * =
nullptr>
115 void assign(InputIt first, InputIt last);
116 void assign(std::initializer_list<T> ilist);
117 void assign(
const vector &other);
118 void assign(
vector &&other);
119 void assign(
const std::vector<T> &other);
125 reference
at(size_type n);
126 const_reference
at(size_type n)
const;
127 const_reference
const_at(size_type n)
const;
129 const_reference
operator[](size_type n)
const;
131 const_reference
front()
const;
132 const_reference
cfront()
const;
134 const_reference
back()
const;
135 const_reference
cback()
const;
137 const value_type *
data()
const noexcept;
138 const value_type *
cdata()
const noexcept;
142 const_iterator
begin()
const noexcept;
143 const_iterator
cbegin()
const noexcept;
145 const_iterator
end()
const noexcept;
146 const_iterator
cend()
const noexcept;
147 reverse_iterator
rbegin();
148 const_reverse_iterator
rbegin()
const noexcept;
149 const_reverse_iterator
crbegin()
const noexcept;
150 reverse_iterator
rend();
151 const_reverse_iterator
rend()
const noexcept;
152 const_reverse_iterator
crend()
const noexcept;
157 size_type snapshot_size);
163 constexpr
bool empty()
const noexcept;
164 size_type
size()
const noexcept;
165 constexpr size_type
max_size()
const noexcept;
166 void reserve(size_type capacity_new);
167 size_type
capacity()
const noexcept;
175 iterator insert(const_iterator pos, size_type count,
const T &value);
176 template <
typename InputIt,
177 typename std::enable_if<
179 InputIt>::type * =
nullptr>
181 iterator insert(const_iterator pos, std::initializer_list<T> ilist);
182 template <
class... Args>
184 template <
class... Args>
191 void resize(size_type count);
192 void resize(size_type count,
const value_type &value);
197 template <
typename P>
198 struct single_element_iterator {
199 using iterator_category = std::input_iterator_tag;
200 using value_type = P;
201 using difference_type = std::ptrdiff_t;
202 using pointer =
const P *;
203 using reference =
const P &;
208 single_element_iterator(
const P *ptr, std::size_t count = 0)
209 : ptr(ptr), count(count)
213 reference operator*()
223 single_element_iterator &
230 single_element_iterator
233 single_element_iterator tmp =
234 single_element_iterator(ptr, count);
240 operator-(
const single_element_iterator &rhs)
242 return count - rhs.count;
246 operator!=(
const single_element_iterator &rhs)
248 return ptr != rhs.ptr || count != rhs.count;
256 template <
typename... Args>
258 template <
typename InputIt,
259 typename std::enable_if<
261 InputIt>::type * =
nullptr>
265 template <
typename InputIt>
269 void shrink(size_type size_new);
271 template <
typename InputIt>
284 template <
typename T>
291 template <
typename T>
293 template <
typename T>
295 template <
typename T>
297 template <
typename T>
299 template <
typename T>
301 template <
typename T>
308 template <
typename T>
310 template <
typename T>
312 template <
typename T>
314 template <
typename T>
316 template <
typename T>
318 template <
typename T>
325 template <
typename T>
327 template <
typename T>
329 template <
typename T>
331 template <
typename T>
333 template <
typename T>
335 template <
typename T>
347 template <
typename T>
351 check_tx_stage_work();
376 template <
typename T>
380 check_tx_stage_work();
385 construct_at_end(count, value);
405 template <
typename T>
409 check_tx_stage_work();
414 construct_at_end(count);
439 template <
typename T>
440 template <
typename InputIt,
441 typename std::enable_if<detail::is_input_iterator<InputIt>::value,
446 check_tx_stage_work();
450 alloc(static_cast<size_type>(std::distance(first, last)));
451 construct_at_end(first, last);
472 template <
typename T>
476 check_tx_stage_work();
481 construct_at_end(other.
cbegin(), other.
cend());
503 template <
typename T>
507 check_tx_stage_work();
510 _capacity = other.capacity();
511 _size = other.size();
512 other._data =
nullptr;
513 other._capacity = other._size = 0;
533 template <
typename T>
557 template <
typename T>
574 template <
typename T>
593 template <
typename T>
597 assign(std::move(other));
611 template <
typename T>
615 assign(ilist.begin(), ilist.end());
632 template <
typename T>
657 template <
typename T>
663 transaction::run(pb, [&] {
664 if (count <= capacity()) {
671 size_type size_old = _size;
672 add_data_to_tx(0, size_old);
677 static_cast<size_type>(size_old)),
680 if (count > size_old) {
681 add_data_to_tx(size_old, count - size_old);
682 construct_at_end(count - size_old, value);
689 construct_at_end(count, value);
712 template <
typename T>
713 template <
typename InputIt,
714 typename std::enable_if<detail::is_input_iterator<InputIt>::value,
721 size_type size_new = static_cast<size_type>(std::distance(first, last));
723 transaction::run(pb, [&] {
724 if (size_new <= capacity()) {
731 size_type size_old = _size;
732 add_data_to_tx(0, size_old);
735 bool growing = size_new > size_old;
738 add_data_to_tx(size_old, size_new - size_old);
741 std::advance(mid, size_old);
744 iterator shrink_to = std::copy(first, mid, &_data[0]);
747 construct_at_end(mid, last);
749 shrink(static_cast<size_type>(std::distance(
755 construct_at_end(first, last);
775 template <
typename T>
779 assign(ilist.begin(), ilist.end());
793 template <
typename T>
812 template <
typename T>
821 transaction::run(pb, [&] {
825 _capacity = other._capacity;
828 other._data =
nullptr;
829 other._capacity = other._size = 0;
845 template <
typename T>
849 assign(other.cbegin(), other.cend());
861 template <
typename T>
879 template <
typename T>
880 typename vector<T>::reference
884 throw std::out_of_range(
"vector::at");
886 detail::conditional_add_to_tx(&_data[static_cast<difference_type>(n)],
887 1, POBJ_XADD_ASSUME_INITIALIZED);
889 return _data[static_cast<difference_type>(n)];
901 template <
typename T>
902 typename vector<T>::const_reference
906 throw std::out_of_range(
"vector::at");
908 return _data[static_cast<difference_type>(n)];
923 template <
typename T>
924 typename vector<T>::const_reference
928 throw std::out_of_range(
"vector::const_at");
930 return _data[static_cast<difference_type>(n)];
944 template <
typename T>
947 detail::conditional_add_to_tx(&_data[static_cast<difference_type>(n)],
948 1, POBJ_XADD_ASSUME_INITIALIZED);
950 return _data[static_cast<difference_type>(n)];
960 template <
typename T>
963 return _data[static_cast<difference_type>(n)];
974 template <
typename T>
975 typename vector<T>::reference
978 detail::conditional_add_to_tx(&_data[0], 1,
979 POBJ_XADD_ASSUME_INITIALIZED);
989 template <
typename T>
990 typename vector<T>::const_reference
1003 template <
typename T>
1004 typename vector<T>::const_reference
1018 template <
typename T>
1019 typename vector<T>::reference
1022 detail::conditional_add_to_tx(
1023 &_data[static_cast<difference_type>(size() - 1)], 1,
1024 POBJ_XADD_ASSUME_INITIALIZED);
1026 return _data[static_cast<difference_type>(size() - 1)];
1034 template <
typename T>
1035 typename vector<T>::const_reference
1038 return _data[static_cast<difference_type>(size() - 1)];
1048 template <
typename T>
1049 typename vector<T>::const_reference
1052 return _data[static_cast<difference_type>(size() - 1)];
1064 template <
typename T>
1065 typename vector<T>::value_type *
1068 add_data_to_tx(0, _size);
1078 template <
typename T>
1079 const typename vector<T>::value_type *
1092 template <
typename T>
1093 const typename vector<T>::value_type *
1104 template <
typename T>
1116 template <
typename T>
1117 typename vector<T>::const_iterator
1120 return const_iterator(_data.get());
1130 template <
typename T>
1131 typename vector<T>::const_iterator
1134 return const_iterator(_data.get());
1142 template <
typename T>
1146 return iterator(_data.get() + static_cast<std::ptrdiff_t>(_size));
1154 template <
typename T>
1155 typename vector<T>::const_iterator
1158 return const_iterator(_data.get() + static_cast<std::ptrdiff_t>(_size));
1168 template <
typename T>
1169 typename vector<T>::const_iterator
1172 return const_iterator(_data.get() + static_cast<std::ptrdiff_t>(_size));
1180 template <
typename T>
1181 typename vector<T>::reverse_iterator
1184 return reverse_iterator(
end());
1192 template <
typename T>
1193 typename vector<T>::const_reverse_iterator
1196 return const_reverse_iterator(
cend());
1206 template <
typename T>
1207 typename vector<T>::const_reverse_iterator
1210 return const_reverse_iterator(
cend());
1219 template <
typename T>
1220 typename vector<T>::reverse_iterator
1223 return reverse_iterator(
begin());
1232 template <
typename T>
1233 typename vector<T>::const_reverse_iterator
1236 return const_reverse_iterator(
cbegin());
1247 template <
typename T>
1248 typename vector<T>::const_reverse_iterator
1251 return const_reverse_iterator(
cbegin());
1267 template <
typename T>
1271 if (start + n > size())
1272 throw std::out_of_range(
"vector::range");
1274 detail::conditional_add_to_tx(cdata() + start, n,
1275 POBJ_XADD_ASSUME_INITIALIZED);
1277 return {_data.get() + start, _data.get() + start + n};
1295 template <
typename T>
1299 if (start + n > size())
1300 throw std::out_of_range(
"vector::range");
1302 if (snapshot_size > n)
1306 _data.get() + start, n,
1309 _data.get() + start, n,
1324 template <
typename T>
1328 if (start + n > size())
1329 throw std::out_of_range(
"vector::range");
1331 return {const_iterator(cdata() + start),
1332 const_iterator(cdata() + start + n)};
1346 template <
typename T>
1350 if (start + n > size())
1351 throw std::out_of_range(
"vector::crange");
1353 return {const_iterator(cdata() + start),
1354 const_iterator(cdata() + start + n)};
1362 template <
typename T>
1372 template <
typename T>
1373 typename vector<T>::size_type
1383 template <
typename T>
1384 constexpr
typename vector<T>::size_type
1387 return PMEMOBJ_MAX_ALLOC_SIZE /
sizeof(value_type);
1408 template <
typename T>
1412 if (capacity_new <= _capacity)
1416 transaction::run(pb, [&] { realloc(capacity_new); });
1422 template <
typename T>
1423 typename vector<T>::size_type
1443 template <
typename T>
1447 size_type capacity_new = size();
1448 if (capacity() == capacity_new)
1452 transaction::run(pb, [&] { realloc(capacity_new); });
1463 template <
typename T>
1468 transaction::run(pb, [&] { shrink(0); });
1483 template <
typename T>
1487 if (_data ==
nullptr)
1491 transaction::run(pb, [&] { dealloc(); });
1518 template <
typename T>
1522 return insert(pos, 1, value);
1549 template <
typename T>
1555 size_type idx = static_cast<size_type>(std::distance(
cbegin(), pos));
1557 transaction::run(pb, [&] {
1558 internal_insert(idx, std::make_move_iterator(&value),
1559 std::make_move_iterator(&value + 1));
1562 return iterator(&_data[static_cast<difference_type>(idx)]);
1593 template <
typename T>
1599 size_type idx = static_cast<size_type>(std::distance(
cbegin(), pos));
1601 transaction::run(pb, [&] {
1603 idx, single_element_iterator<value_type>(&value, 0),
1604 single_element_iterator<value_type>(&value, count));
1607 return iterator(&_data[static_cast<difference_type>(idx)]);
1644 template <
typename T>
1645 template <
typename InputIt,
1646 typename std::enable_if<detail::is_input_iterator<InputIt>::value,
1653 size_type idx = static_cast<size_type>(std::distance(
cbegin(), pos));
1655 transaction::run(pb, [&] { internal_insert(idx, first, last); });
1657 return iterator(&_data[static_cast<difference_type>(idx)]);
1688 template <
typename T>
1692 return insert(pos, ilist.begin(), ilist.end());
1722 template <
typename T>
1723 template <
class... Args>
1729 size_type idx = static_cast<size_type>(std::distance(
cbegin(), pos));
1731 transaction::run(pb, [&] {
1738 noexcept(T(std::forward<Args>(args)...))>
1739 tmp(std::forward<Args>(args)...);
1741 auto &tmp_ref = tmp.get();
1743 internal_insert(idx, std::make_move_iterator(&tmp_ref),
1744 std::make_move_iterator(&tmp_ref + 1));
1747 return iterator(&_data[static_cast<difference_type>(idx)]);
1772 template <
typename T>
1773 template <
class... Args>
1774 typename vector<T>::reference
1784 transaction::run(pb, [&] {
1785 if (_size == _capacity) {
1786 realloc(get_recommended_capacity(_size + 1));
1788 add_data_to_tx(size(), 1);
1791 construct_at_end(1, std::forward<Args>(args)...);
1816 template <
typename T>
1820 return erase(pos, pos + 1);
1845 template <
typename T>
1849 size_type idx = static_cast<size_type>(
1850 std::distance(const_iterator(&_data[0]), first));
1851 size_type count = static_cast<size_type>(std::distance(first, last));
1854 return iterator(&_data[static_cast<difference_type>(idx)]);
1858 transaction::run(pb, [&] {
1863 add_data_to_tx(idx, _size - idx);
1865 pointer move_begin =
1866 &_data[static_cast<difference_type>(idx + count)];
1867 pointer move_end = &_data[static_cast<difference_type>(size())];
1868 pointer dest = &_data[static_cast<difference_type>(idx)];
1870 std::move(move_begin, move_end, dest);
1875 return iterator(&_data[static_cast<difference_type>(idx)]);
1893 template <
typename T>
1897 emplace_back(value);
1916 template <
typename T>
1920 emplace_back(std::move(value));
1933 template <
typename T>
1941 transaction::run(pb, [&] { shrink(size() - 1); });
1960 template <
typename T>
1965 transaction::run(pb, [&] {
1969 if (_capacity < count)
1971 construct_at_end(count - _size);
1993 template <
typename T>
1997 if (_capacity == count)
2001 transaction::run(pb, [&] {
2005 if (_capacity < count)
2007 construct_at_end(count - _size, value);
2015 template <
typename T>
2020 transaction::run(pb, [&] {
2023 std::swap(this->_capacity, other._capacity);
2033 template <
typename T>
2057 template <
typename T>
2061 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2062 assert(_data ==
nullptr);
2065 if (capacity_new > max_size())
2066 throw std::length_error(
"New capacity exceeds max size.");
2068 _capacity = capacity_new;
2070 if (capacity_new == 0)
2079 pmemobj_tx_alloc(
sizeof(value_type) * capacity_new,
2080 detail::type_num<value_type>());
2082 if (res ==
nullptr) {
2083 if (errno == ENOMEM)
2085 "Failed to allocate persistent memory object")
2086 .with_pmemobj_errormsg();
2089 "Failed to allocate persistent memory object")
2090 .with_pmemobj_errormsg();
2102 template <
typename T>
2106 if (
nullptr == pmemobj_pool_by_ptr(
this))
2117 template <
typename T>
2121 if (pmemobj_tx_stage() != TX_STAGE_WORK)
2123 "Function called out of transaction scope.");
2144 template <
typename T>
2145 template <
typename... Args>
2149 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2150 assert(_capacity >= count + _size);
2152 pointer dest = _data.get() + size();
2153 const_pointer
end = dest + count;
2154 for (; dest !=
end; ++dest)
2155 detail::create<value_type, Args...>(
2156 dest, std::forward<Args>(args)...);
2182 template <
typename T>
2183 template <
typename InputIt,
2184 typename std::enable_if<detail::is_input_iterator<InputIt>::value,
2189 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2190 difference_type range_size = std::distance(first, last);
2191 assert(range_size >= 0);
2192 assert(_capacity >= static_cast<size_type>(range_size) + _size);
2194 pointer dest = _data.get() + size();
2195 _size += static_cast<size_type>(range_size);
2196 while (first != last)
2197 detail::create<value_type>(dest++, *first++);
2215 template <
typename T>
2219 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2221 if (_data !=
nullptr) {
2223 if (pmemobj_tx_free(*_data.raw_ptr()) != 0)
2225 "failed to delete persistent memory object")
2226 .with_pmemobj_errormsg();
2239 template <
typename T>
2243 auto pop = pmemobj_pool_by_ptr(
this);
2244 assert(pop !=
nullptr);
2255 template <
typename T>
2259 while (first != last && d_last >=
cend())
2260 detail::create<value_type>(--d_last, std::move(*(--last)));
2263 std::move_backward(first, last, d_last);
2273 template <
typename T>
2274 template <
typename InputIt>
2278 auto count = static_cast<size_type>(std::distance(first, last));
2279 auto dest = _data.get() + idx;
2280 auto initialized_slots = static_cast<size_type>(
cend() - dest);
2284 dest = std::copy_n(first, (std::min)(initialized_slots, count),
2287 std::advance(first, (std::min)(initialized_slots, count));
2290 while (first != last)
2291 detail::create<value_type>(dest++, *first++);
2316 template <
typename T>
2317 template <
typename InputIt>
2321 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2323 auto count = static_cast<size_type>(std::distance(first, last));
2325 if (_capacity >= size() + count) {
2327 &_data[static_cast<difference_type>(size() + count)];
2328 pointer
begin = &_data[static_cast<difference_type>(idx)];
2329 pointer
end = &_data[static_cast<difference_type>(size())];
2331 add_data_to_tx(idx, size() - idx + count);
2334 move_elements_backward(
begin,
end, dest);
2337 construct_or_assign(idx, first, last);
2343 add_data_to_tx(0, _size);
2345 auto old_data = _data;
2346 auto old_size = _size;
2347 pointer old_begin = &_data[0];
2348 pointer old_mid = &_data[static_cast<difference_type>(idx)];
2349 pointer old_end = &_data[static_cast<difference_type>(size())];
2352 _size = _capacity = 0;
2354 alloc(get_recommended_capacity(old_size + count));
2357 construct_at_end(std::make_move_iterator(old_begin),
2358 std::make_move_iterator(old_mid));
2361 construct_at_end(first, last);
2364 construct_at_end(std::make_move_iterator(old_mid),
2365 std::make_move_iterator(old_end));
2368 for (size_type i = 0; i < old_size; ++i)
2369 detail::destroy<value_type>(
2370 old_data[static_cast<difference_type>(i)]);
2371 if (pmemobj_tx_free(old_data.raw()) != 0)
2373 "failed to delete persistent memory object")
2374 .with_pmemobj_errormsg();
2395 template <
typename T>
2399 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2405 add_data_to_tx(0, _size);
2407 auto old_data = _data;
2408 auto old_size = _size;
2409 pointer old_begin = &_data[0];
2410 pointer old_end = capacity_new < _size
2411 ? &_data[static_cast<difference_type>(capacity_new)]
2412 : &_data[static_cast<difference_type>(size())];
2415 _size = _capacity = 0;
2417 alloc(capacity_new);
2419 construct_at_end(std::make_move_iterator(old_begin),
2420 std::make_move_iterator(old_end));
2423 for (size_type i = 0; i < old_size; ++i)
2424 detail::destroy<value_type>(
2425 old_data[static_cast<difference_type>(i)]);
2426 if (pmemobj_tx_free(old_data.raw()) != 0)
2428 "failed to delete persistent memory object")
2429 .with_pmemobj_errormsg();
2438 template <
typename T>
2439 typename vector<T>::size_type
2461 template <
typename T>
2465 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2466 assert(size_new <= _size);
2468 add_data_to_tx(size_new, _size - size_new);
2470 for (size_type i = size_new; i < _size; ++i)
2471 detail::destroy<value_type>(
2472 _data[static_cast<difference_type>(i)]);
2485 template <
typename T>
2489 assert(idx_first + num <= capacity());
2491 #if LIBPMEMOBJ_CPP_VG_MEMCHECK_ENABLED
2493 assert(VALGRIND_CHECK_MEM_IS_ADDRESSABLE(_data.get() + idx_first,
2494 num *
sizeof(T)) == 0);
2497 auto initialized_num = size() - idx_first;
2500 detail::conditional_add_to_tx(_data.get() + idx_first,
2501 (std::min)(initialized_num, num),
2502 POBJ_XADD_ASSUME_INITIALIZED);
2504 if (num > initialized_num) {
2506 detail::conditional_add_to_tx(_data.get() + size(),
2507 num - initialized_num,
2508 POBJ_XADD_NO_SNAPSHOT);
2523 template <
typename T>
2542 template <
typename T>
2546 return !(lhs == rhs);
2559 template <
typename T>
2563 return std::lexicographical_compare(lhs.
begin(), lhs.
end(), rhs.
begin(),
2577 template <
typename T>
2581 return !(rhs < lhs);
2595 template <
typename T>
2612 template <
typename T>
2616 return !(lhs < rhs);
2630 template <
typename T>
2634 return lhs.
size() == rhs.size() &&
2635 std::equal(lhs.
begin(), lhs.
end(), rhs.begin());
2649 template <
typename T>
2653 return !(lhs == rhs);
2666 template <
typename T>
2670 return std::lexicographical_compare(lhs.
begin(), lhs.
end(), rhs.begin(),
2684 template <
typename T>
2688 return !(std::lexicographical_compare(rhs.begin(), rhs.end(),
2703 template <
typename T>
2707 return !(lhs <= rhs);
2720 template <
typename T>
2724 return !(lhs < rhs);
2738 template <
typename T>
2756 template <
typename T>
2760 return !(lhs == rhs);
2773 template <
typename T>
2790 template <
typename T>
2794 return !(rhs < lhs);
2808 template <
typename T>
2825 template <
typename T>
2829 return !(lhs < rhs);
2838 template <
typename T>