Note that there is also flat_set / flat_map in the boost containers library, which does exactly that. ________________________________ From: Boost-users <boost-users-bounces@lists.boost.org> on behalf of degski via Boost-users <boost-users@lists.boost.org> Sent: Friday, July 14, 2017 12:51:53 PM To: boost-users@lists.boost.org 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 <boost-users@lists.boost.org<mailto:boost-users@lists.boost.org>> 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<http://www.lafstern.org/matt/> has written a (now famous) paper<http://lafstern.org/matt/col1.pdf> on the subject. degski -- "Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend." - Novalis 1798