Boost logo

Boost :

Subject: Re: [boost] [Root Pointer] New Documentation
From: Phil Bouchard (philippeb8_at_[hidden])
Date: 2016-04-11 00:08:57


On 04/10/2016 11:45 PM, Vladimir Batov wrote:
> On 04/11/2016 01:32 PM, Phil Bouchard wrote:
>> On 04/10/2016 11:02 PM, Vladimir Batov wrote:
>>> Phil,
>>>
>>> Unfortunately you test below confirmed my suspicion. Now could you
>>> kindly explain how your library is better than:
>>>
>>> template<typename T>
>>> struct manager
>>> {
>>> T* create(args) { all_.emplace_back(args); return &all_.back(); }
>>> void remove(T*) { ... }
>>>
>>> std::list<T> all_;
>>> };
>>>
>>> T* serves as your node_ptr -- all pointers are valid as long as its
>>> manager instance is around. What am I missing?
>>
>> I am not sure if I understand the analogy correctly
>
> Your library does memory and "node" life-time management. It shares
> node_ptrs around and guarantees them to be valid as long as its main
> root_ptr is around. root_ptr clears all node_ptrs when it is destroyed.
> The class above does the same.
>
>> but I can see that remove() will have to do a linear search in the
>> list, slowing down the performance in general.
>
> Well, we are not discussing the efficiency of my "implementation", are
> we? :-)

You asked how my library is better than yours so I'm scrutinizing all
the details.

> Still, if you insist... How about:
>
> struct sort
> {
> bool operator(T const& p1, T const& p2) { return &p1 < &p2; }
> }
>
> std::set<T, sort> all_;
>
> Now "remove" won't need to do linear search.

It's still O(log(n)) whereas note_ptr is O(1).


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk