By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,137 Members | 1,024 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,137 IT Pros & Developers. It's quick & easy.

list<T> alternative...

P: n/a
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)?
Mar 13 '07 #1
Share this Question
Share on Google+
10 Replies


P: n/a
barcaroller wrote:
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.

--
Scott McPhillips [VC++ MVP]

Mar 13 '07 #2

P: n/a
barcaroller wrote:
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!
Mar 13 '07 #3

P: n/a
"Scott McPhillips [MVP]" <org-dot-mvps-at-scottmcpwrote in message
news:Xo******************************@comcast.com. ..
barcaroller wrote:
>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.
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
Mar 13 '07 #4

P: n/a
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
Mar 13 '07 #5

P: n/a
barcaroller wrote:
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?

Mar 13 '07 #6

P: n/a
barcaroller wrote:
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
Mar 13 '07 #7

P: n/a

"P.J. Plauger" <pj*@dinkumware.comwrote in message
news:9c******************************@giganews.com ...

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.


Mar 13 '07 #8

P: n/a
On Mar 14, 6:33 am, "barcaroller" <barcarol...@music.netwrote:
"P.J. Plauger" <p...@dinkumware.comwrote in message

news:9c******************************@giganews.com ...
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.
set<and map<have sort function

Mar 14 '07 #9

P: n/a
On Mar 13, 8:38 am, "barcaroller" <barcarol...@music.netwrote:
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,

Mar 14 '07 #10

P: n/a
On Mar 13, 8:38 am, "barcaroller" <barcarol...@music.netwrote:
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.

Mar 16 '07 #11

This discussion thread is closed

Replies have been disabled for this discussion.