Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Sorting list vs sorting vector

Reply
Thread Tools

Sorting list vs sorting vector

 
 
boltar2003@boltar.world
Guest
Posts: n/a
 
      07-05-2010
Hi

If I have a list of *pointers* to objects that I need to store that will be
sorted based on values within each object , which will be quicker - sorting
a vector of pointers or sorting a list? Since the vector only needs to make
3 pointer copies to swap values whereas a doubly linked list will have to
update a lot more prev/next pointers I'm guessing it will be the vector but
I'm not 100% hence I'm asking the experts on this group.

Thanks for any help.

B2003

 
Reply With Quote
 
 
 
 
Francesco S. Carta
Guest
Posts: n/a
 
      07-05-2010
http://www.velocityreviews.com/forums/(E-Mail Removed)d, on 05/07/2010 11:58:12, wrote:

> Hi
>
> If I have a list of *pointers* to objects that I need to store that will be
> sorted based on values within each object , which will be quicker - sorting
> a vector of pointers or sorting a list? Since the vector only needs to make
> 3 pointer copies to swap values whereas a doubly linked list will have to
> update a lot more prev/next pointers I'm guessing it will be the vector but
> I'm not 100% hence I'm asking the experts on this group.



The best way to find which one is faster on your implementation is to
profile them - once you're there, consider using a std::set passing your
custom compare function to it, there will be no need to sort it out
since it will keep itself sorted as you add items.

--
FSC - http://userscripts.org/scripts/show/59948
http://fscode.altervista.org - http://sardinias.com
 
Reply With Quote
 
 
 
 
James Kanze
Guest
Posts: n/a
 
      07-06-2010
On Jul 5, 10:47 pm, Paavo Helde <(E-Mail Removed)> wrote:
> (E-Mail Removed) wrote innews:i0shck$2je$(E-Mail Removed):


> > If I have a list of *pointers* to objects that I need to store that
> > will be sorted based on values within each object , which will be
> > quicker - sorting a vector of pointers or sorting a list? Since the
> > vector only needs to make 3 pointer copies to swap values whereas a
> > doubly linked list will have to update a lot more prev/next pointers
> > I'm guessing it will be the vector but I'm not 100% hence I'm asking
> > the experts on this group.


> Depends on zillions of the things. I would suspect most of the time goes
> for dereferencing the pointers and accessing the data in each object
> needed for sorting, so it would not really matter much whatever you use
> for storing the pointers themselves. Profiling is the only way to know.


Yes. The number of pointer manipulations is probably around the
same order of magnitude in both cases---it might even be
slightly lower for list. But sorting a list uses a different
algorithm than sorting a vector, and the number of comparisons
is likely to be extremely different.

--
James Kanze
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
const vector<A> vs vector<const A> vs const vector<const A> Javier C++ 2 09-04-2007 08:46 PM
Initializing vector<vector<int> > and other vector questions... pmatos C++ 6 04-26-2007 05:39 PM
Can list container contain an vector object, such as list< vector<string> >?? ehui928 C++ 2 05-29-2006 01:09 PM
Free memory allocate by a STL vector, vector of vector, map of vector Allerdyce.John@gmail.com C++ 8 02-18-2006 12:48 AM
how the vector is created, how to pass vector to webservices method apachesoap:Vector Rushikesh Joshi Perl Misc 0 07-10-2004 01:04 PM



Advertisments