Most efficient way to insert an item into sorted stl list container ???

[Bob Langelaan]

Clearly one way to do so is by using the merge member function of the list container class to merge the item into the sorted list. My question is: Is there a more efficient way to do it?

Thanks in advance,
Bob

[Ian Collins]

On 03/12/16 17:25, Bob Langelaan wrote:
> Clearly one way to do so is by using the merge member function of the
> list container class to merge the item into the sorted list. My
> question is: Is there a more efficient way to do it?

The usual way to insert into a set is with set::insert. If you know
where or roughly where, use the overloads with a hint parameter.

--
Ian Collins

[bartekltg]

On 12.03.2016 05:25, Bob Langelaan wrote:
> Clearly one way to do so is by using the merge member function of the
> list container class to merge the item into the sorted list. My
> question is: Is there a more efficient way to do it?
>

You can find the place for the new item manually and
insert it.

list<int> bla{23,465,123,76,77};
bla.sort();

int foo = 76;
int bar = 100;

bla.insert( upper_bound(bla.begin(),bla.end(),foo ),foo );
bla.insert( upper_bound(bla.begin(),bla.end(),bar ),bar );

for (auto it: bla)
cout<<it<<endl;
Results:
23
76
76
77
100
123
465

It can be a bit faster (not much if your compilator has done
good job with merging), but still it is O(n) time!

It this operation is a bottleneck, You should consider
different container better suited for you needs.
Probably std::set, as Ian have said.

best
Bartek

[Bob Langelaan]

Thanks. That is exactly what I was looking for :)

[K. Frank]

Hello Bob!

On Saturday, March 12, 2016 at 3:35:37 AM UTC-5, Bob Langelaan wrote:
> On Friday, March 11, 2016 at 10:13:04 PM UTC-8, bartekltg wrote:
> > On 12.03.2016 05:25, Bob Langelaan wrote:
> > > Clearly one way to do so is by using the merge member function of the
> > > list container class to merge the item into the sorted list. My
> > > question is: Is there a more efficient way to do it?

> > > ...

> >
> > It this operation is a bottleneck, You should consider
> > different container better suited for you needs.
> > Probably std::set, as Ian have said.
> >
> > best
> > Bartek
>
> Thanks. That is exactly what I was looking for :)

Two comments:

First, you may also want to look at std::multiset if there is
the possibility that your list may contain duplicates (and you
want to preserve that information).

Second, you might NOT want a container that has efficient (i.e.,
log(n)) insertion time if you insert rarely, but read / traverse /
look up frequently. If you insert rarely, append / sort (at
n log(n)) could be overall more efficient if it lets you use a
container that is more efficient for the rest of your use case.
(Also, if you insert in bunches, then several appends followed
by a sort can win overall.)


Best.


K. Frank