Find value (vector vs unordered_map)

[JohnnyBeeGoody]

Hello,

I'm working on a program that aims to backtest quantitative strategy and after looking at the performances of the code, I see that more that half of execution time in spent in a very simple function, which now want to optimise.

This function tells me if a stock is trading on a certain date and for that I have all my trading dates saved in a std::vector, thus the function just checks if it finds the date:

bool Asset::Trades (bdate d) const {
  return (find(tradingdates_.begin(), tradingdates_.end(), d) != tradingdates_.end());
}

I wondered if I could do better using another container. I know unordered_map's complexity for find in constant whereas log(N) for vector. But that would mean putting my date (boost::gregorian::date) as the key value but what would I use as mapped value.

If you have any idea.

Thanks

[JLBorges]

std::unordered_set http://en.cppreference.com/w/cpp/container/unordered_set

To store values of type boost::gregorian::date in the unordered set, a custom hash function is required.

The other (somewhat more efficient) option is to simply store the day_number of the dates in the unordered set.

#include <iostream>
#include <boost/date_time/gregorian/gregorian.hpp>
#include <unordered_set>

struct hash_boost_greg_date
{
    std::size_t operator() ( const boost::gregorian::date& dt ) const
    {
        static std::hash<boost::gregorian::date::date_int_type> hasher ;
        return hasher( dt.day_number() ) ;
    }
};

int main()
{
    const boost::gregorian::date dt{ 2016, boost::date_time::Aug, 5 } ;

    {
        std::unordered_set< boost::gregorian::date, hash_boost_greg_date > trading_days ;

        trading_days.insert(dt) ;
        if( trading_days.find(dt) != trading_days.end() ) std::cout << "found it\n" ;

    }

    {
        std::unordered_set<boost::gregorian::date::date_int_type> trading_days ;

        trading_days.insert( dt.day_number() ) ; // convert date to day_number
        if( trading_days.find( dt.day_number() ) != trading_days.end() ) { /* ... */ }

        const auto day_number = *trading_days.begin() ;
        const boost::gregorian::date dt2(day_number) ; // convert day_number to date
        std::cout << dt << " == " << dt2 << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/362f93ac6ada0e91