boost::unordered_map takes too long when I have only two elements in it

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

boost::unordered_map takes too long when I have only two elements in it

Boost - Users mailing list
Hi,

I am using a boost::unordered_set but I sometimes have just two elements in it. It takes a long time then. Is it wrong if I have too few elements?

Thanks,
Ram


_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: boost::unordered_map takes too long when I have only two elements in it

Boost - Users mailing list
On 14 July 2017 at 13:18, Ram via Boost-users <[hidden email]> wrote:
Is it wrong if I have too few elements?

No, but with 2 elements, the std::unordered_set is gonna be slow, due to all the things that need to be done. If you have always just a couple of elements, just sticking them in a std::vector and doing a linear search might be much faster. You could also maintain an ordered list over a std::vector and use std::lower_bound for doing a binary search.

Below is a priority_queue working like this:

template < typename T >
class priority_queue {

private:

    typedef std::vector < T > Data;

public:

    typedef typename Data::iterator iterator;
    typedef typename Data::const_iterator const_iterator;

private:

    Data m_data;

public:

    priority_queue ( ) noexcept {

        m_data.clear ( );
    }

    iterator begin ( ) noexcept {

        return m_data.begin ( );
    }

    const_iterator begin ( ) const noexcept {

        return m_data.begin ( );
    }

    iterator end ( ) noexcept {

        return m_data.end ( );
    }

    const_iterator end ( ) const noexcept {

        return m_data.end ( );
    }

    void push ( const T t_ ) noexcept {

        const iterator i = std::lower_bound ( m_data.begin ( ), m_data.end ( ), t_, std::greater < T > ( ) );

        if ( i == m_data.end ( ) or std::greater < T > ( ) ( t_, *i ) ) {

            m_data.insert ( i, t_ );
        }
    }

    inline void pop ( ) noexcept {

        if ( m_data.size ( ) ) {

            m_data.pop_back ( );
        }
    }

    inline T top ( ) const noexcept {

        return m_data.back ( );
    }

    inline size_t size ( ) const noexcept {

        return m_data.size ( );
    }

    inline bool empty ( ) const noexcept {

        return m_data.empty ( );
    }
};

Up to something like 128 elements the above is faster than the STL version...

Matt Austern has written a (now famous) paper on the subject.

degski
--
"Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend." - Novalis 1798

_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: boost::unordered_map takes too long when I have only two elements in it

Boost - Users mailing list

Note that there is also flat_set / flat_map in the boost containers library, which does exactly that.


From: Boost-users <[hidden email]> on behalf of degski via Boost-users <[hidden email]>
Sent: Friday, July 14, 2017 12:51:53 PM
To: [hidden email]
Cc: degski
Subject: Re: [Boost-users] boost::unordered_map takes too long when I have only two elements in it
 
On 14 July 2017 at 13:18, Ram via Boost-users <[hidden email]> wrote:
Is it wrong if I have too few elements?

No, but with 2 elements, the std::unordered_set is gonna be slow, due to all the things that need to be done. If you have always just a couple of elements, just sticking them in a std::vector and doing a linear search might be much faster. You could also maintain an ordered list over a std::vector and use std::lower_bound for doing a binary search.

Below is a priority_queue working like this:

template < typename T >
class priority_queue {

private:

    typedef std::vector < T > Data;

public:

    typedef typename Data::iterator iterator;
    typedef typename Data::const_iterator const_iterator;

private:

    Data m_data;

public:

    priority_queue ( ) noexcept {

        m_data.clear ( );
    }

    iterator begin ( ) noexcept {

        return m_data.begin ( );
    }

    const_iterator begin ( ) const noexcept {

        return m_data.begin ( );
    }

    iterator end ( ) noexcept {

        return m_data.end ( );
    }

    const_iterator end ( ) const noexcept {

        return m_data.end ( );
    }

    void push ( const T t_ ) noexcept {

        const iterator i = std::lower_bound ( m_data.begin ( ), m_data.end ( ), t_, std::greater < T > ( ) );

        if ( i == m_data.end ( ) or std::greater < T > ( ) ( t_, *i ) ) {

            m_data.insert ( i, t_ );
        }
    }

    inline void pop ( ) noexcept {

        if ( m_data.size ( ) ) {

            m_data.pop_back ( );
        }
    }

    inline T top ( ) const noexcept {

        return m_data.back ( );
    }

    inline size_t size ( ) const noexcept {

        return m_data.size ( );
    }

    inline bool empty ( ) const noexcept {

        return m_data.empty ( );
    }
};

Up to something like 128 elements the above is faster than the STL version...

Matt Austern has written a (now famous) paper on the subject.

degski
--
"Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend." - Novalis 1798

_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: boost::unordered_map takes too long when I have only two elements in it

Boost - Users mailing list
Thanks!

_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Loading...