STL list and sort
-
Gurus, If I have an STL list (doesn't matter what of) and I sort it, how can I add one element to the list, whilst maintaining the sort order? All I can think of to achieve this is to either: (1) add the new element to one end, and run sort() again, or (2) iterate through the entire list, checking the sort predicate against each element. Neither of these seem particulalrly appealing. Does anyone know the most processor efficient way of doing this please ? thanks, Neil.
cheers, Neil
-
Gurus, If I have an STL list (doesn't matter what of) and I sort it, how can I add one element to the list, whilst maintaining the sort order? All I can think of to achieve this is to either: (1) add the new element to one end, and run sort() again, or (2) iterate through the entire list, checking the sort predicate against each element. Neither of these seem particulalrly appealing. Does anyone know the most processor efficient way of doing this please ? thanks, Neil.
cheers, Neil
They hide that information in the documentation[^] Lower_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last) [1]. Specifically, it returns the first position where value could be inserted without violating the ordering. However that might not be the "most efficient" for your application. There are several things to consider. If you use STL much you should have Scott Meyers book as it discusses efficiency issues.
led mike
-
Gurus, If I have an STL list (doesn't matter what of) and I sort it, how can I add one element to the list, whilst maintaining the sort order? All I can think of to achieve this is to either: (1) add the new element to one end, and run sort() again, or (2) iterate through the entire list, checking the sort predicate against each element. Neither of these seem particulalrly appealing. Does anyone know the most processor efficient way of doing this please ? thanks, Neil.
cheers, Neil
neilsolent wrote:
f I have an STL list (doesn't matter what of) and I sort it, how can I add one element to the list, whilst maintaining the sort order? All I can think of to achieve this is to either: (1) add the new element to one end, and run sort() again, or (2) iterate through the entire list, checking the sort predicate against each element. Neither of these seem particulalrly appealing. Does anyone know the most processor efficient way of doing this please ?
If you insert only one element (2) is probably faster. You can make it even faster if you know from which end to start.
-
They hide that information in the documentation[^] Lower_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last) [1]. Specifically, it returns the first position where value could be inserted without violating the ordering. However that might not be the "most efficient" for your application. There are several things to consider. If you use STL much you should have Scott Meyers book as it discusses efficiency issues.
led mike
Thanks for that answer, Neil
cheers, Neil
-
neilsolent wrote:
f I have an STL list (doesn't matter what of) and I sort it, how can I add one element to the list, whilst maintaining the sort order? All I can think of to achieve this is to either: (1) add the new element to one end, and run sort() again, or (2) iterate through the entire list, checking the sort predicate against each element. Neither of these seem particulalrly appealing. Does anyone know the most processor efficient way of doing this please ?
If you insert only one element (2) is probably faster. You can make it even faster if you know from which end to start.
Thanks for that answer. Unfortunately there will be no way of knowing which end to start from. Neil
cheers, Neil
-
Thanks for that answer. Unfortunately there will be no way of knowing which end to start from. Neil
cheers, Neil
Best bet is to guess by seeing if it's closer in value to
front()orback(). That way, the average search distance for random data will be N/2 where N is the list length. -
They hide that information in the documentation[^] Lower_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last) [1]. Specifically, it returns the first position where value could be inserted without violating the ordering. However that might not be the "most efficient" for your application. There are several things to consider. If you use STL much you should have Scott Meyers book as it discusses efficiency issues.
led mike
led mike wrote:
However that might not be the "most efficient" for your application.
It probably won't be - I don't think the structure of
std::listiterators is terribly conducive to binary searches - could be wrong, mind. -
Best bet is to guess by seeing if it's closer in value to
front()orback(). That way, the average search distance for random data will be N/2 where N is the list length.Stuart Dootson wrote:
Best bet is to guess by seeing if it's closer in value to front() or back(). That way, the average search distance for random data will be N/2 where N is the list length.
but only when the values are distributed equally.
-
led mike wrote:
However that might not be the "most efficient" for your application.
It probably won't be - I don't think the structure of
std::listiterators is terribly conducive to binary searches - could be wrong, mind.Stuart Dootson wrote:
It probably won't be - I don't think the structure of std::list iterators is terribly conducive to binary searches - could be wrong, mind.
std::dequewould probably be a better choice in most cases.If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week Zac