std::string::find vs std::find

iMalc · 07-08-2009, 12:19 AM

Quote:

Originally Posted by Daved

I'm a little surprised the sort takes that long. I would think it would be closer to the set's load time. Perhaps it is because your data is already mostly sorted?

I think that for it to take that long he would have to be sorting it after every push_back.

If you only sort it once, after the data is all loaded in, then perform many binary_searches, then the overhead of the sorting becomes less and less significant to the point that the binary_search will be faster. Still wont beat hashing, but it should be good enough.

**Bubba** · 07-08-2009, 04:14 PM

Hashing would definitely be faster and it's fairly trivial to write a templated hash container. If I need to 'find' items in a collection I rarely, if ever, use vector or list. For very small containers you probably will not notice any issues but you will as the container grows in size. Sorting can also be slow if you don't use it wisely. This is what iMalc is referring to. A brute force approach would be to sort after every change to the collection and that would also be the slowest approach. The less operations you perform on the container the faster it is going to be. If you only sort when you need to or can break the sort down into segments so less items are sorted at any one time then you should get improvements.

However the only way to know for sure is to try several approaches and see which one works best for your particular application.

anon · 07-08-2009, 05:26 PM

Some time ago I discovered a performance bug in MingW's implementation of iter_swap (which is used to swap items by the sorting routine among others). If you happen to have this compiler and change the implementation to:

Code:

  //fixed implementation (must be moved after swap in stl_algobase.h)
  template<typename _ForwardIterator1, typename _ForwardIterator2>
    inline void
    iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
    {
        //concept requirements...
        swap(*__a, *__b);
    }

this might speed up sorting strings in particular (might become comparable to the set).

The problem is that the existing implementation failed to take advantage of overloaded swap functions and creates lots of temporaries, just to swap two strings:

Code:

  template<typename _ForwardIterator1, typename _ForwardIterator2>
    inline void
    iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
    {
        typedef typename iterator_traits<_ForwardIterator1>::value_type
            _ValueType1;
        //concept requirements...
        const _ValueType1 __tmp = *__a;
        *__a = *__b;
        *__b = __tmp;
    }

07-08-2009, 04:14 PM	#17
Bubba Super Moderator Join Date: Aug 2001 Posts: 7,472	Hashing would definitely be faster and it's fairly trivial to write a templated hash container. If I need to 'find' items in a collection I rarely, if ever, use vector or list. For very small containers you probably will not notice any issues but you will as the container grows in size. Sorting can also be slow if you don't use it wisely. This is what iMalc is referring to. A brute force approach would be to sort after every change to the collection and that would also be the slowest approach. The less operations you perform on the container the faster it is going to be. If you only sort when you need to or can break the sort down into segments so less items are sorted at any one time then you should get improvements. However the only way to know for sure is to try several approaches and see which one works best for your particular application. __________________ If you aim at everything you will hit something but you won't know what it is. Last edited by Bubba; 07-08-2009 at 04:16 PM.
Bubba is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode