STL question - does sorting speed up find() for vector?

Discussion in 'C++' started by boltar2003@yahoo.co.uk, May 7, 2009.

  1. Guest

    Hi

    I have a vector containing an list of integers I need to search for. I'm
    not sure how the find() algorithm works internally so if I sort the vector
    will it speed up find() or should I not bother? Does the same apply to a
    list?

    Thanks

    B2003
    , May 7, 2009
    #1
    1. Advertising

  2. Neelesh Guest

    On May 7, 3:02 pm, wrote:
    > Hi
    >
    > I have a vector containing an list of integers I need to search for. I'm
    > not sure how the find() algorithm works internally so if I sort the vector
    > will it speed up find() or should I not bother? Does the same apply to a
    > list?
    >

    Exact definition of std::find() is left to the implementation. The
    standard guanratees that this algorithm runs in worst case O(n), where
    n is the length of the segment we wish to run the search on. However,
    it does not guarantee any kind of "performance improvements" if the
    container is sorted. Moreover,
    (a) There is no way you can tell std::find that the vector is sorted.
    (b) A vector is a "sequence" container, which means that the order of
    the elements in it matters. You would end up in changing the order
    while sorting, even if you don't intend that.

    Finally, even if we assume that you use a sorting algorithm and then a
    hypothetical "optimized" find() on the sorted container, you would end
    up with complexity O(n log(n)) + O(log(n)), i.e. O(n log(n)), which is
    not as better as O(n) guaranteed by std::find.

    std::list is also a sequence container, and hence the same would apply
    for std::list too.

    Thanks.
    Neelesh, May 7, 2009
    #2
    1. Advertising

  3. "Neelesh" <> wrote in message
    news:...
    >On May 7, 3:02 pm, wrote:
    >> I have a vector containing an list of integers I need to search for. I'm
    >> not sure how the find() algorithm works internally so if I sort the
    >> vector
    >> will it speed up find() or should I not bother? Does the same apply to a
    >> list?

    > Exact definition of std::find() is left to the implementation. The
    > standard guanratees that this algorithm runs in worst case O(n), where
    > n is the length of the segment we wish to run the search on. However,
    > it does not guarantee any kind of "performance improvements" if the
    > container is sorted.


    True. But if the container is sorted, and you know it, then don't use
    std::find, use (depending on exactly what you want to know)
    std::binary_search, std::lower_bound, std::upper_bound or
    std::equal_range.

    > Finally, even if we assume that you use a sorting algorithm and then a
    > hypothetical "optimized" find() on the sorted container, you would end
    > up with complexity O(n log(n)) + O(log(n)), i.e. O(n log(n)), which is
    > not as better as O(n) guaranteed by std::find.


    Thus sorting to improve a single search is a bad idea. But if you are
    searching the same container, without changing it, many times, it may
    be worthwhile. As may in some cases using a set or multiset (or map
    or multimap). Or if you have them, their unordered (hash) equivalents.

    Of course this is subject to the usual "premature optimization" warning,
    especially if the container is small.
    Christopher Dearlove, May 7, 2009
    #3
  4. Guest

    On 7 May, 11:02, wrote:
    > Hi
    >
    > I have a vector containing an list of integers I need to search for. I'm
    > not sure how the find() algorithm works internally so if I sort the vector
    > will it speed up find() or should I not bother? Does the same apply to a
    > list?


    find() can't take advantage of a sorted vector, but binary_search()
    does (the vector *must* be sorted first). Yes, you should bother if
    you're going to search the vector many times. You can use the same
    function with a list, but the gains would be negligable (or negative)
    because list iterators are not random access.

    HTH - Guy
    , May 7, 2009
    #4
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Dennis
    Replies:
    1
    Views:
    2,579
    Dennis
    Jun 7, 2004
  2. Replies:
    8
    Views:
    1,913
    Csaba
    Feb 18, 2006
  3. Replies:
    2
    Views:
    1,420
    James Kanze
    Jul 6, 2010
  4. Weng Lei-QCH1840
    Replies:
    1
    Views:
    181
    Thomas
    Aug 15, 2003
  5. Luca Risolia

    STL map to STL vector

    Luca Risolia, Jan 13, 2014, in forum: C++
    Replies:
    32
    Views:
    360
    Seungbeom Kim
    Jan 18, 2014
Loading...

Share This Page