I found the two related questions but they, however, do not answer my question:

The task is as follows:

Implement 'assign' function for the intervals container interval_map:

interval_map<K,V> is a data structure that efficiently associates intervals of keys of type K with values of type V; it is implemented on top of std::map.

Each key-value-pair (k,v) in the m_map member means that the value v is associated to the interval from k (including) to the next key (excluding) in m_map.

Example: the std::map (0,'A'), (3,'B'), (5,'A') represents the mapping

 0 -> 'A'
 1 -> 'A'
 2 -> 'A'
 3 -> 'B'
 4 -> 'B'
 5 -> 'A' 
 6 -> 'A'
 7 -> 'A'
// ... all the way to numeric_limits<key>::max()

The representation in m_map must be canonical, that is, consecutive map entries must not have the same value:

..., (0,'A'), (3,'A'), ... 

is not allowed.

Initially, the whole range of K is associated with a given initial value, passed to the constructor.

Key type K

  • besides being copyable and assignable, is less-than comparable via operator< ;
  • does not implement any other operations, in particular no equality comparison or arithmetic operators.

Value type V

  • besides being copyable and assignable, is equality-comparable via operator== ;
  • does not implement any other operations.

Below is my implementation of interval map in C++17 which works correctly but does not pass the efficiency (speed) requirement. The requirement is to use at most one operation of O(log N) complexity where N is the number of elements in the map.

Huh.. is it possible at all to achieve this ? Probably using new C++17 map's features like extract and merge ? But I could not come up with a good solution though..

#include <stdio.h>
#include <stdint.h>
#include <iostream>
#include <sstream>
#include <cmath>
#include <vector>
#include <functional>
#include <iomanip>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <limits>
#include <stdexcept>
#include <memory>
#include <chrono>
#include <random>

#if 1
#define OUTZ(...) std::cerr << __VA_ARGS__ << std::endl;
#define OUTZ(...)

// Placeholder type exposes only '<' operation on the underlying type T
template < class T >
struct Placeholder {

    typedef T inner_type;
    typedef Placeholder< T > Self;

    Placeholder(T _i) : i(_i) { }

