list<T> alternative...

[barcaroller]

I'm writing a real-time application which is currently using C++ linked
lists. The items have to be sorted. I collect the items as they come in,
search the list sequentially until I find the insertion point, and insert
the item.

This is proving to be inefficient. Is there a more efficient alternative
(maybe in Boost or standard C)?

 

[Scott McPhillips [MVP]]

I'm writing a real-time application which is currently using C++ linked
lists. The items have to be sorted. I collect the items as they come in,
search the list sequentially until I find the insertion point, and insert
the item.

This is proving to be inefficient. Is there a more efficient alternative
(maybe in Boost or standard C)?

Have a look at std::lower_bound, which uses a binary search. Should be
much faster than a sequential search.

 

[Piyo]

I'm writing a real-time application which is currently using C++ linked
lists. The items have to be sorted. I collect the items as they come in,
search the list sequentially until I find the insertion point, and insert
the item.

This is proving to be inefficient. Is there a more efficient alternative
(maybe in Boost or standard C)?

Have you taken a look at std::set<> ??

HTH!

 

[P.J. Plauger]

Have a look at std::lower_bound, which uses a binary search. Should be
much faster than a sequential search.

Doesn't help if the container is a list, because lower_bound
degenerates to a sequential search given bidirectional iterators.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 

[practisethink]

use std::map<>, it will be sorted when you add or remove item from it,
the speed of it's sort is very fast, because it use RB tree to store

 

[Rolf Magnus]

I'm writing a real-time application which is currently using C++ linked
lists. The items have to be sorted. I collect the items as they come in,
search the list sequentially until I find the insertion point, and insert
the item.

This is proving to be inefficient. Is there a more efficient alternative
(maybe in Boost or standard C)?

Well, what requirements do you have for your container? I don't think you
can speed it up much more with std::list, but maybe another container could
be used?

 

[Kai-Uwe Bux]

I'm writing a real-time application which is currently using C++ linked
lists. The items have to be sorted. I collect the items as they come in,
search the list sequentially until I find the insertion point, and insert
the item.

This is proving to be inefficient. Is there a more efficient alternative
(maybe in Boost or standard C)?

The closest to a sorted list is std::multiset<T>.


Best

Kai-Uwe Bux

 

[barcaroller]

Doesn't help if the container is a list, because lower_bound
degenerates to a sequential search given bidirectional iterators.

I should have clarified. It does not need to be a list. Any container
where I can insert and retrieve sorted items would be sufficient.

 

[wufeng]

I should have clarified. It does not need to be a list. Any container
where I can insert and retrieve sorted items would be sufficient.

set<> and map<> have sort function

 

[coosa]

I'm writing a real-time application which is currently using C++ linked
lists. The items have to be sorted. I collect the items as they come in,
search the list sequentially until I find the insertion point, and insert
the item.

This is proving to be inefficient. Is there a more efficient alternative
(maybe in Boost or standard C)?

Use Set;
Overload the less operator and you don't have to worry about the
sorting any more; it is ensured then that each element inside the set
is sorted; for speed associative containers are more appropriate; that
definitely includes the STL set class,

 

[sss.zhou]

I'm writing a real-time application which is currently using C++ linked
lists. The items have to be sorted. I collect the items as they come in,
search the list sequentially until I find the insertion point, and insert
the item.

This is proving to be inefficient. Is there a more efficient alternative
(maybe in Boost or standard C)?

I want asking you some questions:
A. Does the size of your application using list huge?
B. Does the application often insert or delete item in the middle of
list?
C. Does the application often access the item in the middle of list?

The choise you can make is to select an more efficient container
(e.g: set,map,list,verctor ....) or not a more efficient list. I don't
think that std will produce an unefficient list. If the list is
unefficient in you application, it is the list doesn't fit you
application. This is my oppinion.
At last, sorry for my poor english.( I am still studying) If anyone
points out the error or out of place using, I will be pleased with it.