Geek asks and answers

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

I want to create a map with the timestamp keyword and two other elements. So I thought something like this:

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

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

2) How to add a new item to this card? As far as I know, insertdoes not accept 3 parameters. I do not know the correct syntax for this operation.

3) I have to do a very quick search using a key (which is a timestamp in my case), so std::mapis this a suitable container for this purpose?

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

Thanks, really ...

+3
source share
2 answers

1) You can use TimePoint inside the map. Chrono has nanosecond resolution.

2) You can use Tuples . But the way you did it is already correct, you use only two parameters (time_t, std :: pair).

3) See here , I would use an unordered map ( EDIT : it looks like unordered maps cannot store time points (ideone.com/H6Yr7v). Instead, you need to use a map.)

EDIT:

++ 11, Vecihi. , , - ++ 11 capabilites , .

+1

boost_ ( PerformanceCounter ) System_clock 100 ().

, , : , , :

#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;
}

:

  • boost ++ 11 (++ 11, USE_BOOST )
  • g++ g++ 4.8.1 ( g++ 4.7.2), stable_clock . Boost, , ,

.

+1

More articles:


All Articles