C++ library with a lot of data structures

[Kallinteris Andreas]

Looking for performance efficient library(/ies)

specifically right now i am looking for a library that supports array queues

[JLBorges]

> specifically right now i am looking for a library that supports array queues

What limitation of std::queue (with the default std::deque as the underlying container) are you trying to overcome?

[Kallinteris Andreas]

std::deque uses a dynamic array but i want a static one (for perfomance)

[jonnin]

I don't know of any... you could dig around in the embedded world maybe, but even so most (almost all?) libraries are going to, at the very minimum, allocate it as a pointer based off a size you provide.


a fast queue … you just need 2 integers (current front and back) and the array. Wrap it in an object, 2-3 functions...
You could DIY this before you could locate, download, compile, and integrate someone else's code for it.

[doug4]

Why do you feel that a static array performs better than a dynamic one?

[Peter87]

Boost has a circular buffer. It will only do one dynamic allocation when you create it (unless you explicitly change the capacity) so it should be much better than std::deque. If you don't want any dynamic allocations at all I guess you would have to use your own allocator but I don't really know much about that.
https://www.boost.org/doc/libs/1_69_0/doc/html/circular_buffer.html

I also found this "fixed capacity queue" which sounds exactly like what you want but I have no idea how good it is.
https://www.etlcpp.com/queue.html

[z05DSL3A]

masterAndreas, You could take a look at Intel® Performance Libraries, they may have things that you are looking for.

I posted a link to free downloads here (haven't checked it's still valid)
http://www.cplusplus.com/forum/lounge/250217/

[JLBorges]

> Boost has a circular buffer. It will only do one dynamic allocation when you create it.

It is pretty fast.

#include <iostream>
#include <boost/circular_buffer.hpp>
#include <queue>
#include <utility>
#include <algorithm>
#include <random>
#include <ctime>

int main() {
    
    const int N = 100'000'000 ;
    std::mt19937 rng ; // not seeded

    const auto start = std::clock() ;

    const std::size_t capacity = 100'000 ;
    std::queue< int, boost::circular_buffer<int> > mq{ boost::circular_buffer<int>(capacity) } ;

    for( int i = 0 ; i < N ; ++i )
    {
        if( mq.empty() ) mq.push(i) ;
        else if( mq.size() == capacity ) mq.pop() ;
        else if( rng() & 1U ) mq.push(i) ;
        else mq.pop() ;
    }

    const auto end = std::clock() ;
    std::cout << "construction + " << N/1'000'000 << " million push/pop operations in "
              << (end-start) * 1000.0 / CLOCKS_PER_SEC << " processor millisecs.\n" ;
} 

echo && g++ -std=c++17 -O3 -march=native -Wall -Wextra -pedantic-errors main.cpp && ./a.out && echo -e '\n\n==============\n\n'
echo && clang++ -std=c++17  -stdlib=libc++ -O3 -march=native -Wall -Wextra -pedantic-errors main.cpp -lsupc++ && ./a.out

construction + 100 million push/pop operations in 1095.79 processor millisecs.


==============



construction + 100 million push/pop operations in 2125.37 processor millisecs.

http://coliru.stacked-crooked.com/a/40450a18e009214b

[JLBorges]

> I also found this "fixed capacity queue"

Fixed capacity queue a la ETL (throws on push to a full queue) using boost::circular_buffer

#include <iostream>
#include <boost/circular_buffer.hpp>
#include <queue>
#include <utility>
#include <algorithm>
#include <random>
#include <ctime>

template < typename T > struct my_queue {

    // https://www.boost.org/doc/libs/1_69_0/doc/html/circular_buffer.html#circular_buffer.intro
    using container_type = boost::circular_buffer<T> ;
    using value_type = typename container_type::value_type ;
    using size_type = typename container_type::size_type ;
    using reference = typename container_type::reference ;
    using const_reference = typename container_type::const_reference ;

    explicit my_queue( std::size_t capacity ) : buffer(capacity) {}

    bool empty() const { return buffer.empty() ; }
    bool full() const { return size() == capacity() ; }
    size_type size() const { return buffer.size() ; }
    size_type capacity() const { return buffer.capacity() ; }

    reference front() { return buffer.front() ; }
    const_reference front() const { return buffer.front() ; }
    reference back() { return buffer.back() ; }
    const_reference back() const { return buffer.back() ; }

    void push( const value_type& v ) { check_size() ; buffer.push_back(v) ; }
    void push( value_type&& v ) { check_size() ; buffer.push_back( std::move(v) ) ; }
    template < typename... ARGS > void emplace( ARGS&&... args )
    { check_size() ; buffer.emplace_back( std::forward<ARGS>(args)... ) ; }

    void pop() { if( !empty() ) buffer.pop_front() ; }

    void swap( my_queue& other ) noexcept { using std::swap ; swap( buffer, other.buffer ) ; }
    friend void swap( my_queue& a, my_queue& b ) { a.swap(b) ; }

    private:
        container_type buffer ;
        void check_size() const { if( full() ) throw std::runtime_error( "que is full" ) ; }
};

template struct my_queue<int> ;

int main() {
    
    const int N = 100'000'000 ;
    std::mt19937 rng ; // not seeded

    const auto start = std::clock() ;

    const std::size_t capacity = 100'000 ;
    my_queue<int> mq(capacity) ;

    for( int i = 0 ; i < N ; ++i )
    {
        if( mq.empty() ) mq.push(i) ;
        else if( mq.full() ) mq.pop() ;
        else if( rng() & 1U ) mq.push(i) ;
        else mq.pop() ;
    }

    const auto end = std::clock() ;
    std::cout << "construction + " << N/1'000'000 << " million push/pop operations in "
              << (end-start) * 1000.0 / CLOCKS_PER_SEC << " processor millisecs.\n" ;
} 

echo && g++ -std=c++17 -O3 -march=native -Wall -Wextra -pedantic-errors main.cpp && ./a.out && echo -e '\n\n==============\n\n'
echo && clang++ -std=c++17  -stdlib=libc++ -O3 -march=native -Wall -Wextra -pedantic-errors main.cpp -lsupc++ && ./a.out

construction + 100 million push/pop operations in 1254.22 processor millisecs.


==============



construction + 100 million push/pop operations in 2115.43 processor millisecs.

http://coliru.stacked-crooked.com/a/9b6d5eb643d6c165