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

• interval map implementation
• Where exactly does my code not adhere to the specification of the key and value type?

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;
#else
#define OUTZ(...)
#endif

// 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;

public:
    // 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
            return;

        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() {
        m_map.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 << ") = ";
                else
                    std::cout << "+oo) = ";
                std::cout << it->second << "\n";
    #endif
            if(*pprev == v) {
                throw std::runtime_error("FATAL: incorrect intervals..");
            }
            pprev = &v;
        }
    }
};


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

    srand(time(NULL));
    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);
        xmap.print();
        xmap.intervals_check();
    }
    return 0;
}
catch(std::exception& ex) {
    std::cerr << "Exception: " << ex.what() << std::endl;
    return -1;
}
catch(...) {
    std::cerr << "Unknown exception!" << std::endl;
    return -1;
}