Sorting list vs sorting vector

B

boltar2003

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
 
F

Francesco S. Carta

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.
 
J

James Kanze

(e-mail address removed) wrote innews:[email protected]:
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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,733
Messages
2,569,440
Members
44,829
Latest member
PIXThurman

Latest Threads

Top