1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516 |
- #ifndef BOOST_INTRUSIVE_LIST_HPP
- #define BOOST_INTRUSIVE_LIST_HPP
- #include <boost/intrusive/detail/config_begin.hpp>
- #include <boost/intrusive/intrusive_fwd.hpp>
- #include <boost/intrusive/detail/assert.hpp>
- #include <boost/intrusive/list_hook.hpp>
- #include <boost/intrusive/circular_list_algorithms.hpp>
- #include <boost/intrusive/pointer_traits.hpp>
- #include <boost/intrusive/detail/mpl.hpp>
- #include <boost/intrusive/link_mode.hpp>
- #include <boost/intrusive/detail/get_value_traits.hpp>
- #include <boost/intrusive/detail/is_stateful_value_traits.hpp>
- #include <boost/intrusive/detail/default_header_holder.hpp>
- #include <boost/intrusive/detail/reverse_iterator.hpp>
- #include <boost/intrusive/detail/uncast.hpp>
- #include <boost/intrusive/detail/list_iterator.hpp>
- #include <boost/intrusive/detail/array_initializer.hpp>
- #include <boost/intrusive/detail/exception_disposer.hpp>
- #include <boost/intrusive/detail/equal_to_value.hpp>
- #include <boost/intrusive/detail/key_nodeptr_comp.hpp>
- #include <boost/intrusive/detail/simple_disposers.hpp>
- #include <boost/intrusive/detail/size_holder.hpp>
- #include <boost/intrusive/detail/algorithm.hpp>
- #include <boost/move/utility_core.hpp>
- #include <boost/static_assert.hpp>
- #include <boost/intrusive/detail/value_functors.hpp>
- #include <cstddef> //std::size_t, etc.
- #if defined(BOOST_HAS_PRAGMA_ONCE)
- # pragma once
- #endif
- namespace boost {
- namespace intrusive {
- struct default_list_hook_applier
- { template <class T> struct apply{ typedef typename T::default_list_hook type; }; };
- template<>
- struct is_default_hook_tag<default_list_hook_applier>
- { static const bool value = true; };
- struct list_defaults
- {
- typedef default_list_hook_applier proto_value_traits;
- static const bool constant_time_size = true;
- typedef std::size_t size_type;
- typedef void header_holder_type;
- };
- #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
- template<class T, class ...Options>
- #else
- template <class ValueTraits, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
- #endif
- class list_impl
- {
-
- public:
- typedef ValueTraits value_traits;
- typedef typename value_traits::pointer pointer;
- typedef typename value_traits::const_pointer const_pointer;
- typedef typename pointer_traits<pointer>::element_type value_type;
- typedef typename pointer_traits<pointer>::reference reference;
- typedef typename pointer_traits<const_pointer>::reference const_reference;
- typedef typename pointer_traits<pointer>::difference_type difference_type;
- typedef SizeType size_type;
- typedef list_iterator<value_traits, false> iterator;
- typedef list_iterator<value_traits, true> const_iterator;
- typedef boost::intrusive::reverse_iterator<iterator> reverse_iterator;
- typedef boost::intrusive::reverse_iterator<const_iterator> const_reverse_iterator;
- typedef typename value_traits::node_traits node_traits;
- typedef typename node_traits::node node;
- typedef typename node_traits::node_ptr node_ptr;
- typedef typename node_traits::const_node_ptr const_node_ptr;
- typedef circular_list_algorithms<node_traits> node_algorithms;
- typedef typename detail::get_header_holder_type
- < value_traits, HeaderHolder >::type header_holder_type;
- static const bool constant_time_size = ConstantTimeSize;
- static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value;
- static const bool has_container_from_iterator =
- detail::is_same< header_holder_type, detail::default_header_holder< node_traits > >::value;
-
- private:
- typedef detail::size_holder<constant_time_size, size_type> size_traits;
-
- BOOST_MOVABLE_BUT_NOT_COPYABLE(list_impl)
- static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value;
-
- BOOST_STATIC_ASSERT(!(constant_time_size &&
- ((int)value_traits::link_mode == (int)auto_unlink)
- ));
- node_ptr get_root_node()
- { return data_.root_plus_size_.m_header.get_node(); }
- const_node_ptr get_root_node() const
- { return data_.root_plus_size_.m_header.get_node(); }
- struct root_plus_size : public size_traits
- {
- header_holder_type m_header;
- };
- struct data_t : public value_traits
- {
- typedef typename list_impl::value_traits value_traits;
- explicit data_t(const value_traits &val_traits)
- : value_traits(val_traits)
- {}
- root_plus_size root_plus_size_;
- } data_;
- size_traits &priv_size_traits()
- { return data_.root_plus_size_; }
- const size_traits &priv_size_traits() const
- { return data_.root_plus_size_; }
- const value_traits &priv_value_traits() const
- { return data_; }
- value_traits &priv_value_traits()
- { return data_; }
- typedef typename boost::intrusive::value_traits_pointers
- <ValueTraits>::const_value_traits_ptr const_value_traits_ptr;
- const_value_traits_ptr priv_value_traits_ptr() const
- { return pointer_traits<const_value_traits_ptr>::pointer_to(this->priv_value_traits()); }
-
- public:
-
-
-
-
-
-
- list_impl()
- : data_(value_traits())
- {
- this->priv_size_traits().set_size(size_type(0));
- node_algorithms::init_header(this->get_root_node());
- }
-
-
-
-
-
-
- explicit list_impl(const value_traits &v_traits)
- : data_(v_traits)
- {
- this->priv_size_traits().set_size(size_type(0));
- node_algorithms::init_header(this->get_root_node());
- }
-
-
-
-
-
-
-
-
- template<class Iterator>
- list_impl(Iterator b, Iterator e, const value_traits &v_traits = value_traits())
- : data_(v_traits)
- {
-
- this->priv_size_traits().set_size(size_type(0));
- node_algorithms::init_header(this->get_root_node());
-
- this->insert(this->cend(), b, e);
- }
-
-
-
-
-
-
-
-
-
- list_impl(BOOST_RV_REF(list_impl) x)
- : data_(::boost::move(x.priv_value_traits()))
- {
- this->priv_size_traits().set_size(size_type(0));
- node_algorithms::init_header(this->get_root_node());
-
- this->swap(x);
- }
-
-
- list_impl& operator=(BOOST_RV_REF(list_impl) x)
- { this->swap(x); return *this; }
-
-
-
-
-
-
-
-
-
- ~list_impl()
- {
- if(is_safe_autounlink<ValueTraits::link_mode>::value){
- this->clear();
- node_algorithms::init(this->get_root_node());
- }
- }
-
-
-
-
-
-
-
-
-
-
- void push_back(reference value)
- {
- node_ptr to_insert = priv_value_traits().to_node_ptr(value);
- BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(to_insert));
- node_algorithms::link_before(this->get_root_node(), to_insert);
- this->priv_size_traits().increment();
- }
-
-
-
-
-
-
-
-
-
-
- void push_front(reference value)
- {
- node_ptr to_insert = priv_value_traits().to_node_ptr(value);
- BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(to_insert));
- node_algorithms::link_before(node_traits::get_next(this->get_root_node()), to_insert);
- this->priv_size_traits().increment();
- }
-
-
-
-
-
-
-
-
- void pop_back()
- { return this->pop_back_and_dispose(detail::null_disposer()); }
-
-
-
-
-
-
-
-
-
-
-
- template<class Disposer>
- void pop_back_and_dispose(Disposer disposer)
- {
- node_ptr to_erase = node_traits::get_previous(this->get_root_node());
- node_algorithms::unlink(to_erase);
- this->priv_size_traits().decrement();
- if(safemode_or_autounlink)
- node_algorithms::init(to_erase);
- disposer(priv_value_traits().to_value_ptr(to_erase));
- }
-
-
-
-
-
-
-
-
- void pop_front()
- { return this->pop_front_and_dispose(detail::null_disposer()); }
-
-
-
-
-
-
-
-
-
-
-
- template<class Disposer>
- void pop_front_and_dispose(Disposer disposer)
- {
- node_ptr to_erase = node_traits::get_next(this->get_root_node());
- node_algorithms::unlink(to_erase);
- this->priv_size_traits().decrement();
- if(safemode_or_autounlink)
- node_algorithms::init(to_erase);
- disposer(priv_value_traits().to_value_ptr(to_erase));
- }
-
-
-
-
-
- reference front()
- { return *priv_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); }
-
-
-
-
-
- const_reference front() const
- { return *priv_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); }
-
-
-
-
-
- reference back()
- { return *priv_value_traits().to_value_ptr(node_traits::get_previous(this->get_root_node())); }
-
-
-
-
-
- const_reference back() const
- { return *priv_value_traits().to_value_ptr(detail::uncast(node_traits::get_previous(this->get_root_node()))); }
-
-
-
-
-
- iterator begin()
- { return iterator(node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); }
-
-
-
-
-
- const_iterator begin() const
- { return this->cbegin(); }
-
-
-
-
-
- const_iterator cbegin() const
- { return const_iterator(node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); }
-
-
-
-
-
- iterator end()
- { return iterator(this->get_root_node(), this->priv_value_traits_ptr()); }
-
-
-
-
-
- const_iterator end() const
- { return this->cend(); }
-
-
-
-
-
- const_iterator cend() const
- { return const_iterator(detail::uncast(this->get_root_node()), this->priv_value_traits_ptr()); }
-
-
-
-
-
-
- reverse_iterator rbegin()
- { return reverse_iterator(this->end()); }
-
-
-
-
-
-
- const_reverse_iterator rbegin() const
- { return this->crbegin(); }
-
-
-
-
-
-
- const_reverse_iterator crbegin() const
- { return const_reverse_iterator(end()); }
-
-
-
-
-
-
- reverse_iterator rend()
- { return reverse_iterator(begin()); }
-
-
-
-
-
-
- const_reverse_iterator rend() const
- { return this->crend(); }
-
-
-
-
-
-
- const_reverse_iterator crend() const
- { return const_reverse_iterator(this->begin()); }
-
-
-
-
-
-
-
-
- static list_impl &container_from_end_iterator(iterator end_iterator)
- { return list_impl::priv_container_from_end_iterator(end_iterator); }
-
-
-
-
-
-
-
-
- static const list_impl &container_from_end_iterator(const_iterator end_iterator)
- { return list_impl::priv_container_from_end_iterator(end_iterator); }
-
-
-
-
-
-
-
-
- size_type size() const
- {
- if(constant_time_size)
- return this->priv_size_traits().get_size();
- else
- return node_algorithms::count(this->get_root_node()) - 1;
- }
-
-
-
-
-
-
-
- bool empty() const
- { return node_algorithms::unique(this->get_root_node()); }
-
-
-
-
-
-
-
- void swap(list_impl& other)
- {
- node_algorithms::swap_nodes(this->get_root_node(), other.get_root_node());
- this->priv_size_traits().swap(other.priv_size_traits());
- }
-
-
-
-
-
-
-
-
-
- void shift_backwards(size_type n = 1)
- { node_algorithms::move_forward(this->get_root_node(), n); }
-
-
-
-
-
-
-
-
-
- void shift_forward(size_type n = 1)
- { node_algorithms::move_backwards(this->get_root_node(), n); }
-
-
-
-
-
-
-
-
-
-
-
-
- iterator erase(const_iterator i)
- { return this->erase_and_dispose(i, detail::null_disposer()); }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- iterator erase(const_iterator b, const_iterator e)
- {
- if(safemode_or_autounlink || constant_time_size){
- return this->erase_and_dispose(b, e, detail::null_disposer());
- }
- else{
- node_algorithms::unlink(b.pointed_node(), e.pointed_node());
- return e.unconst();
- }
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- iterator erase(const_iterator b, const_iterator e, size_type n)
- {
- BOOST_INTRUSIVE_INVARIANT_ASSERT(node_algorithms::distance(b.pointed_node(), e.pointed_node()) == n);
- if(safemode_or_autounlink || constant_time_size){
- return this->erase_and_dispose(b, e, detail::null_disposer());
- }
- else{
- if(constant_time_size){
- this->priv_size_traits().decrease(n);
- }
- node_algorithms::unlink(b.pointed_node(), e.pointed_node());
- return e.unconst();
- }
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template <class Disposer>
- iterator erase_and_dispose(const_iterator i, Disposer disposer)
- {
- node_ptr to_erase(i.pointed_node());
- ++i;
- node_algorithms::unlink(to_erase);
- this->priv_size_traits().decrement();
- if(safemode_or_autounlink)
- node_algorithms::init(to_erase);
- disposer(this->priv_value_traits().to_value_ptr(to_erase));
- return i.unconst();
- }
- #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
- template<class Disposer>
- iterator erase_and_dispose(iterator i, Disposer disposer)
- { return this->erase_and_dispose(const_iterator(i), disposer); }
- #endif
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template <class Disposer>
- iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
- {
- node_ptr bp(b.pointed_node()), ep(e.pointed_node());
- node_algorithms::unlink(bp, ep);
- while(bp != ep){
- node_ptr to_erase(bp);
- bp = node_traits::get_next(bp);
- if(safemode_or_autounlink)
- node_algorithms::init(to_erase);
- disposer(priv_value_traits().to_value_ptr(to_erase));
- this->priv_size_traits().decrement();
- }
- return e.unconst();
- }
-
-
-
-
-
-
-
-
-
- void clear()
- {
- if(safemode_or_autounlink){
- this->clear_and_dispose(detail::null_disposer());
- }
- else{
- node_algorithms::init_header(this->get_root_node());
- this->priv_size_traits().set_size(size_type(0));
- }
- }
-
-
-
-
-
-
-
-
-
-
-
- template <class Disposer>
- void clear_and_dispose(Disposer disposer)
- {
- const_iterator it(this->begin()), itend(this->end());
- while(it != itend){
- node_ptr to_erase(it.pointed_node());
- ++it;
- if(safemode_or_autounlink)
- node_algorithms::init(to_erase);
- disposer(priv_value_traits().to_value_ptr(to_erase));
- }
- node_algorithms::init_header(this->get_root_node());
- this->priv_size_traits().set_size(0);
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template <class Cloner, class Disposer>
- void clone_from(const list_impl &src, Cloner cloner, Disposer disposer)
- {
- this->clear_and_dispose(disposer);
- detail::exception_disposer<list_impl, Disposer>
- rollback(*this, disposer);
- const_iterator b(src.begin()), e(src.end());
- for(; b != e; ++b){
- this->push_back(*cloner(*b));
- }
- rollback.release();
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template <class Cloner, class Disposer>
- void clone_from(BOOST_RV_REF(list_impl) src, Cloner cloner, Disposer disposer)
- {
- this->clear_and_dispose(disposer);
- detail::exception_disposer<list_impl, Disposer>
- rollback(*this, disposer);
- iterator b(src.begin()), e(src.end());
- for(; b != e; ++b){
- this->push_back(*cloner(*b));
- }
- rollback.release();
- }
-
-
-
-
-
-
-
-
-
-
-
- iterator insert(const_iterator p, reference value)
- {
- node_ptr to_insert = this->priv_value_traits().to_node_ptr(value);
- BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(to_insert));
- node_algorithms::link_before(p.pointed_node(), to_insert);
- this->priv_size_traits().increment();
- return iterator(to_insert, this->priv_value_traits_ptr());
- }
-
-
-
-
-
-
-
-
-
-
-
- template<class Iterator>
- void insert(const_iterator p, Iterator b, Iterator e)
- {
- for (; b != e; ++b)
- this->insert(p, *b);
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template<class Iterator>
- void assign(Iterator b, Iterator e)
- {
- this->clear();
- this->insert(this->cend(), b, e);
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template<class Iterator, class Disposer>
- void dispose_and_assign(Disposer disposer, Iterator b, Iterator e)
- {
- this->clear_and_dispose(disposer);
- this->insert(this->cend(), b, e);
- }
-
-
-
-
-
-
-
-
-
-
-
- void splice(const_iterator p, list_impl& x)
- {
- if(!x.empty()){
- node_algorithms::transfer
- (p.pointed_node(), x.begin().pointed_node(), x.end().pointed_node());
- size_traits &thist = this->priv_size_traits();
- size_traits &xt = x.priv_size_traits();
- thist.increase(xt.get_size());
- xt.set_size(size_type(0));
- }
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
- void splice(const_iterator p, list_impl&x, const_iterator new_ele)
- {
- node_algorithms::transfer(p.pointed_node(), new_ele.pointed_node());
- x.priv_size_traits().decrement();
- this->priv_size_traits().increment();
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
- void splice(const_iterator p, list_impl&x, const_iterator f, const_iterator e)
- {
- if(constant_time_size)
- this->splice(p, x, f, e, node_algorithms::distance(f.pointed_node(), e.pointed_node()));
- else
- this->splice(p, x, f, e, 1);
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
- void splice(const_iterator p, list_impl&x, const_iterator f, const_iterator e, size_type n)
- {
- if(n){
- if(constant_time_size){
- BOOST_INTRUSIVE_INVARIANT_ASSERT(n == node_algorithms::distance(f.pointed_node(), e.pointed_node()));
- node_algorithms::transfer(p.pointed_node(), f.pointed_node(), e.pointed_node());
- size_traits &thist = this->priv_size_traits();
- size_traits &xt = x.priv_size_traits();
- thist.increase(n);
- xt.decrease(n);
- }
- else{
- node_algorithms::transfer(p.pointed_node(), f.pointed_node(), e.pointed_node());
- }
- }
- }
-
-
-
-
-
-
-
-
-
-
-
- void sort()
- { this->sort(value_less<value_type>()); }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template<class Predicate>
- void sort(Predicate p)
- {
- if(node_traits::get_next(this->get_root_node())
- != node_traits::get_previous(this->get_root_node())){
- list_impl carry(this->priv_value_traits());
- detail::array_initializer<list_impl, 64> counter(this->priv_value_traits());
- int fill = 0;
- while(!this->empty()){
- carry.splice(carry.cbegin(), *this, this->cbegin());
- int i = 0;
- while(i < fill && !counter[i].empty()) {
- counter[i].merge(carry, p);
- carry.swap(counter[i++]);
- }
- carry.swap(counter[i]);
- if(i == fill)
- ++fill;
- }
- for (int i = 1; i < fill; ++i)
- counter[i].merge(counter[i-1], p);
- this->swap(counter[fill-1]);
- }
- }
-
-
-
-
-
-
-
-
-
-
-
- void merge(list_impl& x)
- { this->merge(x, value_less<value_type>()); }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template<class Predicate>
- void merge(list_impl& x, Predicate p)
- {
- const_iterator e(this->cend()), ex(x.cend());
- const_iterator b(this->cbegin());
- while(!x.empty()){
- const_iterator ix(x.cbegin());
- while (b != e && !p(*ix, *b)){
- ++b;
- }
- if(b == e){
-
- this->splice(e, x);
- break;
- }
- else{
- size_type n(0);
- do{
- ++ix; ++n;
- } while(ix != ex && p(*ix, *b));
- this->splice(b, x, x.begin(), ix, n);
- }
- }
- }
-
-
-
-
-
-
-
- void reverse()
- { node_algorithms::reverse(this->get_root_node()); }
-
-
-
-
-
-
-
-
-
- void remove(const_reference value)
- { this->remove_if(value_equal<const_reference>(value)); }
-
-
-
-
-
-
-
-
-
-
-
- template<class Disposer>
- void remove_and_dispose(const_reference value, Disposer disposer)
- { this->remove_and_dispose_if(value_equal<const_reference>(value), disposer); }
-
-
-
-
-
-
-
-
-
- template<class Pred>
- void remove_if(Pred pred)
- {
- const node_ptr root_node = this->get_root_node();
- typename node_algorithms::stable_partition_info info;
- node_algorithms::stable_partition
- (node_traits::get_next(root_node), root_node, detail::key_nodeptr_comp<Pred, value_traits>(pred, &this->priv_value_traits()), info);
-
-
- this->erase( const_iterator(node_traits::get_next(root_node), this->priv_value_traits_ptr())
- , const_iterator(info.beg_2st_partition, this->priv_value_traits_ptr())
- , info.num_1st_partition);
- }
-
-
-
-
-
-
-
-
-
-
-
-
- template<class Pred, class Disposer>
- void remove_and_dispose_if(Pred pred, Disposer disposer)
- {
- const node_ptr root_node = this->get_root_node();
- typename node_algorithms::stable_partition_info info;
- node_algorithms::stable_partition
- (node_traits::get_next(root_node), root_node, detail::key_nodeptr_comp<Pred, value_traits>(pred, &this->priv_value_traits()), info);
-
-
- this->erase_and_dispose( const_iterator(node_traits::get_next(root_node), this->priv_value_traits_ptr())
- , const_iterator(info.beg_2st_partition, this->priv_value_traits_ptr())
- , disposer);
- }
-
-
-
-
-
-
-
-
-
- void unique()
- { this->unique_and_dispose(std::equal_to<value_type>(), detail::null_disposer()); }
-
-
-
-
-
-
-
-
-
-
- template<class BinaryPredicate>
- void unique(BinaryPredicate pred)
- { this->unique_and_dispose(pred, detail::null_disposer()); }
-
-
-
-
-
-
-
-
-
-
-
-
- template<class Disposer>
- void unique_and_dispose(Disposer disposer)
- { this->unique_and_dispose(std::equal_to<value_type>(), disposer); }
-
-
-
-
-
-
-
-
-
-
-
-
- template<class BinaryPredicate, class Disposer>
- void unique_and_dispose(BinaryPredicate pred, Disposer disposer)
- {
- const_iterator itend(this->cend());
- const_iterator cur(this->cbegin());
- if(cur != itend){
- const_iterator after(cur);
- ++after;
- while(after != itend){
- if(pred(*cur, *after)){
- after = this->erase_and_dispose(after, disposer);
- }
- else{
- cur = after;
- ++after;
- }
- }
- }
- }
-
-
-
-
-
-
-
-
-
-
-
- static iterator s_iterator_to(reference value)
- {
- BOOST_STATIC_ASSERT((!stateful_value_traits));
- BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(value_traits::to_node_ptr(value)));
- return iterator(value_traits::to_node_ptr(value), const_value_traits_ptr());
- }
-
-
-
-
-
-
-
-
-
-
-
- static const_iterator s_iterator_to(const_reference value)
- {
- BOOST_STATIC_ASSERT((!stateful_value_traits));
- reference r =*detail::uncast(pointer_traits<const_pointer>::pointer_to(value));
- BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(value_traits::to_node_ptr(r)));
- return const_iterator(value_traits::to_node_ptr(r), const_value_traits_ptr());
- }
-
-
-
-
-
-
-
-
-
- iterator iterator_to(reference value)
- {
- BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(this->priv_value_traits().to_node_ptr(value)));
- return iterator(this->priv_value_traits().to_node_ptr(value), this->priv_value_traits_ptr());
- }
-
-
-
-
-
-
-
-
-
- const_iterator iterator_to(const_reference value) const
- {
- reference r = *detail::uncast(pointer_traits<const_pointer>::pointer_to(value));
- BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(this->priv_value_traits().to_node_ptr(r)));
- return const_iterator(this->priv_value_traits().to_node_ptr(r), this->priv_value_traits_ptr());
- }
-
-
-
-
-
-
- void check() const
- {
- const_node_ptr header_ptr = get_root_node();
-
- BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_next(header_ptr));
- BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_previous(header_ptr));
-
- BOOST_INTRUSIVE_INVARIANT_ASSERT((node_traits::get_next(header_ptr) == header_ptr)
- == (node_traits::get_previous(header_ptr) == header_ptr));
- if (node_traits::get_next(header_ptr) == header_ptr)
- {
- if (constant_time_size)
- BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == 0);
- return;
- }
- size_t node_count = 0;
- const_node_ptr p = header_ptr;
- while (true)
- {
- const_node_ptr next_p = node_traits::get_next(p);
- BOOST_INTRUSIVE_INVARIANT_ASSERT(next_p);
- BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_previous(next_p) == p);
- p = next_p;
- if (p == header_ptr) break;
- ++node_count;
- }
- if (constant_time_size)
- BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == node_count);
- }
- friend bool operator==(const list_impl &x, const list_impl &y)
- {
- if(constant_time_size && x.size() != y.size()){
- return false;
- }
- return ::boost::intrusive::algo_equal(x.cbegin(), x.cend(), y.cbegin(), y.cend());
- }
- friend bool operator!=(const list_impl &x, const list_impl &y)
- { return !(x == y); }
- friend bool operator<(const list_impl &x, const list_impl &y)
- { return ::boost::intrusive::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
- friend bool operator>(const list_impl &x, const list_impl &y)
- { return y < x; }
- friend bool operator<=(const list_impl &x, const list_impl &y)
- { return !(y < x); }
- friend bool operator>=(const list_impl &x, const list_impl &y)
- { return !(x < y); }
- friend void swap(list_impl &x, list_impl &y)
- { x.swap(y); }
-
- private:
- static list_impl &priv_container_from_end_iterator(const const_iterator &end_iterator)
- {
- BOOST_STATIC_ASSERT((has_container_from_iterator));
- node_ptr p = end_iterator.pointed_node();
- header_holder_type* h = header_holder_type::get_holder(p);
- root_plus_size* r = detail::parent_from_member
- < root_plus_size, header_holder_type>(h, &root_plus_size::m_header);
- data_t *d = detail::parent_from_member<data_t, root_plus_size>
- ( r, &data_t::root_plus_size_);
- list_impl *s = detail::parent_from_member<list_impl, data_t>(d, &list_impl::data_);
- return *s;
- }
-
- };
- #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
- template<class T, class ...Options>
- #else
- template<class T, class O1 = void, class O2 = void, class O3 = void, class O4 = void>
- #endif
- struct make_list
- {
-
- typedef typename pack_options
- < list_defaults,
- #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
- O1, O2, O3, O4
- #else
- Options...
- #endif
- >::type packed_options;
- typedef typename detail::get_value_traits
- <T, typename packed_options::proto_value_traits>::type value_traits;
- typedef list_impl
- <
- value_traits,
- typename packed_options::size_type,
- packed_options::constant_time_size,
- typename packed_options::header_holder_type
- > implementation_defined;
-
- typedef implementation_defined type;
- };
- #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
- #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
- template<class T, class O1, class O2, class O3, class O4>
- #else
- template<class T, class ...Options>
- #endif
- class list
- : public make_list<T,
- #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
- O1, O2, O3, O4
- #else
- Options...
- #endif
- >::type
- {
- typedef typename make_list
- <T,
- #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
- O1, O2, O3, O4
- #else
- Options...
- #endif
- >::type Base;
-
- BOOST_STATIC_ASSERT((detail::is_same<typename Base::value_traits::value_type, T>::value));
- BOOST_MOVABLE_BUT_NOT_COPYABLE(list)
- public:
- typedef typename Base::value_traits value_traits;
- typedef typename Base::iterator iterator;
- typedef typename Base::const_iterator const_iterator;
- BOOST_INTRUSIVE_FORCEINLINE list()
- : Base()
- {}
- BOOST_INTRUSIVE_FORCEINLINE explicit list(const value_traits &v_traits)
- : Base(v_traits)
- {}
- template<class Iterator>
- BOOST_INTRUSIVE_FORCEINLINE list(Iterator b, Iterator e, const value_traits &v_traits = value_traits())
- : Base(b, e, v_traits)
- {}
- BOOST_INTRUSIVE_FORCEINLINE list(BOOST_RV_REF(list) x)
- : Base(BOOST_MOVE_BASE(Base, x))
- {}
- BOOST_INTRUSIVE_FORCEINLINE list& operator=(BOOST_RV_REF(list) x)
- { return static_cast<list &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
- template <class Cloner, class Disposer>
- BOOST_INTRUSIVE_FORCEINLINE void clone_from(const list &src, Cloner cloner, Disposer disposer)
- { Base::clone_from(src, cloner, disposer); }
- template <class Cloner, class Disposer>
- BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(list) src, Cloner cloner, Disposer disposer)
- { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); }
- BOOST_INTRUSIVE_FORCEINLINE static list &container_from_end_iterator(iterator end_iterator)
- { return static_cast<list &>(Base::container_from_end_iterator(end_iterator)); }
- BOOST_INTRUSIVE_FORCEINLINE static const list &container_from_end_iterator(const_iterator end_iterator)
- { return static_cast<const list &>(Base::container_from_end_iterator(end_iterator)); }
- };
- #endif
- }
- }
- #include <boost/intrusive/detail/config_end.hpp>
- #endif
|