Sorting list vs sorting vector

Discussion in 'C++' started by boltar2003, Jul 5, 2010.

  1. boltar2003

    boltar2003 Guest


    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.

    boltar2003, Jul 5, 2010
    1. Advertisements

  2. 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.
    Francesco S. Carta, Jul 5, 2010
    1. Advertisements

  3. boltar2003

    James Kanze Guest

    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, Jul 6, 2010
    1. Advertisements

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 (here). After that, you can post your question and our members will help you out.