Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

find_first_of: A performance pitfall among the STL algorithms

, 18 Jun 2007 CPOL
This article is discussing the performance problems found in the most notable find_first_of implementations and suggests useful improvements and workarounds.
////////////////////////////////////////////////////////////////////////////////
// The Loki Library
// Copyright (c) 2001 by Andrei Alexandrescu
// This code accompanies the book:
// Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design 
//     Patterns Applied". Copyright (c) 2001. Addison-Wesley.
// Permission to use, copy, modify, distribute and sell this software for any 
//     purpose is hereby granted without fee, provided that the above copyright 
//     notice appear in all copies and that both that copyright notice and this 
//     permission notice appear in supporting documentation.
// The author or Addison-Wesley Longman make no representations about the 
//     suitability of this software for any purpose. It is provided "as is" 
//     without express or implied warranty.
////////////////////////////////////////////////////////////////////////////////
#ifndef LOKI_ASSOCVECTOR_INC_
#define LOKI_ASSOCVECTOR_INC_

// $Id: AssocVector.h 765 2006-10-18 13:55:32Z syntheticpp $


#include <algorithm>
#include <functional>
#include <vector>
#include <utility>

namespace Loki
{
////////////////////////////////////////////////////////////////////////////////
// class template AssocVectorCompare
// Used by AssocVector
////////////////////////////////////////////////////////////////////////////////

    namespace Private
    {
        template <class Value, class C>
        class AssocVectorCompare : public C
        {
            typedef std::pair<typename C::first_argument_type, Value>
                Data;
            typedef typename C::first_argument_type first_argument_type;

        public:
            AssocVectorCompare()
            {}
            
            AssocVectorCompare(const C& src) : C(src)
            {}
            
            bool operator()(const first_argument_type& lhs, 
                const first_argument_type& rhs) const
            { return C::operator()(lhs, rhs); }
            
            bool operator()(const Data& lhs, const Data& rhs) const
            { return operator()(lhs.first, rhs.first); }
            
            bool operator()(const Data& lhs, 
                const first_argument_type& rhs) const
            { return operator()(lhs.first, rhs); }
            
            bool operator()(const first_argument_type& lhs,
                const Data& rhs) const
            { return operator()(lhs, rhs.first); }
        };
    }

////////////////////////////////////////////////////////////////////////////////
// class template AssocVector
// An associative vector built as a syntactic drop-in replacement for std::map
// BEWARE: AssocVector doesn't respect all map's guarantees, the most important
//     being:
// * iterators are invalidated by insert and erase operations
// * the complexity of insert/erase is O(N) not O(log N)
// * value_type is std::pair<K, V> not std::pair<const K, V>
// * iterators are random
////////////////////////////////////////////////////////////////////////////////