    friend bool operator <(const Self& x, const Self& y) {
        return x.i < y.i;

    friend std::ostream& operator <<(std::ostream& os,
                  const Self& x) {
        os << x.i;
        return os;
    T i;

template<typename K, typename V>
class interval_map {

    friend void IntervalMapTest();
    V m_valBegin;
    std::map<K,V> m_map;

    // constructor associates whole range of K with val
    interval_map(V const& val)
        : m_valBegin(val)
    { }

    // Assign value val to interval [keyBegin, keyEnd).
    // Overwrite previous values in this interval.
    // If !( keyBegin < keyEnd ), this designates an empty interval,
    // and assign must do nothing.
    void assign( K const& keyBegin, K const& keyEnd, V const& val ) {

        if(!(keyBegin < keyEnd)) // empty interval

        auto [iend,endAdded] = m_map.emplace(keyEnd, val); // NOTE: the value must be adjusted!

        auto eraseEnd = iend;
        if(endAdded) {
            // see if we insert before the first interval
            const auto& vprev = (iend == std::begin(m_map) ? m_valBegin : std::prev(iend)->second);
            if(vprev == val) {
                eraseEnd = std::next(iend); // erase iend if the values are equal
            } else { // need to correct the value of 'keyEnd'
                iend->second = vprev;
        } else { // no insertion has occurred
            if(iend->second == val) {
                eraseEnd = std::next(iend);
        // insert with hint since keyBeg might be located just before keyEnd
        auto ibeg = m_map.insert_or_assign(iend, keyBegin, val);
        auto eraseBeg = std::next(ibeg);
            const auto& vprev = (ibeg == std::begin(m_map) ? m_valBegin : std::prev(ibeg)->second);
            if(vprev == val)
                eraseBeg = ibeg; // erase begin too as we hit

//        OUTZ("Erasing range: [" << eraseBeg->first << "; "
//             << (eraseEnd == end(m_map) ?  Kmax : eraseEnd->first) << ']');

        m_map.erase(eraseBeg, eraseEnd);

    // look-up of the value associated with key
    V const& operator[]( K const& key ) const
        auto it = m_map.upper_bound(key);
        if(it == m_map.begin()) {
            return m_valBegin;
        } else {
            return (--it)->second;

    void print(const std::string& msg = {}) {
        OUTZ("printing: " << msg);
        OUTZ("-oo -- > " << m_valBegin);
        for(const auto& [key, val] : m_map) {
            OUTZ(key << " ---> " << val);

    void clear() {

    //! tests whether intervals satisfy canonical representation
    void intervals_check() {

        const V *pprev = &m_valBegin;
        OUTZ("Checking intervals..");
        for(const auto& [k,v] : m_map) {
           // uncomment this to print intervals in the container
    #if 0
                std::cout << "[" << it->first << "; ";
                if(next != m_map.end())
                    std::cout << next->first << ") = ";
                    std::cout << "+oo) = ";
                std::cout << it->second << "\n";
            if(*pprev == v) {
                throw std::runtime_error("FATAL: incorrect intervals..");
            pprev = &v;

int main() try
    interval_map< Placeholder<int>, char > xmap('?');

    for(int i = 0; i < 10000; i++) {
        int beg = rand() % 20 - 10,
            end = beg + rand() % 100;
        char C = 'A' + rand() % 12;
        xmap.assign(beg, end, C);
    return 0;
catch(std::exception& ex) {
    std::cerr << "Exception: " << ex.what() << std::endl;
    return -1;
catch(...) {
    std::cerr << "Unknown exception!" << std::endl;
    return -1;
  • \$\begingroup\$ I see a couple of reasons why it does not pass the efficiency requirement. First, you erase beg/end immediately after inserting them (in some cases), leading to redundant operations on Key/Value. Second, they state that you should use overloads of insert/emplace that take a hint as a parameter. I think their criteria-testing system just straight-up rejects implementations that use insert/emplace/erase without a hint. Also, imagine that emplace_hint gives up with assert(false) if it couldn't insert in amortized constant time. \$\endgroup\$
    – Hedede
    Commented Mar 5 at 7:37

1 Answer 1


Include the correct headers

I don't see a need for these headers:

#include <chrono>
#include <cmath>
#include <functional>
#include <iomanip>
#include <limits>
#include <memory>
#include <random>
#include <set>
#include <sstream>
#include <stdint.h>
#include <stdio.h>
#include <unordered_map>
#include <vector>

On the other hand, we need to add these:

#include <cstdlib>              // std::srand, std::rand
#include <ctime>                // std::time
#include <iterator>             // std::next, std::prev, std::begin

Avoid macros

This doesn't really require a macro:

#if 1
#define OUTZ(...) std::cerr << __VA_ARGS__ << std::endl;
#define OUTZ(...)

One disadvantage is that when compiled out, the arguments don't get parsed, so errors can creep in.

We could just select an appropriate choice of stream (probably not std::cerr, given that its usage doesn't seem to be for errors):

#if 1
std::ostream& log_stream = std::clog;
std::ofstream log_stream{"/dev/null"};  // Or create a null stream class

Also, we probably don't want to be flushing all of this output, so prefer plain '\n' to heavyweight std::endl.

Placeholder class

This seems to be present just to confirm that the interval map doesn't require anything other < from the key type, so probably belongs with the test code.

inner_type is never used. Prefer using to typedef for Self (or just omit it).

The constructor is redundant: since i is public, the default aggregate initialisation should be fine.

The operators don't need to be friend, because i is public.

The interval_map class accepts any type for key and value; we should express the constraints:

#include <concepts>

template<std::copy_constructible K, std::equality_comparable V>
    requires requires(K key) { key < key; }
class interval_map

We have declared a friend called IntervalMapTest - it would be useful to have some tests, but this seems not to have been implemented. Definitely consider doing so.

The constructor can reduce copying of large value types using std::move:

    interval_map(V val)
        : m_valBegin{std::move(val)}
    { }

In assign(), we are also able to pass keyBegin and keyEnd by value, and std::move() them in arguments to emplace() and insert_or_assign().

As you say, the complexity here doesn't meet requirements. If our map has \$N\$ elements and the added range spans \$R\$ of them, we have:

  • std::map::emplace(): \$O(\log N)\$
  • std::map::insert_or_assign(): \$O(\log N)\$
  • std::map::erase(): \$O(\log N + R)\$

It's not possible to get the desired single \$O(\log N)\$ operation using this representation, due to the erase(). Options available are:

  • change the representation (likely harming performance of operator[]), or
  • use a hand-coded linear search for the start and end positions, leaving erase() as the only \$O(\log N)\$ function called from assign() (which doesn't seem to fit the spirit of the challenge).

It's normal for main() to return small positive values - for example, on my Linux system here, returning -1 results in status 255 received by the invoking shell. <cstdlib> has the macro EXIT_FAILURE for exactly this purpose, and I see no reason not to use it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.