Adding new item and searching with time key in a 3 element map C++

Question

I want to create a map with a high resolution timestamp key and two other items. So I thought something like that:

std::map<time_t,std::pair<long,int>> someContainer; //(time_t will be replaced)

1) I need a timestamp type which is nanosecond resolution, I saw boost::chrono::high_resolution_clock but I don't think it will give nanosecond resolution, and if it is can I use it as a type inside a map?

2) How to add a new item to this map? As far as I know insert does not take 3 parameters. I don't know the right syntax for this operation.

3) I have to perform a very fast search via the key (which is timestamp in my case) so std::map is the right container for this purpose?

By the way I am working in Visual Studio 2008, Visual C++ in a Win 7 x64 computer...

Thanks indeed...

Answer 1

You can use boost steady_clock (which actually is using a PerformanceCounter on windoes) The system_clock has a resolution of 100 nanoseconds (windows).

Utilizing timestamps and with the assumption the timestamps are added chronological to the container you could implement a hybrid solution: A sequential container holding the entries and a mapped view to ranges in that sequence:

#define USE_BOOST 1

#include <algorithm>
#include <deque>
#include <iostream>
#include <map>

#if USE_BOOST
#include <boost/chrono/system_clocks.hpp>
#include <boost/chrono/chrono_io.hpp>
#else
#include <chrono>
#endif

#if USE_BOOST
#define CHRONO boost::chrono
#else
#define CHRONO std::chrono
#endif

struct Entry {
    typedef CHRONO::steady_clock clock_type;
    typedef clock_type::time_point time_point;

    time_point time;
    // More members

    Entry(const time_point& time)
    :   time(time)
    {}
};

volatile int a;
int main()
{
    typedef Entry::clock_type clock_type;
    typedef clock_type::time_point time_point;
    typedef std::deque<Entry> entry_container;
    typedef entry_container::size_type size_type;

    typedef std::map<time_point, size_type> entry_index;
    const size_type EntryIndexRange = std::max(128 / sizeof(Entry), size_type(16));

    entry_container entries;
    entry_index index;

    // Samples
    // =======

    time_point min_time = clock_type::now();
    for(unsigned i = 0; i < 1000; ++i) {
        time_point time = clock_type::now();
        if(entries.size() % EntryIndexRange == 0) {
            index.insert(entry_index::value_type(time, entries.size()));
        }
        entries.push_back(Entry(time));
    }
    time_point max_time = clock_type::now();

    // Lookup
    // ======

    time_point lookup_time = min_time + (max_time - min_time) / 2;
    std::cout
        << "Lookup: "
        << CHRONO::duration_cast<CHRONO::nanoseconds>(
            lookup_time - min_time).count()
        << " nanoseconds\n";
    entry_index::const_iterator idx = index.lower_bound(lookup_time);
    if(idx != index.end()) {
        struct Less {
            bool operator () (const Entry& e, const time_point& t) const {
                return e.time < t;
            }
        };
        size_type i = idx->second;
        entry_container::const_iterator entry = std::lower_bound(
            entries.begin() + i, entries.begin() + i + EntryIndexRange, lookup_time, Less());
        if(entry != entries.end()) {
            if(entry->time == lookup_time) {
                std::cout
                    << "Match: "
                    << CHRONO::duration_cast<CHRONO::nanoseconds>(
                        entry->time - min_time).count()
                    << " nanoseconds\n";
            }
            else {
                time_point next_time = max_time;
                entry_container::const_iterator next = entry;
                if(++next != entries.end()) next_time = next->time;
                std::cout
                    << "Range: "
                    << CHRONO::duration_cast<CHRONO::nanoseconds>(
                        entry->time - min_time).count()
                    << " to  "
                    << CHRONO::duration_cast<CHRONO::nanoseconds>(
                        next_time - min_time).count()
                    << " nanoseconds\n";
            }
        }
    }
    return 0;
}

Notes:

• The code requires boost or C++11 (C++11 if USE_BOOST is zero)
• If the code is compiled with g++ below g++ 4.8.1 (I have g++ 4.7.2) and without boost the resolution of the steady_clock is microseconds, only. Boost seems to support nanoseconds, though

With this approach you keep the data sorted and have a reasonable performance to lookup a time-key.