    template
    <
        class K,
        class V,
        class C = std::less<K>,
        class A = std::allocator< std::pair<K, V> >
    >
    class AssocVector 
        : private std::vector< std::pair<K, V>, A >
        , private Private::AssocVectorCompare<V, C>
    {
        typedef std::vector<std::pair<K, V>, A> Base;
        typedef Private::AssocVectorCompare<V, C> MyCompare;

    public:
        typedef K key_type;
        typedef V mapped_type;
        typedef typename Base::value_type value_type;

        typedef C key_compare;
        typedef A allocator_type;
        typedef typename A::reference reference;
        typedef typename A::const_reference const_reference;
        typedef typename Base::iterator iterator;
        typedef typename Base::const_iterator const_iterator;
        typedef typename Base::size_type size_type;
        typedef typename Base::difference_type difference_type;
        typedef typename A::pointer pointer;
        typedef typename A::const_pointer const_pointer;
        typedef typename Base::reverse_iterator reverse_iterator;
        typedef typename Base::const_reverse_iterator const_reverse_iterator;

        class value_compare
            : public std::binary_function<value_type, value_type, bool>
            , private key_compare
        {
            friend class AssocVector;
        
        protected:
            value_compare(key_compare pred) : key_compare(pred)
            {}

        public:
            bool operator()(const value_type& lhs, const value_type& rhs) const
            { return key_compare::operator()(lhs.first, rhs.first); }
        };
        
        // 23.3.1.1 construct/copy/destroy

        explicit AssocVector(const key_compare& comp = key_compare(), 
            const A& alloc = A())
        : Base(alloc), MyCompare(comp)
        {}
        
        template <class InputIterator>
        AssocVector(InputIterator first, InputIterator last, 
            const key_compare& comp = key_compare(), 
            const A& alloc = A())
        : Base(first, last, alloc), MyCompare(comp)
        {
            MyCompare& me = *this;
            std::sort(begin(), end(), me);
        }
        
        AssocVector& operator=(const AssocVector& rhs)
        { 
            AssocVector(rhs).swap(*this); 
            return *this;
        }

        // iterators:
        // The following are here because MWCW gets 'using' wrong
        iterator begin() { return Base::begin(); }
        const_iterator begin() const { return Base::begin(); }
        iterator end() { return Base::end(); }
        const_iterator end() const { return Base::end(); }
        reverse_iterator rbegin() { return Base::rbegin(); }
        const_reverse_iterator rbegin() const { return Base::rbegin(); }
        reverse_iterator rend() { return Base::rend(); }
        const_reverse_iterator rend() const { return Base::rend(); }
        
        // capacity:
        bool empty() const { return Base::empty(); }
        size_type size() const { return Base::size(); }
        size_type max_size() { return Base::max_size(); }

        // 23.3.1.2 element access:
        mapped_type& operator[](const key_type& key)
        { return insert(value_type(key, mapped_type())).first->second; }

        // modifiers:
        std::pair<iterator, bool> insert(const value_type& val)
        {
            bool found(true);
            iterator i(lower_bound(val.first));

            if (i == end() || this->operator()(val.first, i->first))
            {
                i = Base::insert(i, val);
                found = false;
            }
            return std::make_pair(i, !found);
        }
        //Section [23.1.2], Table 69
        //http://developer.apple.com/documentation/DeveloperTools/gcc-3.3/libstdc++/23_containers/howto.html#4
        iterator insert(iterator pos, const value_type& val)
        {
            if( (pos == begin() || this->operator()(*(pos-1),val)) && 
                (pos == end()    || this->operator()(val, *pos)) )
            {
                return Base::insert(pos, val);
            }
            return insert(val).first;
        }
       
        template <class InputIterator>
        void insert(InputIterator first, InputIterator last)
        { for (; first != last; ++first) insert(*first); }
        
        void erase(iterator pos)
        { Base::erase(pos); }

        size_type erase(const key_type& k)
        {
            iterator i(find(k));
            if (i == end()) return 0;
            erase(i);
            return 1;
        }

        void erase(iterator first, iterator last)
        { Base::erase(first, last); }

        void swap(AssocVector& other)
        {
            Base::swap(other);
            MyCompare& me = *this;
            MyCompare& rhs = other;
            std::swap(me, rhs);
        }
        
        void clear()
        { Base::clear(); }

        // observers:
        key_compare key_comp() const
        { return *this; }

        value_compare value_comp() const
        {
            const key_compare& comp = *this;
            return value_compare(comp);
        }

        // 23.3.1.3 map operations:
        iterator find(const key_type& k)
        {
            iterator i(lower_bound(k));
            if (i != end() && this->operator()(k, i->first))
            {
                i = end();
            }
            return i;
        }

        const_iterator find(const key_type& k) const
        {       
            const_iterator i(lower_bound(k));
            if (i != end() && this->operator()(k, i->first))
            {
                i = end();
            }
            return i;
        }

        size_type count(const key_type& k) const
        { return find(k) != end(); }

        iterator lower_bound(const key_type& k)
        {
            MyCompare& me = *this;
            return std::lower_bound(begin(), end(), k, me);
        }

        const_iterator lower_bound(const key_type& k) const
        {
            const MyCompare& me = *this;
            return std::lower_bound(begin(), end(), k, me);
        }

        iterator upper_bound(const key_type& k)
        {
            MyCompare& me = *this;
            return std::upper_bound(begin(), end(), k, me);
        }

        const_iterator upper_bound(const key_type& k) const
        {
            const MyCompare& me = *this;
            return std::upper_bound(begin(), end(), k, me);
        }

        std::pair<iterator, iterator> equal_range(const key_type& k)
        {
            MyCompare& me = *this;
            return std::equal_range(begin(), end(), k, me);
        }

        std::pair<const_iterator, const_iterator> equal_range(
            const key_type& k) const
        {
            const MyCompare& me = *this;
            return std::equal_range(begin(), end(), k, me);
        }

        template <class K1, class V1, class C1, class A1>
        friend bool operator==(const AssocVector<K1, V1, C1, A1>& lhs,
                        const AssocVector<K1, V1, C1, A1>& rhs);

        bool operator<(const AssocVector& rhs) const
        {
            const Base& me = *this;
            const Base& yo = rhs;
            return me < yo;
        }

        template <class K1, class V1, class C1, class A1>
        friend bool operator!=(const AssocVector<K1, V1, C1, A1>& lhs,
                               const AssocVector<K1, V1, C1, A1>& rhs);

        template <class K1, class V1, class C1, class A1>
        friend bool operator>(const AssocVector<K1, V1, C1, A1>& lhs,
                              const AssocVector<K1, V1, C1, A1>& rhs);

        template <class K1, class V1, class C1, class A1>
        friend bool operator>=(const AssocVector<K1, V1, C1, A1>& lhs,
                               const AssocVector<K1, V1, C1, A1>& rhs);

        template <class K1, class V1, class C1, class A1>
        friend bool operator<=(const AssocVector<K1, V1, C1, A1>& lhs,
                               const AssocVector<K1, V1, C1, A1>& rhs);
    };

