libs/hub/include/boost/container/hub.hpp

99.6% Lines (717/720) 90.9% List of functions (1593/1752)

[ ] prev/next file n p prev/next uncovered line

hub.hpp

f(x) Functions (1752)

Function Calls Lines Blocks

Line	Hits	Source Code
1		/* Hub container.
2		*
3		* Copyright 2025-2026 Joaquin M Lopez Munoz.
4		* Distributed under the Boost Software License, Version 1.0.
5		* (See accompanying file LICENSE_1_0.txt or copy at
6		* http://www.boost.org/LICENSE_1_0.txt)
7		*/
8
9		#ifndef BOOST_CONTAINER_HUB_HPP
10		#define BOOST_CONTAINER_HUB_HPP
11
12		#include <algorithm>
13		#include <boost/assert.hpp>
14		#include <boost/config.hpp>
15		#include <boost/config/workaround.hpp>
16		#include <boost/core/allocator_access.hpp>
17		#include <boost/core/bit.hpp>
18		#include <boost/core/empty_value.hpp>
19		#include <boost/core/no_exceptions_support.hpp>
20		#include <boost/core/pointer_traits.hpp>
21		#include <boost/throw_exception.hpp>
22		#include <cstddef>
23		#include <cstdint>
24		#include <functional>
25		#include <initializer_list>
26		#include <iterator>
27		#include <memory>
28		#include <new>
29		#include <stdexcept>
30		#include <type_traits>
31		#include <utility>
32
33		#ifndef BOOST_NO_CXX17_HDR_MEMORY_RESOURCE
34		#include <memory_resource>
35		#endif
36
37		#if defined(BOOST_NO_CXX20_HDR_CONCEPTS) \|\| defined(BOOST_NO_CXX20_HDR_RANGES)
38		#define BOOST_CONTAINER_HUB_NO_RANGES
39		#elif BOOST_WORKAROUND(BOOST_CLANG_VERSION, < 170100) && \
40		defined(BOOST_LIBSTDCXX_VERSION)
41		/* https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109647
42		* https://github.com/llvm/llvm-project/issues/49620
43		*/
44		#define BOOST_CONTAINER_HUB_NO_RANGES
45		#endif
46
47		#if !defined(BOOST_CONTAINER_HUB_NO_RANGES)
48		#include <concepts>
49		#include <ranges>
50		#endif
51
52		#if !defined(BOOST_CONTAINER_HUB_DISABLE_SSE2)
53		#if defined(BOOST_CONTAINER_HUB_ENABLE_SSE2)\|\| \
54		defined(__SSE2__) \|\| \
55		defined(_M_X64) \|\| (defined(_M_IX86_FP) && _M_IX86_FP >= 2)
56		#define BOOST_CONTAINER_HUB_SSE2
57		#endif
58		#endif
59
60		#if defined(BOOST_CONTAINER_HUB_SSE2)
61		#include <emmintrin.h>
62		#endif
63
64		#ifdef __has_builtin
65		#define BOOST_CONTAINER_HUB_HAS_BUILTIN(x) __has_builtin(x)
66		#else
67		#define BOOST_CONTAINER_HUB_HAS_BUILTIN(x) 0
68		#endif
69
70		#if !defined(NDEBUG)
71		#define BOOST_CONTAINER_HUB_ASSUME(cond) BOOST_ASSERT(cond)
72		#elif BOOST_CONTAINER_HUB_HAS_BUILTIN(__builtin_assume)
73		#define BOOST_CONTAINER_HUB_ASSUME(cond) __builtin_assume(cond)
74		#elif defined(__GNUC__) \|\| \
75		BOOST_CONTAINER_HUB_HAS_BUILTIN(__builtin_unreachable)
76		#define BOOST_CONTAINER_HUB_ASSUME(cond) \
77		do{ \
78		if(!(cond)) __builtin_unreachable(); \
79		} while(0)
80		#elif defined(_MSC_VER)
81		#define BOOST_CONTAINER_HUB_ASSUME(cond) __assume(cond)
82		#else
83		#define BOOST_CONTAINER_HUB_ASSUME(cond) \
84		do{ \
85		static_cast<void>(false && (cond)); \
86		} while(0)
87		#endif
88
89		/* We use BOOST_CONTAINER_HUB_PREFETCH[_BLOCK] macros rather than proper
90		* functions because of https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109985
91		*/
92
93		#if defined(BOOST_GCC) \|\| defined(BOOST_CLANG)
94		#define BOOST_CONTAINER_HUB_PREFETCH(p) \
95		__builtin_prefetch((const char*)boost::to_address(p))
96		#elif defined(BOOST_CONTAINER_HUB_SSE2)
97		#define BOOST_CONTAINER_HUB_PREFETCH(p) \
98		_mm_prefetch((const char*)boost::to_address(p), _MM_HINT_T0)
99		#else
100		#define BOOST_CONTAINER_HUB_PREFETCH(p) ((void)(p))
101		#endif
102
103		#define BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb, Block) \
104		do{ \
105		auto p0 = &static_cast<Block&>(*(pbb)); \
106		BOOST_CONTAINER_HUB_PREFETCH(p0->data()); \
107		} while(0)
108
109		#if defined(BOOST_MSVC)
110		#pragma warning(push)
111		#pragma warning(disable:4714) /* marked as __forceinline not inlined */
112		#endif
113
114		namespace boost {
115
116		namespace container {
117
118		template<typename T, typename Allocator = std::allocator<T>>
119		class hub;
120
121		template<typename T, typename Allocator, typename Predicate>
122		typename hub<T, Allocator>::size_type erase_if(hub<T, Allocator>&, Predicate);
123
124		namespace hub_detail {
125
126		template<typename ValuePointer> class iterator;
127
128		}
129
130		template<typename T, typename Allocator, typename F>
131		F for_each(hub<T, Allocator>&, F);
132
133		template<typename ValuePtr, typename F>
134		std::pair<hub_detail::iterator<ValuePtr>, F> for_each_while(
135		hub_detail::iterator<ValuePtr>, hub_detail::iterator<ValuePtr>, F);
136
137		#ifndef BOOST_NO_CXX17_HDR_MEMORY_RESOURCE
138		namespace pmr {
139
140		template<typename T>
141		using hub = boost::container::hub<T, std::pmr::polymorphic_allocator<T>>;
142
143		}
144		#endif
145
146		namespace hub_detail {
147
148	34185010x	inline int unchecked_countr_zero(std::uint64_t x)
149		{
150		#if defined(BOOST_MSVC) && (defined(_M_X64) \|\| defined(_M_ARM64))
151		unsigned long r;
152		_BitScanForward64(&r, x);
153		return (int)r;
154		#elif defined(BOOST_GCC) \|\| defined(BOOST_CLANG)
155	34185010x	return (int)__builtin_ctzll(x);
156		#else
157		BOOST_CONTAINER_HUB_ASSUME(x != 0);
158		return (int)core::countr_zero(x);
159		#endif
160		}
161
162	11233515x	inline int unchecked_countr_one(std::uint64_t x)
163		{
164	11233515x	return unchecked_countr_zero(~x);
165		}
166
167	627199x	inline int unchecked_countl_zero(std::uint64_t x)
168		{
169		#if defined(BOOST_MSVC) && (defined(_M_X64) \|\| defined(_M_ARM64))
170		unsigned long r;
171		_BitScanReverse64(&r, x);
172		return (int)(63 - r);
173		#elif defined(BOOST_GCC) \|\| defined(BOOST_CLANG)
174	627199x	return (int)__builtin_clzll(x);
175		#else
176		BOOST_CONTAINER_HUB_ASSUME(x != 0);
177		return (int)core::countl_zero(x);
178		#endif
179		}
180
181		template<typename Pointer, typename T>
182		using pointer_rebind_t =
183		typename pointer_traits<Pointer>::template rebind<T>;
184
185		template<typename VoidPointer>
186		struct block_base
187		{
188		using pointer = pointer_rebind_t<VoidPointer, block_base>;
189		using const_pointer = pointer_rebind_t<VoidPointer, const block_base>;
190		using mask_type = std::uint64_t;
191
192		static constexpr int N = 64;
193		static constexpr mask_type full = (mask_type)(-1);
194
195	22512508x	static pointer pointer_to(block_base& x) noexcept
196		{
197	22512508x	return pointer_traits<pointer>::pointer_to(x);
198		}
199
200	442381x	static const_pointer pointer_to(const block_base& x) noexcept
201		{
202	442381x	return pointer_traits<const_pointer>::pointer_to(x);
203		}
204
205		BOOST_FORCEINLINE void link_available_before(pointer p) noexcept
206		{
207	208703x	next_available = p;
208	208703x	prev_available = p->prev_available;
209	209689x	next_available->prev_available = pointer_to(*this);
210	209689x	prev_available->next_available = pointer_to(*this);
211	209452x	}
212
213		BOOST_FORCEINLINE void link_available_after(pointer p) noexcept
214		{
215	117702x	prev_available = p;
216	117702x	next_available = p->next_available;
217	117830x	next_available->prev_available = pointer_to(*this);
218	117830x	prev_available->next_available = pointer_to(*this);
219	117798x	}
220
221		BOOST_FORCEINLINE void unlink_available() noexcept
222		{
223	227239x	prev_available->next_available = next_available;
224	227429x	next_available->prev_available = prev_available;
225	227239x	}
226
227		BOOST_FORCEINLINE void link_before(pointer p) noexcept
228		{
229	168727x	next = p;
230	168727x	prev = p->prev;
231	169495x	next->prev = pointer_to(*this);
232	169509x	prev->next = pointer_to(*this);
233	169323x	}
234
235		BOOST_FORCEINLINE void unlink() noexcept
236		{
237	99210x	prev->next = next;
238	99307x	next->prev = prev;
239	99210x	}
240
241		pointer prev_available,
242		next_available,
243		prev,
244		next;
245		mask_type mask;
246		};
247
248		template<typename ValuePointer>
249		struct block: block_base<pointer_rebind_t<ValuePointer, void>>
250		{
251		using super = block_base<pointer_rebind_t<ValuePointer, void>>;
252		using pointer = pointer_rebind_t<ValuePointer, block>;
253
254	44905932x	ValuePointer data() noexcept { return data_; }
255		ValuePointer data_;
256
257		static pointer
258	15865788x	static_cast_block_pointer(typename super::pointer pbb) noexcept
259		{
260	15865788x	return pointer_traits<pointer>::pointer_to(static_cast<block&>(*pbb));
261		}
262		};
263
264		template<typename ValuePointer>
265	17940x	void swap_payload(block<ValuePointer>& x, block<ValuePointer>& y) noexcept
266		{
267	17940x	std::swap(x.mask, y.mask);
268	17940x	std::swap(x.data_, y.data_);
269	17940x	}
270
271		template<typename ValuePointer>
272		struct block_list: block<ValuePointer>
273		{
274		using block = hub_detail::block<ValuePointer>;
275		using block_base = typename block::super;
276		using block_base_pointer = typename block_base::pointer;
277		using const_block_base_pointer = typename block_base::const_pointer;
278		using block_pointer = typename block::pointer;
279		using block_base::full;
280		using block_base::pointer_to;
281		using block_base::prev_available;
282		using block_base::next_available;
283		using block_base::prev;
284		using block_base::next;
285		using block_base::mask;
286		using block::data_;
287
288	566x	block_list()
289	62x	{
290	566x	reset();
291	566x	mask = 1; /* sentinel */
292	566x	data_ = nullptr;
293	566x	}
294
295	47x	block_list(block_list&& x) noexcept: block_list{}
296		{
297	52x	if(x.next_available != x.header()) {
298	45x	prev_available = x.prev_available;
299	45x	next_available = x.next_available;
300	50x	next_available->prev_available = header();
301	55x	prev_available->next_available = header();
302		}
303	52x	if(x.prev != x.header()) {
304	45x	prev = x.prev;
305	45x	next = x.next;
306	50x	next->prev = header();
307	55x	prev->next = header();
308		}
309	47x	x.reset();
310	47x	}
311
312	61x	block_list& operator=(block_list&& x) noexcept
313		{
314	61x	reset();
315	73x	if(x.next_available != x.header()) {
316	49x	prev_available = x.prev_available;
317	49x	next_available = x.next_available;
318	58x	next_available->prev_available = header();
319	67x	prev_available->next_available = header();
320		}
321	73x	if(x.prev != x.header()) {
322	53x	prev = x.prev;
323	53x	next = x.next;
324	63x	next->prev = header();
325	73x	prev->next = header();
326		}
327	61x	x.reset();
328	61x	return *this;
329		}
330
331	1339x	void reset() noexcept
332		{
333	1339x	prev_available = header();
334	1339x	next_available = header();
335	1339x	prev = header();
336	1339x	next = header();
337	1339x	}
338
339	11113642x	block_base_pointer header() noexcept
340		{
341	11113642x	return pointer_to(static_cast<block_base&>(*this));
342		}
343
344	442381x	const_block_base_pointer header() const noexcept
345		{
346	442381x	return pointer_to(static_cast<const block_base&>(*this));
347		}
348
349		BOOST_FORCEINLINE void link_at_back(block_pointer pb) noexcept
350		{
351	168713x	pb->link_before(header());
352	169309x	}
353
354		BOOST_FORCEINLINE void link_before(
355		block_pointer pbx, block_pointer pby) noexcept
356		{
357	14x	pbx->link_before(pby);
358	14x	}
359
360		BOOST_FORCEINLINE static void unlink(block_pointer pb) noexcept
361		{
362	59619x	pb->unlink();
363	99515x	}
364
365		BOOST_FORCEINLINE void link_available_at_back(block_pointer pb) noexcept
366		{
367	208703x	pb->link_available_before(header());
368	209452x	}
369
370		BOOST_FORCEINLINE void link_available_at_front(block_pointer pb) noexcept
371		{
372	117702x	pb->link_available_after(header());
373	117798x	}
374
375		BOOST_FORCEINLINE void unlink_available(block_pointer pb) noexcept
376		{
377	227239x	pb->unlink_available();
378	227833x	}
379		};
380
381		template<typename ValuePointer>
382		class iterator
383		{
384		using element_type = typename pointer_traits<ValuePointer>::element_type;
385		template<typename Value2Pointer>
386		using enable_if_consts_to_element_type_t =typename std::enable_if<
387		std::is_same<
388		const typename pointer_traits<Value2Pointer>::element_type,
389		element_type>::value
390		>::type;
391
392		public:
393		using value_type = typename std::remove_const<element_type>::type;
394		using difference_type =
395		typename pointer_traits<ValuePointer>::difference_type;
396		using pointer = ValuePointer;
397		using reference = element_type&;
398		using iterator_category = std::bidirectional_iterator_tag;
399
400		iterator() = default;
401	25003x	iterator(const iterator&) = default;
402
403		template<
404		typename Value2Pointer,
405		typename = enable_if_consts_to_element_type_t<Value2Pointer>
406		>
407	3963x	iterator(const iterator<Value2Pointer>& x) noexcept: pbb{x.pbb}, n{x.n} {}
408
409	2804x	iterator& operator=(const iterator& x) = default;
410
411		template<
412		typename Value2Pointer,
413		typename = enable_if_consts_to_element_type_t<Value2Pointer>
414		>
415	3974x	iterator& operator=(const iterator<Value2Pointer>& x) noexcept
416		{
417	3974x	pbb = x.pbb;
418	3974x	n = x.n;
419	3974x	return *this;
420		}
421
422	11545240x	pointer operator->() const noexcept
423		{
424	11633560x	return static_cast<block&>(*pbb).data() + n;
425		}
426
427	11545166x	reference operator*() const noexcept
428		{
429	11589308x	return *operator->();
430		}
431
432		BOOST_FORCEINLINE iterator& operator++() noexcept
433		{
434	7737387x	auto mask = pbb->mask & (full << 1 << n);
435	7262084x	if(BOOST_UNLIKELY(mask == 0)) {
436	593747x	pbb = pbb->next;
437	607859x	BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb->next, block);
438	604344x	mask = pbb->mask;
439		}
440	8117833x	n = hub_detail::unchecked_countr_zero(mask);
441	8117833x	return *this;
442		}
443
444		BOOST_FORCEINLINE iterator operator++(int) noexcept
445		{
446	854034x	iterator tmp(*this);
447		this->operator++();
448	854034x	return tmp;
449		}
450
451		BOOST_FORCEINLINE iterator& operator--() noexcept
452		{
453	9025x	auto mask = pbb->mask & (full >> 1 >> (N - 1 - n));
454	35074x	if(BOOST_UNLIKELY(mask == 0)) {
455	810x	pbb = pbb->prev;
456	2430x	BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb->prev, block);
457	2025x	mask = pbb->mask;
458		}
459	36100x	n = N - 1 - hub_detail::unchecked_countl_zero(mask);
460	36100x	return *this;
461		}
462
463		BOOST_FORCEINLINE iterator operator--(int) noexcept
464		{
465	1368x	iterator tmp(*this);
466		this->operator--();
467	1368x	return tmp;
468		}
469
470	8040489x	friend bool operator==(const iterator& x, const iterator& y) noexcept
471		{
472	8130660x	return x.pbb == y.pbb && x.n == y.n;
473		}
474
475	7140215x	friend bool operator!=(const iterator& x, const iterator& y) noexcept
476		{
477	7140215x	return !(x == y);
478		}
479
480		private:
481		template<typename> friend class iterator;
482		template<typename, typename> friend class container::hub;
483		template<typename VP, typename F>
484		friend std::pair<hub_detail::iterator<VP>, F> container::for_each_while(
485		hub_detail::iterator<VP>, hub_detail::iterator<VP>, F);
486		template<typename HubIt, typename F>
487		friend HubIt for_each_while_core(
488		typename HubIt::block_base_pointer,typename HubIt::block_base_pointer,
489		F&&);
490
491		template<typename T>
492		using pointer_rebind_t = hub_detail::pointer_rebind_t<ValuePointer, T>;
493		using block_base = hub_detail::block_base<pointer_rebind_t<void>>;
494		using block_base_pointer = pointer_rebind_t<block_base>;
495		using const_block_base_pointer = pointer_rebind_t<const block_base>;
496		using nonconst_pointer = pointer_rebind_t<value_type>; /* used by Natvis */
497		using block = hub_detail::block<nonconst_pointer>;
498		using mask_type = typename block_base::mask_type;
499
500		static constexpr int N = block_base::N;
501		static constexpr mask_type full = block_base::full;
502
503	10405188x	iterator(const_block_base_pointer pbb_, int n_) noexcept:
504	10405188x	pbb{const_cast_block_base_pointer(pbb_)}, n{n_} {}
505
506	532x	iterator(const_block_base_pointer pbb_) noexcept:
507	532x	pbb{const_cast_block_base_pointer(pbb_)},
508	652x	n{hub_detail::unchecked_countr_zero(pbb->mask)}
509	532x	{}
510
511		static block_base_pointer
512	10405720x	const_cast_block_base_pointer(const_block_base_pointer pbb_) noexcept
513		{
514	10405720x	return block_base::pointer_to(const_cast<block_base&>(*pbb_));
515		}
516
517		block_base_pointer pbb = nullptr;
518		int n = 0;
519		};
520
521		template<typename HubIterator, typename F>
522	1438x	HubIterator for_each_while_core(
523		typename HubIterator::block_base_pointer pbb,
524		typename HubIterator::block_base_pointer last_pbb, F&& f)
525		{
526		using block = typename HubIterator::block;
527
528	1438x	BOOST_ASSERT(pbb != last_pbb);
529	1438x	auto pb = block::static_cast_block_pointer(pbb);
530	1438x	auto mask = pb->mask;
531	1438x	auto n = unchecked_countr_zero(mask);
532	1438x	auto pd = pb->data();
533		do {
534	157117x	pbb = pb->next;
535	157117x	auto next_mask = pbb->mask;
536	157117x	auto next_n = unchecked_countr_zero(next_mask);
537	157525x	auto next_pd = block::static_cast_block_pointer(pbb)->data();
538	157525x	BOOST_CONTAINER_HUB_PREFETCH(next_pd + next_n);
539	157117x	BOOST_CONTAINER_HUB_PREFETCH(pbb->next);
540		for(; ; ) {
541	4903163x	if(!f(pd[n])) return {pb, n};
542	4886458x	mask &= mask - 1;
543	4886458x	if(!mask) break;
544	4730270x	n = unchecked_countr_zero(mask);
545		}
546	156188x	pb = block::static_cast_block_pointer(pbb);
547	156188x	mask = next_mask;
548	156188x	n = next_n;
549	156012x	pd = next_pd;
550	156188x	} while(pb != last_pbb);
551	509x	return {last_pbb};
552		}
553
554		template<typename T, std::size_t N>
555		struct sort_iterator
556		{
557		using value_type = T;
558		using difference_type = std::ptrdiff_t;
559		using pointer = T*;
560		using reference = T&;
561		using iterator_category = std::random_access_iterator_tag;
562
563	998909x	sort_iterator(T** pp_, difference_type index_): pp{pp_}, index{index_} {}
564
565	133126286x	pointer operator->() const noexcept
566		{
567	133126286x	return pp[(std::size_t)index / N] + ((std::size_t)index % N);
568		}
569
570	133126286x	reference operator*() const noexcept
571		{
572	133126286x	return *operator->();
573		}
574
575	24816551x	sort_iterator& operator++() noexcept
576		{
577	24816551x	++index;
578	24816551x	return *this;
579		}
580
581		sort_iterator operator++(int) noexcept
582		{
583		sort_iterator tmp(*this);
584		++index;
585		return tmp;
586		}
587
588	30159473x	sort_iterator& operator--() noexcept
589		{
590	30159473x	--index;
591	30159473x	return *this;
592		}
593
594		sort_iterator operator--(int) noexcept
595		{
596		sort_iterator tmp(*this);
597		--index;
598		return tmp;
599		}
600
601		friend difference_type
602	749178x	operator-(const sort_iterator& x, const sort_iterator& y) noexcept
603		{
604	749178x	return x.index - y.index;
605		}
606
607		sort_iterator& operator+=(difference_type n) noexcept
608		{
609		index += n;
610		return *this;
611		}
612
613		friend sort_iterator
614	749178x	operator+(const sort_iterator& x, difference_type n) noexcept
615		{
616	749178x	return {x.pp, x.index + n};
617		}
618
619		friend sort_iterator
620		operator+(difference_type n, const sort_iterator& x) noexcept
621		{
622		return {x.pp, n + x.index};
623		}
624
625		sort_iterator& operator-=(difference_type n) noexcept
626		{
627		index -= n;
628		return *this;
629		}
630
631		friend sort_iterator
632	249709x	operator-(const sort_iterator& x, difference_type n) noexcept
633		{
634	249709x	return {x.pp, x.index - n};
635		}
636
637		reference operator[](difference_type n) const noexcept
638		{
639		return (this + n);
640		}
641
642		friend bool
643	8x	operator==(const sort_iterator& x, const sort_iterator& y) noexcept
644		{
645	8x	return x.index == y.index;
646		}
647
648		friend bool
649	2400531x	operator!=(const sort_iterator& x, const sort_iterator& y) noexcept
650		{
651	2400531x	return x.index != y.index;
652		}
653
654		friend bool
655	8674178x	operator<(const sort_iterator& x, const sort_iterator& y) noexcept
656		{
657	8674178x	return x.index < y.index;
658		}
659
660		friend bool
661		operator>(const sort_iterator& x, const sort_iterator& y) noexcept
662		{
663		return x.index > y.index;
664		}
665
666		friend bool
667		operator<=(const sort_iterator& x, const sort_iterator& y) noexcept
668		{
669		return x.index <= y.index;
670		}
671
672		friend bool
673		operator>=(const sort_iterator& x, const sort_iterator& y) noexcept
674		{
675		return x.index >= y.index;
676		}
677
678		T** pp;
679		difference_type index;
680		};
681
682		template<typename T, typename Allocator>
683		struct buffer
684		{
685	31x	buffer(std::size_t n, Allocator al_) noexcept: al{al_}
686		{
687	31x	allocate_data(n);
688	31x	if(data) capacity = n;
689	31x	}
690
691	31x	~buffer()
692		{
693	31x	if(data) {
694	458x	for(; begin_ != end_; ++begin_) allocator_destroy(al, begin());
695	31x	deallocate_data();
696		}
697	31x	}
698
699	4825271x	T* begin() const noexcept { return data + begin_; }
700	2412866x	T* end() const noexcept { return data + end_; }
701
702		template<typename... Args>
703	2412838x	void emplace_back(Args&&... args)
704		{
705	2412838x	BOOST_ASSERT(data && end_ != capacity);
706	2412838x	allocator_construct(al, end(), std::forward<Args>(args)...);
707	2412835x	++end_;
708	2412835x	}
709
710	2412408x	void erase_front() noexcept
711		{
712	2412408x	BOOST_ASSERT(data && begin_ != end_);
713	2412408x	allocator_destroy(al, begin());
714	2412408x	++begin_;
715	2412408x	}
716
717		Allocator al;
718		std::size_t begin_ = 0, end_ = 0;
719		std::size_t capacity = 0;
720		T* data = nullptr;
721
722		private:
723		#if defined(__cpp_aligned_new) && __cpp_aligned_new >= 201606L
724		using aligned_new_required = std::integral_constant<
725		bool, (alignof(T) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)>;
726
727	31x	void allocate_data(std::size_t n)
728		{
729	31x	data = static_cast<T>(allocate(n sizeof(T), aligned_new_required{}));
730	31x	}
731
732	30x	static void* allocate(std::size_t m, std::false_type)
733		{
734	30x	return ::operator new[](m, std::nothrow);
735		}
736
737	1x	static void* allocate(std::size_t m, std::true_type)
738		{
739	1x	return ::operator new[](m, std::align_val_t{alignof(T)}, std::nothrow);
740		}
741
742	31x	void deallocate_data() { deallocate(data, aligned_new_required{}); }
743
744	30x	static void deallocate(void* p, std::false_type) { ::operator delete[](p); }
745
746	1x	static void deallocate(void* p, std::true_type)
747		{
748	1x	::operator delete[](p, std::align_val_t{alignof(T)});
749	1x	}
750		#else
751		void allocate_data(std::size_t n)
752		{
753		data = static_cast<T>(::operator new[](n sizeof(T), std::nothrow));
754		}
755
756		void deallocate_data() { ::operator delete[](data); }
757		#endif
758		};
759
760		template<typename T>
761		struct nodtor_deleter
762		{
763		using pointer = T*;
764		void operator()(pointer p) noexcept { ::operator delete(p); }
765		};
766
767		template<typename T>
768		struct nodtor_deleter<T[]>
769		{
770		using pointer = T*;
771	22x	void operator()(pointer p) noexcept { ::operator delete[](p); }
772		};
773
774		template<typename T>
775		using nodtor_unique_ptr = std::unique_ptr<T, nodtor_deleter<T>>;
776
777		template<typename T>
778		struct type_identity { using type = T; };
779
780		template<typename T>
781		using type_identity_t = typename type_identity<T>::type;
782
783		#if !defined(BOOST_CONTAINER_HUB_NO_RANGES)
784		template<class R, class T>
785		concept container_compatible_range =
786		std::ranges::input_range<R> &&
787		std::convertible_to<std::ranges::range_reference_t<R>, T>;
788
789		/* Use own from_range_t only if std::from_range_t does not exist.
790		* Technique explained at
791		https://bannalia.blogspot.com/2016/09/compile-time-checking-existence-of.html
792		*/
793
794		struct from_range_t{ explicit from_range_t() = default; };
795		struct from_range_t_hook{};
796
797		} /* namespace hub_detail */
798		} /* namespace container */
799		} /* namespace boost */
800
801		namespace std {
802
803		template<> struct hash< ::boost::container::hub_detail::from_range_t_hook>
804		{
805		using from_range_t_type = decltype([] {
806		using namespace ::boost::container::hub_detail;
807		return from_range_t{};
808		}());
809
810		/* make standard happy */
811		std::size_t operator()(
812		const ::boost::container::hub_detail::from_range_t_hook&) const;
813		};
814
815		}
816
817		namespace boost {
818		namespace container {
819
820		/* TODO: this may collide with other same-named entities in different
821		* parts of Boost.Container.
822		*/
823		using from_range_t =
824		typename std::hash<hub_detail::from_range_t_hook>::from_range_t_type;
825		inline constexpr from_range_t from_range {};
826
827		namespace hub_detail {
828		#endif
829
830		template<typename InputIterator>
831		using enable_if_is_input_iterator_t =
832		typename std::enable_if<
833		std::is_convertible<
834		typename std::iterator_traits<InputIterator>::iterator_category,
835		std::input_iterator_tag
836		>::value
837		>::type;
838
839		/* std::pmr::polymorphic_allocator::destroy may be marked as deprecated.
840		* C&P from boost/core/allocator_access.hpp.
841		*/
842		#if defined(_LIBCPP_SUPPRESS_DEPRECATED_PUSH)
843		_LIBCPP_SUPPRESS_DEPRECATED_PUSH
844		#endif
845		#if defined(_STL_DISABLE_DEPRECATED_WARNING)
846		_STL_DISABLE_DEPRECATED_WARNING
847		#endif
848		#if defined(__clang__) && defined(__has_warning)
849		# if __has_warning("-Wdeprecated-declarations")
850		# pragma clang diagnostic push
851		# pragma clang diagnostic ignored "-Wdeprecated-declarations"
852		# endif
853		#elif defined(_MSC_VER)
854		# pragma warning(push)
855		# pragma warning(disable: 4996)
856		#elif defined(BOOST_GCC) && BOOST_GCC >= 40600
857		# pragma GCC diagnostic push
858		# pragma GCC diagnostic ignored "-Wdeprecated-declarations"
859		#endif
860
861		template<typename Allocator, typename Ptr, typename = void>
862		struct allocator_has_destroy: std::false_type {};
863
864		template<typename Allocator, typename Ptr>
865		struct allocator_has_destroy<
866		Allocator, Ptr,
867		decltype((void)std::declval<Allocator&>().destroy(std::declval<Ptr>()))
868		>: std::true_type {};
869
870		#if defined(__clang__) && defined(__has_warning)
871		# if __has_warning("-Wdeprecated-declarations")
872		# pragma clang diagnostic pop
873		# endif
874		#elif defined(_MSC_VER)
875		# pragma warning(pop)
876		#elif defined(BOOST_GCC) && BOOST_GCC >= 40600
877		# pragma GCC diagnostic pop
878		#endif
879		#if defined(_STL_RESTORE_DEPRECATED_WARNING)
880		_STL_RESTORE_DEPRECATED_WARNING
881		#endif
882		#if defined(_LIBCPP_SUPPRESS_DEPRECATED_POP)
883		_LIBCPP_SUPPRESS_DEPRECATED_POP
884		#endif
885
886		template<typename Allocator>
887		struct is_std_allocator: std::false_type {};
888
889		template<typename T>
890		struct is_std_allocator<std::allocator<T>>: std::true_type {};
891
892		template<typename Allocator>
893		struct is_std_pmr_polymorphic_allocator: std::false_type {};
894
895		#ifndef BOOST_NO_CXX17_HDR_MEMORY_RESOURCE
896		template<typename T>
897		struct is_std_pmr_polymorphic_allocator<std::pmr::polymorphic_allocator<T>>:
898		std::true_type {};
899		#endif
900
901		struct if_constexpr_void_else{ void operator()() const {} };
902
903		template<typename F, typename G = if_constexpr_void_else>
904	2x	void if_constexpr(std::true_type, F f, G = G{}) { f(); }
905
906		template<typename F, typename G = if_constexpr_void_else>
907	19x	void if_constexpr(std::false_type, F, G g = G{}) { g(); }
908
909		template<typename T>
910	23x	void copy_assign_if(std::true_type, T& x, const T& y) { x = y; }
911
912		template<typename T>
913	27x	void copy_assign_if(std::false_type, T&, const T&) {}
914
915		template<typename T>
916	10x	void move_assign_if(std::true_type, T& x, T& y) { x = std::move(y); }
917
918		template<typename T>
919	7x	void move_assign_if(std::false_type, T&, T&) {}
920
921		template<typename T>
922	2x	void swap_if(std::true_type, T& x, T& y) { using std::swap; swap(x, y); }
923
924		template<typename T>
925		void swap_if(std::false_type, T&, T&) {}
926
927		template<typename Allocator>
928		struct block_typedefs
929		{
930		using pointer = allocator_pointer_t<Allocator>;
931		template<typename Q>
932		using pointer_rebind_t = hub_detail::pointer_rebind_t<pointer, Q>;
933
934		using block_base = hub_detail::block_base<pointer_rebind_t<void>>;
935		using block_base_pointer = pointer_rebind_t<block_base>;
936		using const_block_base_pointer = pointer_rebind_t<const block_base>;
937		using block = hub_detail::block<pointer>;
938		using block_pointer = pointer_rebind_t<block>;
939		using block_allocator = allocator_rebind_t<Allocator,block>;
940		using block_list = hub_detail::block_list<pointer>;
941		};
942
943		} /* namespace container::hub_detail */
944
945		template<typename T, typename Allocator>
946		class hub: empty_value<
947		typename hub_detail::block_typedefs<Allocator>::block_allocator, 0>
948		{
949		static_assert(
950		!std::is_const<T>::value && !std::is_volatile<T>::value &&
951		!std::is_function<T>::value && !std::is_reference<T>::value &&
952		!std::is_void<T>::value,
953		"T must be a cv-unqualified object type");
954		static_assert(
955		std::is_same<T, allocator_value_type_t<Allocator>>::value,
956		"Allocator's value_type must be the same type as T");
957
958		public:
959		using value_type = T;
960		using allocator_type = Allocator;
961		using pointer = allocator_pointer_t<Allocator>;
962		using const_pointer = allocator_const_pointer_t<Allocator>;
963		using reference = T&;
964		using const_reference = const T&;
965		using size_type = allocator_size_type_t<Allocator>;
966		using difference_type = allocator_difference_type_t<Allocator>;
967		using iterator = hub_detail::iterator<pointer>;
968		using const_iterator = hub_detail::iterator<const_pointer>;
969		using reverse_iterator = std::reverse_iterator<iterator>;
970		using const_reverse_iterator = std::reverse_iterator<const_iterator>;
971
972	106x	hub() noexcept(noexcept(Allocator())): hub{Allocator()} {}
973
974	519x	explicit hub(const Allocator& al_) noexcept:
975	519x	allocator_base{empty_init, al_} {}
976
977	23x	explicit hub(size_type n, const Allocator& al_ = Allocator()): hub{al_}
978		{
979	23x	range_insert_impl(size_type(0), n, [&, this] (T* p, size_type) {
980	228x	allocator_construct(al(), p);
981		});
982	23x	}
983
984	36x	hub(size_type n, const T& x, const Allocator& al_ = Allocator()): hub{al_}
985		{
986	36x	insert(n, x);
987	36x	}
988
989		template<
990		typename InputIterator,
991		typename = hub_detail::enable_if_is_input_iterator_t<InputIterator>
992		>
993	263x	hub(
994		InputIterator first, InputIterator last,
995	263x	const Allocator& al_ = Allocator()): hub{al_}
996		{
997	263x	insert(first, last);
998	263x	}
999
1000		#if !defined(BOOST_CONTAINER_HUB_NO_RANGES)
1001		template<hub_detail::container_compatible_range<T> R>
1002	13x	hub(from_range_t, R&& rg, const Allocator& al_ = Allocator()): hub{al_}
1003		{
1004	13x	insert_range(std::forward<R>(rg));
1005	13x	}
1006		#endif
1007
1008	108x	hub(const hub& x):
1009	132x	hub{x, allocator_select_on_container_copy_construction(x.al())} {}
1010
1011	112x	hub(const hub& x, const hub_detail::type_identity_t<Allocator>& al_):
1012	112x	hub(x.begin(), x.end(), al_) {}
1013
1014	24x	hub(hub&& x) noexcept:
1015	28x	hub{std::move(x), Allocator(std::move(x.al())), std::true_type{}} {}
1016
1017	26x	hub(hub&& x, const hub_detail::type_identity_t<Allocator>& al_):
1018	26x	hub{std::move(x), al_, allocator_is_always_equal_t<Allocator>{}} {}
1019
1020	15x	hub(std::initializer_list<T> il, const Allocator& al_ = Allocator()):
1021	15x	hub{il.begin(), il.end(), al_} {}
1022
1023	545x	~hub() { reset(); }
1024
1025	50x	hub& operator=(const hub& x)
1026		{
1027		using pocca =
1028		allocator_propagate_on_container_copy_assignment_t<Allocator>;
1029
1030	50x	if(this != &x) {
1031	52x	if(al() != x.al() && pocca::value) {
1032	10x	reset();
1033	10x	hub_detail::copy_assign_if(pocca{}, al(), x.al());
1034	10x	insert(x.begin(), x.end());
1035		}
1036		else{
1037	40x	hub_detail::copy_assign_if(pocca{}, al(), x.al());
1038	40x	assign(x.begin(), x.end());
1039		}
1040		}
1041	14x	return *this;
1042		}
1043
1044	27x	hub& operator=(hub&& x)
1045		noexcept(
1046		allocator_propagate_on_container_move_assignment_t<Allocator>::value \|\|
1047		allocator_is_always_equal_t<Allocator>::value)
1048		{
1049	27x	if(this != &x) {
1050	27x	move_assign(
1051		x,
1052		std::integral_constant<
1053		bool,
1054		allocator_propagate_on_container_move_assignment_t<Allocator>::
1055		value \|\|
1056		allocator_is_always_equal_t<Allocator>::value>{});
1057		}
1058	18x	return *this;
1059		}
1060
1061	7x	hub& operator=(std::initializer_list<T> il)
1062		{
1063	7x	assign(il);
1064	4x	return *this;
1065		}
1066
1067		template<
1068		typename InputIterator,
1069		typename = hub_detail::enable_if_is_input_iterator_t<InputIterator>
1070		>
1071	79x	void assign(InputIterator first, InputIterator last)
1072		{
1073	79x	range_assign_impl(
1074		first, last,
1075		[this] (T* p, InputIterator it) { allocator_construct(al(), p, *it); },
1076		[] (T* p, InputIterator it) { p = it; });
1077	25x	}
1078
1079		#if !defined(BOOST_CONTAINER_HUB_NO_RANGES)
1080		template<hub_detail::container_compatible_range<T> R>
1081	16x	void assign_range(R&& rg)
1082		{
1083	16x	range_assign_impl(
1084		std::ranges::begin(rg), std::ranges::end(rg),
1085	515x	[this] (T* p, auto it) { allocator_construct(al(), p, *it); },
1086	3725x	[] (T* p, auto it) { p = it; });
1087	4x	}
1088		#endif
1089
1090	20x	void assign(size_type n, const T& x)
1091		{
1092	20x	range_assign_impl(
1093		size_type(0), n,
1094		[&, this] (T* p, size_type) { allocator_construct(al(), p, x); },
1095		[&] (T* p, size_type) { *p = x; });
1096	20x	}
1097
1098	23x	void assign(std::initializer_list<T> il) { assign(il.begin(), il.end()); }
1099
1100	64x	allocator_type get_allocator() const noexcept { return al(); }
1101
1102	3376x	iterator begin() noexcept { return ++end(); }
1103	441610x	const_iterator begin() const noexcept { return ++end(); }
1104	21040x	iterator end() noexcept { return {blist.header(), 0}; }
1105	442381x	const_iterator end() const noexcept { return {blist.header(), 0}; }
1106	8x	reverse_iterator rbegin() noexcept { return reverse_iterator{end()}; }
1107	12x	const_reverse_iterator rbegin() const noexcept
1108	12x	{ return const_reverse_iterator{end()}; }
1109	8x	reverse_iterator rend() noexcept { return reverse_iterator{begin()}; }
1110	12x	const_reverse_iterator rend() const noexcept
1111	12x	{ return const_reverse_iterator{begin()}; }
1112	1074x	const_iterator cbegin() const noexcept { return begin(); }
1113	1201x	const_iterator cend() const noexcept { return end(); }
1114	4x	const_reverse_iterator crbegin() const noexcept { return rbegin(); }
1115	4x	const_reverse_iterator crend() const noexcept { return rend(); }
1116
1117	65x	bool empty() const noexcept { return size_ == 0; }
1118	220860x	size_type size() const noexcept { return size_; }
1119
1120	52x	size_type max_size() const noexcept
1121		{
1122		std::size_t
1123	52x	bs = (std::size_t)allocator_max_size(al()) * sizeof(block),
1124	76x	vs = (std::size_t)allocator_max_size(Allocator(al())) * sizeof(T);
1125		return
1126	52x	(size_type)((std::min)(bs, vs) / (sizeof(block) + sizeof(T) * N) * N);
1127		}
1128
1129	1295x	size_type capacity() const noexcept { return num_blocks * N; }
1130
1131	40x	void reserve(size_type n)
1132		{
1133	40x	if(n > max_size()) {
1134	8x	BOOST_THROW_EXCEPTION(
1135		std::length_error("Requested capacity greater than max_size()"));
1136		}
1137	304x	while(capacity() < n) (void)create_new_available_block();
1138	28x	}
1139
1140	24x	void shrink_to_fit()
1141		{
1142	24x	compact();
1143	24x	trim_capacity();
1144	24x	}
1145
1146	38x	void trim_capacity() noexcept { trim_capacity(0); }
1147
1148	44x	void trim_capacity(size_type n) noexcept
1149		{
1150	44x	if(capacity() <= n) return;
1151	51x	for(auto pbb = blist.header()->prev_available;
1152	439x	capacity() - n >= N && pbb != blist.header() && pbb->mask == 0; ) {
1153	282x	auto pb = static_cast_block_pointer(pbb);
1154	282x	pbb = pbb-> prev_available;
1155	336x	blist.unlink_available(pb);
1156	282x	delete_block(pb);
1157	282x	--num_blocks;
1158		}
1159		}
1160
1161		template<typename... Args>
1162		BOOST_FORCEINLINE iterator emplace(Args&&... args)
1163		{
1164	9934664x	auto pbb = blist.next_available; /* for construct_or_restore_capacity */
1165		int n;
1166	9935434x	auto pb = retrieve_available_block(n);
1167	19872504x	construct_or_restore_capacity(
1168	9935434x	boost::to_address(pb->data() + n), pbb, std::forward<Args>(args)...);
1169	9934592x	auto mask_plus_one = (pb->mask \|= pb->mask + 1) + 1;
1170	9935819x	if(BOOST_UNLIKELY(mask_plus_one <= 2)) {
1171		/* pb->mask == 0 (impossible), 1 or full */
1172	310512x	if(mask_plus_one == 0) blist.unlink_available(pb);
1173	155285x	else /* pb->mask == 1 */ blist.link_at_back(pb);
1174		}
1175	9934592x	++size_;
1176	9935819x	return {pb, n};
1177		}
1178
1179		template<typename... Args>
1180		BOOST_FORCEINLINE iterator emplace_hint(const_iterator, Args&&... args)
1181		{
1182	26x	return emplace(std::forward<Args>(args)...);
1183		}
1184
1185	1604x	BOOST_FORCEINLINE iterator insert(const T& x) { return emplace(x); }
1186		BOOST_FORCEINLINE iterator insert(const_iterator, const T& x)
1187	4x	{ return emplace(x); }
1188	19868384x	BOOST_FORCEINLINE iterator insert(T&& x) { return emplace(std::move(x)); }
1189		BOOST_FORCEINLINE iterator insert(const_iterator, T&& x)
1190	32x	{ return emplace(std::move(x)); }
1191
1192	16x	void insert(std::initializer_list<T> il) { insert(il.begin(), il.end()); }
1193
1194		#if !defined(BOOST_CONTAINER_HUB_NO_RANGES)
1195		template<hub_detail::container_compatible_range<T> R>
1196	33x	void insert_range(R&& rg)
1197		{
1198	33x	range_insert_impl(
1199		std::ranges::begin(rg), std::ranges::end(rg),
1200	236x	[this] (T* p, auto it) { allocator_construct(al(), p, *it); });
1201	18x	}
1202		#endif
1203
1204		template<
1205		typename InputIterator,
1206		typename = hub_detail::enable_if_is_input_iterator_t<InputIterator>
1207		>
1208	219091x	void insert(InputIterator first, InputIterator last)
1209		{
1210	219091x	range_insert_impl(first, last, [this] (T* p, InputIterator it) {
1211		allocator_construct(al(), p, *it);
1212		});
1213	219016x	}
1214
1215	48x	void insert(size_type n, const T& x)
1216		{
1217	48x	range_insert_impl(size_type(0), n, [&, this] (T* p, size_type) {
1218	945x	allocator_construct(al(), p, x);
1219		});
1220	33x	}
1221
1222		BOOST_FORCEINLINE iterator erase(const_iterator pos)
1223		{
1224	2037x	auto pbb = pos.pbb;
1225	4317x	auto n = pos.n;
1226		++pos;
1227	760x	erase_impl(pbb, n);
1228	5077x	return {pos.pbb, pos.n};
1229		}
1230
1231		BOOST_FORCEINLINE void erase_void(const_iterator pos)
1232		{
1233		erase_impl(pos.pbb, pos.n);
1234		}
1235
1236	1257x	iterator erase(const_iterator first, const_iterator last)
1237		{
1238	4161x	for(auto pbb = first.pbb; first != last; ) {
1239	3213x	first = erase(first);
1240	3213x	if(first.pbb != pbb) break;
1241		}
1242	1257x	auto pbb = first.pbb;
1243	1468x	if(pbb != last.pbb) {
1244		do {
1245	61x	auto pb = static_cast_block_pointer(pbb);
1246	61x	pbb = pb->next;
1247	61x	BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb, block);
1248	61x	size_ -= destroy_all_in_nonempty_block(pb);
1249	6x	blist.unlink(pb);
1250	63x	if(BOOST_LIKELY(pb->mask != full)) blist.unlink_available(pb);
1251	67x	blist.link_available_at_back(pb);
1252	61x	pb->mask = 0;
1253	67x	} while(pbb != last.pbb);
1254	19x	first = {pbb};
1255		}
1256	1267x	while(first != last) first = erase(first);
1257	1468x	return {last.pbb, last.n};
1258		}
1259
1260	21x	void swap(hub& x)
1261		noexcept(
1262		allocator_propagate_on_container_swap_t<Allocator>::value \|\|
1263		allocator_is_always_equal_t<Allocator>::value)
1264		{
1265		using pocs = allocator_propagate_on_container_swap_t<Allocator>;
1266
1267	21x	hub_detail::if_constexpr(pocs{}, [&, this]{
1268		hub_detail::swap_if(pocs{}, al(), x.al());
1269		},
1270		[&, this]{ /* else */
1271		BOOST_ASSERT(al() == x.al());
1272		(void)this;
1273		});
1274	21x	std::swap(blist, x.blist);
1275	21x	std::swap(num_blocks, x.num_blocks);
1276	21x	std::swap(size_, x.size_);
1277	21x	}
1278
1279	16x	void clear() noexcept { erase(begin(), end()); }
1280
1281	12x	void splice(hub& x)
1282		{
1283	12x	BOOST_ASSERT(this != &x);
1284	20x	BOOST_ASSERT(al() == x.al());
1285	90x	for(auto pbb = x.blist.header()->next; pbb != x.blist.header(); ) {
1286	60x	auto pb = static_cast_block_pointer(pbb);
1287	60x	pbb = pbb->next;
1288	60x	if(pb->mask != full) {
1289	18x	x.blist.unlink_available(pb);
1290	21x	blist.link_available_at_front(pb);
1291		}
1292	12x	x.blist.unlink(pb);
1293	60x	blist.link_at_back(pb);
1294	60x	--x.num_blocks;
1295	60x	++num_blocks;
1296	60x	auto s = core::popcount(pb->mask);
1297	60x	x.size_ -= (size_type)s;
1298	60x	size_ += (size_type)s;
1299		}
1300	12x	}
1301
1302	6x	void splice(hub&& x) { splice(x); }
1303
1304		template<typename BinaryPredicate = std::equal_to<T>>
1305	6x	size_type unique(BinaryPredicate pred = BinaryPredicate())
1306		{
1307	6x	auto s = size_;
1308	1206x	for(auto first = cbegin(), last = cend(); first != last; ) {
1309	1200x	auto next = std::next(first);
1310	1200x	first = erase(
1311		next,
1312		std::find_if_not(next, last, [&] (const T& x) {
1313		return pred(x, *first);
1314		}));
1315		}
1316	6x	return (size_type)(s - size_);
1317		}
1318
1319		#if defined(BOOST_MSVC)
1320		#pragma warning(push)
1321		#pragma warning(disable:4127) /* conditional expression is constant */
1322		#endif
1323
1324		template<typename Compare = std::less<T>>
1325	57x	void sort(Compare comp = Compare())
1326		{
1327		/* transfer_sort is usually the fastest, but it consumes the most
1328		* auxiliary memory when sizeof(T) > sizeof(sort_proxy), so we restrict
1329		* its usage to the case sizeof(T) <= sizeof(sort_proxy).
1330		* compact_sort uses the least amount of auxiliary memory (by far), and
1331		* it's also faster than proxy_sort when the auxiliary memory of the latter
1332		* exceeds some threshold seemingly related to the size of the L2 cache;
1333		* we conventionally set the threshold to 2MB for lack of a more precise
1334		* estimation mechanism.
1335		* TODO: In 32-bit mode, the threshold policy is not so clear-cut and the
1336		* cost of moving elements around seems to play a role.
1337		*/
1338		BOOST_IF_CONSTEXPR(sizeof(T) <= sizeof(sort_proxy)) {
1339	33x	if(transfer_sort(comp)) return;
1340		}
1341		else{
1342		static constexpr std::size_t memory_threshold = 2 * 1024 * 1024;
1343	24x	if((std::size_t)size_ * sizeof(sort_proxy) <= memory_threshold) {
1344	13x	if(proxy_sort(comp)) return;
1345		}
1346		}
1347	11x	compact_sort(comp);
1348		}
1349
1350		#if defined(BOOST_MSVC)
1351		#pragma warning(pop) /* C4127 */
1352		#endif
1353
1354	1600x	iterator get_iterator(const_pointer p)
1355		{
1356		std::less<const T*> less;
1357	4992x	for(auto pbb = blist.next; pbb != blist.header(); pbb = pbb-> next) {
1358	3328x	auto pb = static_cast_block_pointer(pbb);
1359	6272x	if(!less(boost::to_address(p), boost::to_address(pb->data())) &&
1360	4608x	less(boost::to_address(p), boost::to_address(pb->data() + N))) {
1361	2000x	int n = (int)(p - pb->data());
1362	1600x	BOOST_ASSERT_MSG(
1363		(pb->mask & ((mask_type)(1) << n)) != 0,
1364		"p points to an invalid element");
1365	1600x	return {pb, n};
1366		}
1367		}
1368	✗	BOOST_ASSERT_MSG(false, "p does not point into the extents of *this");
1369		#if defined(BOOST_ASSERT_HANDLER_IS_NORETURN)
1370		BOOST_UNREACHABLE_RETURN(end());
1371		#else
1372		return end();
1373		#endif
1374		}
1375
1376	800x	const_iterator get_iterator(const_pointer p) const
1377		{
1378	800x	return const_cast<hub*>(this)->get_iterator(p);
1379		}
1380
1381		private:
1382		template<typename U, typename A, typename P>
1383		friend typename hub<U, A>::size_type erase_if(hub<U, A>&, P);
1384
1385		using block_typedefs = hub_detail::block_typedefs<Allocator>;
1386		using block_base = typename block_typedefs::block_base;
1387		using block_base_pointer = typename block_typedefs::block_base_pointer;
1388		using const_block_base_pointer =
1389		typename block_typedefs::const_block_base_pointer;
1390		using block = typename block_typedefs::block;
1391		using block_pointer = typename block_typedefs::block_pointer;
1392		using block_allocator = typename block_typedefs::block_allocator;
1393		using block_list = typename block_typedefs::block_list;
1394		using allocator_base = empty_value<block_allocator, 0>;
1395		using mask_type = typename block_base::mask_type;
1396
1397		static constexpr int N = block_base::N;
1398		static constexpr mask_type full = block_base::full;
1399
1400	22271480x	block_allocator& al() noexcept { return allocator_base::get(); }
1401	374x	const block_allocator& al() const noexcept { return allocator_base::get(); }
1402
1403		struct reset_on_exit
1404		{
1405	32x	~reset_on_exit() { x.reset(); }
1406
1407		hub& x;
1408		};
1409
1410	26x	hub(
1411		hub&& x, const Allocator& al_, std::true_type /* equal allocs */) noexcept:
1412	26x	allocator_base{empty_init, al_}, blist{std::move(x.blist)},
1413	26x	num_blocks{x.num_blocks}, size_{x.size_}
1414		{
1415	26x	x.num_blocks = 0;
1416	26x	x.size_ = 0;
1417	26x	}
1418
1419	24x	hub(
1420		hub&& x, const Allocator& al_, std::false_type /* maybe unequal allocs */):
1421	24x	hub{al_}
1422		{
1423	24x	if(al() == x.al()) {
1424	2x	blist = std::move(x.blist);
1425	2x	num_blocks = x.num_blocks;
1426	2x	size_ = x.size_;
1427	2x	x.num_blocks = 0;
1428	2x	x.size_ = 0;
1429		}
1430		else {
1431	22x	reset_on_exit on_exit{x}; (void)on_exit;
1432	22x	range_insert_impl(x.begin(), x.end(), [this] (T* p, iterator it) {
1433		allocator_construct(al(), p, std::move(*it));
1434		});
1435	22x	}
1436	24x	}
1437
1438	17x	void move_assign(hub& x, std::true_type /* transfer structure */)
1439		{
1440		using pocma =
1441		allocator_propagate_on_container_move_assignment_t<Allocator>;
1442
1443	17x	reset();
1444	17x	hub_detail::move_assign_if(pocma{}, al(), x.al());
1445	17x	blist = std::move(x.blist);
1446	17x	num_blocks = x.num_blocks;
1447	17x	size_ = x.size_;
1448	17x	x.num_blocks = 0;
1449	17x	x.size_ = 0;
1450	17x	}
1451
1452	16x	void move_assign(hub& x, std::false_type /* maybe move data */)
1453		{
1454	16x	if(al() == x.al()) {
1455	6x	move_assign(x, std::true_type{});
1456		}
1457		else {
1458	10x	reset_on_exit on_exit{x}; (void)on_exit;
1459	10x	range_assign_impl(
1460		x.begin(), x.end(),
1461	4585x	[this] (T* p, iterator it)
1462	2294x	{ allocator_construct(al(), p, std::move(*it)); },
1463	400x	[] (T* p, iterator it)
1464	200x	{ p = std::move(it); });
1465	10x	}
1466	7x	}
1467
1468		static block_pointer
1469	15551045x	static_cast_block_pointer(block_base_pointer pbb) noexcept
1470		{
1471	15551045x	return block::static_cast_block_pointer(pbb);
1472		}
1473
1474	169703x	block_pointer create_new_available_block()
1475		{
1476	169703x	auto pb = allocator_allocate(al(), 1);
1477	169608x	pb->mask = 0;
1478		BOOST_TRY {
1479	169608x	allocator_rebind_t<Allocator, value_type> val(al());
1480	169830x	pb->data_ = allocator_allocate(val, N);
1481		}
1482	190x	BOOST_CATCH(...) {
1483	95x	allocator_deallocate(al(), pb, 1);
1484	95x	BOOST_RETHROW;
1485		}
1486		BOOST_CATCH_END
1487	169513x	blist.link_available_at_back(pb);
1488	169513x	++num_blocks;
1489	169513x	return pb;
1490		}
1491
1492	169513x	void delete_block(block_pointer pb) noexcept
1493		{
1494	169513x	allocator_rebind_t<Allocator, value_type> val(al());
1495	169513x	allocator_deallocate(val, pb->data(), N);
1496	169513x	allocator_deallocate(al(), pb, 1);
1497	169513x	}
1498
1499		BOOST_FORCEINLINE block_pointer retrieve_available_block(int& n)
1500		{
1501	10163922x	if(BOOST_LIKELY(blist.next_available != blist.header())) {
1502	9994329x	auto pb = static_cast_block_pointer(blist.next_available);
1503	9993919x	n = hub_detail::unchecked_countr_one(pb->mask);
1504	9993509x	return pb;
1505		}
1506		else {
1507	169427x	n = 0;
1508	169427x	return create_new_available_block();
1509		}
1510		}
1511
1512	59563x	size_type destroy_all_in_nonempty_block(block_pointer pb) noexcept
1513		{
1514	59563x	BOOST_ASSERT(pb->mask != 0);
1515	59639x	return destroy_all_in_nonempty_block(pb, std::integral_constant<bool,
1516		std::is_trivially_destructible<T>::value &&
1517		( hub_detail::is_std_allocator<block_allocator>::value \|\|
1518		hub_detail::is_std_pmr_polymorphic_allocator<block_allocator>::value \|\|
1519	59563x	!hub_detail::allocator_has_destroy<block_allocator, T*>::value )>{});
1520		}
1521
1522	59197x	size_type destroy_all_in_nonempty_block(
1523		block_pointer pb, std::true_type /* trivial destruction */) noexcept
1524		{
1525	59197x	return (size_type)core::popcount(pb->mask);
1526		}
1527
1528	366x	size_type destroy_all_in_nonempty_block(
1529		block_pointer pb, std::false_type /* use allocator_destroy */) noexcept
1530		{
1531	366x	size_type s = 0;
1532	366x	auto mask = pb->mask;
1533		do {
1534	9295x	auto n = hub_detail::unchecked_countr_zero(mask);
1535	9295x	allocator_destroy(al(), boost::to_address(pb->data() + n));
1536	9295x	++s;
1537	9295x	mask &= mask - 1;
1538	9295x	} while(mask);
1539	366x	return s;
1540		}
1541
1542	69808x	size_type destroy_all_in_full_block(block_pointer pb) noexcept
1543		{
1544	69808x	BOOST_ASSERT(pb->mask == full);
1545	4537520x	for(int n = 0; n < N; ++n) {
1546	4479104x	allocator_destroy(al(), boost::to_address(pb->data() + n));
1547		}
1548	69808x	return (size_type)N;
1549		}
1550
1551	604x	void reset() noexcept
1552		{
1553	100222x	for(auto pbb = blist.next_available; pbb != blist.header(); ) {
1554	99417x	auto pb = static_cast_block_pointer(pbb);
1555	99417x	pbb = pb->next_available;
1556		BOOST_IF_CONSTEXPR(!std::is_trivially_destructible<T>::value) {
1557	40205x	BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb, block);
1558		}
1559	99417x	if(pb->mask != 0) {
1560	59502x	destroy_all_in_nonempty_block(pb);
1561	70x	blist.unlink(pb);
1562		}
1563	99417x	delete_block(pb);
1564		}
1565		/* full blocks remaining */
1566	70623x	for(auto pbb = blist.next; pbb != blist.header(); ) {
1567	69808x	BOOST_ASSERT(pbb->mask == full);
1568	69808x	auto pb = static_cast_block_pointer(pbb);
1569	69808x	pbb = pb->next;
1570		BOOST_IF_CONSTEXPR(!std::is_trivially_destructible<T>::value) {
1571	50515x	BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb, block);
1572		}
1573	69808x	destroy_all_in_full_block(pb);
1574	69808x	delete_block(pb);
1575		}
1576	604x	blist.reset();
1577	604x	num_blocks = 0;
1578	604x	size_ = 0;
1579	604x	}
1580
1581		template<typename... Args>
1582	9935843x	inline void construct_or_restore_capacity(
1583		value_type* p, block_base_pointer pbb, Args&&... args)
1584		{
1585		BOOST_TRY {
1586	9935843x	allocator_construct(al(), p, std::forward<Args>(args)...);
1587		}
1588	48x	BOOST_CATCH(...) {
1589	24x	auto pb = static_cast_block_pointer(blist.next_available);
1590	24x	if(pb != pbb) { /* block freshly allocated -> restore capacity */
1591	6x	blist.unlink_available(pb);
1592	6x	delete_block(pb);
1593	6x	--num_blocks;
1594		}
1595	24x	BOOST_RETHROW
1596		}
1597		BOOST_CATCH_END
1598	9935819x	}
1599
1600		BOOST_FORCEINLINE void erase_impl(block_base_pointer pbb, int n) noexcept
1601		{
1602	5121149x	auto pb = static_cast_block_pointer(pbb);
1603	5122871x	allocator_destroy(al(), boost::to_address(pb->data() + n));
1604	5121178x	if(BOOST_UNLIKELY(pb->mask == full)) blist.link_available_at_front(pb);
1605	5118566x	pb->mask &= ~((mask_type)(1) << n);
1606	5121149x	if(BOOST_UNLIKELY(pb->mask == 0)) {
1607	8x	blist.unlink(pb);
1608	36x	blist.unlink_available(pb);
1609	44x	blist.link_available_at_back(pb);
1610		}
1611	5121149x	--size_;
1612	5121149x	}
1613
1614		template<typename Incrementable, typename Sentinel, typename Construct>
1615	219322x	void range_insert_impl(
1616		Incrementable first, Sentinel last, Construct construct_)
1617		{
1618	232934x	while(first != last) {
1619		int n;
1620	227154x	auto pb = retrieve_available_block(n);
1621		for(; ; ) {
1622	891380x	construct_(boost::to_address(pb->data() + n), first++);
1623	875760x	++size_;
1624	875925x	if(BOOST_UNLIKELY(pb->mask == 0)) blist.link_at_back(pb);
1625	883541x	pb->mask \|= pb->mask +1;
1626	875760x	if(pb->mask == full) {
1627	13612x	blist.unlink_available(pb);
1628	13612x	break;
1629		}
1630	862148x	else if(first == last) return;
1631	648497x	n = hub_detail::unchecked_countr_one(pb->mask);
1632		}
1633		}
1634		}
1635
1636		template<
1637		typename Incrementable, typename Sentinel,
1638		typename Construct, typename Insert
1639		>
1640	125x	void range_assign_impl(
1641		Incrementable first, Sentinel last, Construct construct_, Insert insert_)
1642		{
1643	125x	auto pbb = blist.next;
1644	125x	int n = -1;
1645	125x	if(first != last) {
1646		/* consume active blocks */
1647	268x	for(; pbb != blist.header(); pbb = pbb->next) {
1648	144x	auto pb = static_cast_block_pointer(pbb);
1649	144x	n = 0;
1650	8536x	for(mask_type bit = 1; bit; bit <<= 1, ++n) {
1651	8408x	if(pb->mask & bit) { /* full slot */
1652	8100x	insert_(boost::to_address(pb->data() + n), first++);
1653		}
1654		else { /* empty slot */
1655	950x	construct_(boost::to_address(pb->data() + n), first++);
1656	745x	++size_;
1657	745x	pb->mask \|= bit;
1658	748x	if(pb->mask == full) blist.unlink_available(pb);
1659		}
1660	8399x	if(first == last) goto exit;
1661		}
1662		}
1663	112x	exit: ;
1664		}
1665	116x	if(first != last) {
1666		/* all active blocks consumed, keep inserting */
1667	105x	range_insert_impl(first, last, construct_);
1668		}
1669		else{
1670		/* erase remaining original elements */
1671	20x	auto it = (n == -1)? const_iterator{pbb}: ++const_iterator{pbb, n};
1672	11x	erase(it, cend());
1673		}
1674	50x	}
1675
1676		template<typename Compare>
1677	34x	bool transfer_sort(Compare comp)
1678		{
1679		/* transfer to a buffer, sort and transfer back */
1680	34x	if(size_ > 1) {
1681	53x	hub_detail::buffer<T,Allocator> buf(size_, al());
1682	31x	if(!buf.data) return false;
1683
1684	31x	container::for_each(*this, [&] (value_type& x) {
1685	446x	buf.emplace_back(std::move(x));
1686		});
1687	28x	std::sort(buf.begin(), buf.end(), comp);
1688	28x	container::for_each(*this, [&] (value_type& x) {
1689	16x	x = std::move(*buf.begin());
1690	16x	buf.erase_front();
1691		});
1692	31x	}
1693	31x	return true;
1694		}
1695
1696		struct sort_proxy
1697		{
1698		T* p;
1699		size_type n;
1700		};
1701
1702		template<typename Compare>
1703	13x	bool proxy_sort(Compare comp)
1704		{
1705		/* sort an array of (pointer, index) pairs and relocate according to it */
1706	13x	if(size_ > 1) {
1707	11x	hub_detail::nodtor_unique_ptr<sort_proxy[]> p
1708		{static_cast<sort_proxy*>(
1709	11x	::operator new[](size_ * sizeof(sort_proxy), std::nothrow))};
1710	11x	if(!p) return false;
1711
1712	11x	size_type i = 0;
1713	11x	container::for_each(*this, [&] (value_type& x) {
1714	862x	p[i] = {std::addressof(x), i};
1715	862x	++i;
1716		});
1717
1718	11x	std::sort(
1719	11x	p.get(), p.get() + size_,
1720	7000x	[&] (const sort_proxy& x, const sort_proxy& y) {
1721	7000x	return comp(const_cast<const T&>(x.p), const_cast<const T&>(y.p));
1722		});
1723
1724	11x	i = 0;
1725	7892x	for(; i < size_; ++i) {
1726	7884x	if(p[i].n != i) {
1727	56x	T x = std::move(*(p[i].p));
1728	53x	auto j = i;
1729		do {
1730	7819x	auto k = p[j].n;
1731	7819x	(p[j].p) = std::move(p[k].p);
1732	7819x	p[j].n = j;
1733	7819x	j = k;
1734	7819x	} while(p[j].n != i);
1735	53x	*(p[j].p) = std::move(x);
1736	53x	p[j].n = j;
1737	53x	}
1738		}
1739	11x	}
1740	10x	return true;
1741		}
1742
1743		template<typename Compare>
1744	11x	void compact_sort(Compare comp)
1745		{
1746		/* compact elements and build an array of pointers to data chunks of N */
1747		using sort_iterator = hub_detail::sort_iterator<T, (std::size_t)N>;
1748
1749	11x	if(size_ > 1) {
1750	11x	std::size_t n = (std::size_t)((size_ + N - 1) / N);
1751	11x	hub_detail::nodtor_unique_ptr<T*[]> p
1752	11x	{static_cast<T*>(::operator new[](n sizeof(T*)))};
1753	11x	std::size_t i = 0;
1754	11x	compact([&] (block_pointer pb) {
1755	✗	p[i++] = boost::to_address(pb->data());
1756		});
1757	11x	BOOST_ASSERT(i == n);
1758
1759	22x	std::sort(
1760		sort_iterator{p.get(), 0},
1761	11x	sort_iterator{p.get(), (std::ptrdiff_t)size_}, comp);
1762	11x	}
1763	8x	}
1764
1765	76x	void compact() { compact([] (block_pointer) {}); }
1766
1767		template<typename Track>
1768	35x	void compact(Track track)
1769		{
1770	41403x	for(auto pbbx = blist.next; pbbx != blist.header(); ) {
1771	41385x	auto pbx = static_cast_block_pointer(pbbx);
1772	41385x	auto pbby = pbbx->next;
1773	41385x	if(pbx->mask != full) {
1774		do{
1775	57747x	if(pbby->mask == full) {
1776		do {
1777	8470x	track(static_cast_block_pointer(pbby));
1778	8470x	pbby = pbby->next;
1779	8470x	} while(pbby->mask == full);
1780	✗	blist.unlink(pbx);
1781	14x	blist.link_before(pbx, static_cast_block_pointer(pbby));
1782		}
1783	57750x	if(pbby == blist.header()) {
1784	25x	compact(pbx);
1785	25x	track(pbx);
1786	25x	return;
1787		}
1788		else{
1789	57722x	auto pby = static_cast_block_pointer(pbby);
1790	57722x	compact(pbx,pby);
1791	57722x	if(pby->mask == 0) {
1792	39842x	pbby = pby->next;
1793	1x	blist.unlink(pby);
1794	39842x	blist.unlink_available(pby);
1795	39843x	blist.link_available_at_back(pby);
1796		}
1797		}
1798	57722x	}while(pbx->mask != full);
1799	18779x	blist.unlink_available(pbx);
1800		}
1801	41360x	track(pbx);
1802	41356x	pbbx = pbby;
1803		}
1804		}
1805
1806	57722x	void compact(block_pointer pbx, block_pointer pby)
1807		{
1808	57722x	auto cx = core::popcount(pbx->mask),
1809	57722x	cy = core::popcount(pby->mask);
1810	57722x	if(cx < cy) {
1811	17940x	std::swap(cx, cy);
1812	17940x	swap_payload(pbx, pby);
1813		}
1814	57722x	auto c = (std::min)(N - cx, cy);
1815	648664x	while(c--) {
1816	590942x	auto n = hub_detail::unchecked_countr_one(pbx->mask);
1817	590942x	auto m = N - 1 - hub_detail::unchecked_countl_zero(pby->mask);
1818	591038x	allocator_construct(
1819	591006x	al(), boost::to_address(pbx->data() + n), std::move(pby->data()[m]));
1820	591006x	allocator_destroy(al(), boost::to_address(pby->data() + m));
1821	590974x	pbx->mask \|= pbx->mask + 1;
1822	590942x	pby->mask &= ~((mask_type)(1) << m);
1823		}
1824	57722x	}
1825
1826	25x	void compact(block_pointer pb)
1827		{
1828	132x	for(; ; ) {
1829	157x	auto n = hub_detail::unchecked_countr_one(pb->mask);
1830	157x	auto m = N - 1 - hub_detail::unchecked_countl_zero(pb->mask);
1831	157x	if(n > m) return;
1832	228x	allocator_construct(
1833	196x	al(), boost::to_address(pb->data() + n), std::move(pb->data()[m]));
1834	196x	allocator_destroy(al(), boost::to_address(pb->data() + m));
1835	164x	pb->mask \|= pb->mask + 1;
1836	132x	pb->mask &= ~((mask_type)(1) << m);
1837		}
1838		}
1839
1840		block_list blist;
1841		size_type num_blocks = 0;
1842		size_type size_ = 0;
1843		};
1844
1845		#if !defined(BOOST_NO_CXX17_DEDUCTION_GUIDES)
1846		template<
1847		typename InputIterator,
1848		typename Allocator = std::allocator<
1849		typename std::iterator_traits<InputIterator>::value_type>
1850		>
1851		hub(InputIterator, InputIterator, Allocator = Allocator())
1852		-> hub<
1853		typename std::iterator_traits<InputIterator>::value_type, Allocator>;
1854
1855		#if !defined(BOOST_CONTAINER_HUB_NO_RANGES)
1856		template<
1857		std::ranges::input_range R,
1858		typename Allocator = std::allocator<std::ranges::range_value_t<R>>
1859		>
1860		hub(from_range_t, R&&, Allocator = Allocator())
1861		-> hub<std::ranges::range_value_t<R>, Allocator>;
1862		#endif
1863		#endif
1864
1865		template<typename T, typename Allocator>
1866	8x	void swap(hub<T, Allocator>& x, hub<T, Allocator>& y)
1867		noexcept(noexcept(x.swap(y)))
1868		{
1869	8x	x.swap(y);
1870	8x	}
1871
1872		template<typename T, typename Allocator, typename U = T>
1873		typename hub<T, Allocator>::size_type
1874	8x	erase(hub<T, Allocator>& x, const U& value)
1875		{
1876	8x	return container::erase_if(
1877	8x	x, [&](const T& v) -> bool { return v == value; });
1878		}
1879
1880		template<typename T, typename Allocator, typename Predicate>
1881		typename hub<T, Allocator>::size_type
1882	54x	erase_if(hub<T, Allocator>& x, Predicate pred)
1883		{
1884		using hub_container = hub<T, Allocator>;
1885		using size_type = typename hub_container::size_type;
1886		using block = typename hub_container::block;
1887
1888	54x	auto s = x.size_;
1889	155332x	for(auto pbb = x.blist.next; pbb != x.blist.header(); ) {
1890	155262x	auto pb = x.static_cast_block_pointer(pbb);
1891	155262x	pbb = pb->next;
1892	155262x	BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb, block);
1893	155262x	auto mask = pb->mask;
1894		do {
1895	9935010x	auto n = hub_detail::unchecked_countr_zero(mask);
1896	9935510x	if(pred(pb->data()[n])) x.erase_impl(pb, n);
1897	9935010x	mask &= mask - 1;
1898	9935010x	} while(mask);
1899		}
1900	54x	return (size_type)(s - x.size_);
1901		}
1902
1903		template<typename ValuePtr, typename F>
1904	758x	F for_each(
1905		hub_detail::iterator<ValuePtr> first, hub_detail::iterator<ValuePtr> last,
1906		F f)
1907		{
1908		using reference = typename hub_detail::iterator<ValuePtr>::reference;
1909
1910	758x	container::for_each_while(
1911		first, last, [&] (reference x) { f(x); return true; });
1912	755x	return f;
1913		}
1914
1915		template<typename T, typename Allocator, typename F>
1916	74x	F for_each(hub<T, Allocator>& x, F f)
1917		{
1918	74x	container::for_each(x.begin(), x.end(), std::ref(f));
1919	71x	return f;
1920		}
1921
1922		template<typename T, typename Allocator, typename F>
1923	4x	F for_each(const hub<T, Allocator>& x, F f)
1924		{
1925	4x	container::for_each(x.begin(), x.end(), std::ref(f));
1926	4x	return f;
1927		}
1928
1929		template<typename ValuePtr, typename F>
1930	2142x	std::pair<hub_detail::iterator<ValuePtr>, F> for_each_while(
1931		hub_detail::iterator<ValuePtr> first, hub_detail::iterator<ValuePtr> last,
1932		F f)
1933		{
1934	57003x	for(auto pbb = first.pbb; first != last; ) {
1935	56297x	if(!f(*first)) return {first, std::move(f)};
1936		++first;
1937	69225x	if(first.pbb != pbb) break;
1938		}
1939	2112x	if(first.pbb != last.pbb) {
1940	1438x	first = hub_detail::for_each_while_core<hub_detail::iterator<ValuePtr>>(
1941	696x	first.pbb, last.pbb, f);
1942	1785x	if(first.pbb != last.pbb) return {first, std::move(f)};
1943		}
1944	12819x	for(; first != last; ++first) if(!f(*first)) return {first, std::move(f)};
1945	771x	return {first, std::move(f)};
1946		}
1947
1948		template<typename T, typename Allocator, typename F>
1949		std::pair<typename hub<T, Allocator>::iterator, F>
1950	4x	for_each_while(hub<T, Allocator>& x, F f)
1951		{
1952		return {
1953	8x	container::for_each_while(x.begin(), x.end(), std::ref(f)).first,
1954	8x	std::move(f)};
1955		}
1956
1957		template<typename T, typename Allocator, typename F>
1958		std::pair<typename hub<T, Allocator>::const_iterator, F>
1959	4x	for_each_while(const hub<T, Allocator>& x, F f)
1960		{
1961		return {
1962	8x	container::for_each_while(x.begin(), x.end(), std::ref(f)).first,
1963	8x	std::move(f)};
1964		}
1965
1966		} /* namespace container */
1967
1968		} /* namespace boost */
1969
1970		#if defined(BOOST_MSVC)
1971		#pragma warning(pop) /* C4714 */
1972		#endif
1973
1974		#endif
1975