Assignment function for Intervals container

Question

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

• Hedede: 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.

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

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;
#else
std::ofstream log_stream{"/dev/null"}; // Or create a null stream class
#endif

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.