    template <class K, class V, class C, class A>
    inline bool operator==(const AssocVector<K, V, C, A>& lhs,
                           const AssocVector<K, V, C, A>& rhs)
    {
      const std::vector<std::pair<K, V>, A>& me = lhs;
      return me == rhs;
    }

    template <class K, class V, class C, class A>
    inline bool operator!=(const AssocVector<K, V, C, A>& lhs,
                           const AssocVector<K, V, C, A>& rhs)
    { return !(lhs == rhs); }

    template <class K, class V, class C, class A>
    inline bool operator>(const AssocVector<K, V, C, A>& lhs,
                          const AssocVector<K, V, C, A>& rhs)
    { return rhs < lhs; }

    template <class K, class V, class C, class A>
    inline bool operator>=(const AssocVector<K, V, C, A>& lhs,
                           const AssocVector<K, V, C, A>& rhs)
    { return !(lhs < rhs); }

    template <class K, class V, class C, class A>
    inline bool operator<=(const AssocVector<K, V, C, A>& lhs,
                           const AssocVector<K, V, C, A>& rhs)
    { return !(rhs < lhs); }


    // specialized algorithms:
    template <class K, class V, class C, class A>
    void swap(AssocVector<K, V, C, A>& lhs, AssocVector<K, V, C, A>& rhs)
    { lhs.swap(rhs); }
    
} // namespace Loki

#endif // end file guardian

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Jim Xochellis
Software Developer
Greece Greece
I live in Greece with my wife and our two daughters. I am a professional software developer since 1999, using mostly C/C++ in my work.

My main expertise are: C/C++, STL, software optimization, generic programming and debugging. I am also very experienced in client–server programming, communications, concurrent programming, software security and cryptography. Finally, in my early professional years, I have worked a lot on cross-platform programming (Mac+Win).

I am familiar with the MFC, wxWidgets and Cplat GUI frameworks and the Python, Java, Pascal, Fortran, Prolog and Rexx programming languages.

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150414.1 | Last Updated 18 Jun 2007
Article Copyright 2007 by Jim Xochellis
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid