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

Question

Task Description

interval_map<K,V> is a data structure that efficiently associates intervals of keys of type K with values of type V. Your task is to implement the assign member function of this data structure, which is outlined below.

interval_map<K, V> is implemented on top of std::map. In case you are not entirely sure which functions std::map provides, what they do and which guarantees they provide, we provide an excerpt of the C++ standard here. (at the end)

Each key-value-pair (k,v) in the std::map means that the value v is associated with the interval from k (including) to the next key (excluding) in the std::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<int>::max()

The representation in the std::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 of the interval_map data structure.

Here's my implementation of assign(): (rest of the code comes by default).

#include <map>
#include <limits>

template<typename K, typename V>
class interval_map {
    std::map<K,V> m_map;

public:
  // constructor associates whole range of K with val by inserting (K_min, val)
  // into the map
  interval_map( V const& val) {
      m_map.insert(m_map.end(),std::make_pair(std::numeric_limits<K>::lowest(),val));
  }

  // Assign value val to interval [keyBegin, keyEnd).
  // Overwrite previous values in this interval.
  // Conforming to the C++ Standard Library conventions, the interval
  // includes keyBegin, but excludes keyEnd.
  // If !( keyBegin < keyEnd ), this designates an empty interval,
  // and assign must do nothing.
  void assign( K const& keyBegin, K const& keyEnd, V const& val ) {

        // insert code here   
        if (!(keyBegin < keyEnd)) return;

        std::pair<K,V> beginExtra;
        std::pair<K,V> endExtra;
        bool beginHasExtra = false;
        bool endHasExtra = false;

        typename std::map<K,V>::iterator itBegin;
        itBegin = m_map.lower_bound(keyBegin);
        if ( itBegin!=m_map.end() && keyBegin < itBegin->first ) {
            if (itBegin != m_map.begin()) {
                beginHasExtra = true;
                --itBegin;
                beginExtra = std::make_pair(itBegin->first, itBegin->second);
            }
            // openRange for erase is prevIterator
            // insert (prevIterator->first, prevIterator->second) as well!
        }

        typename std::map<K,V>::iterator itEnd;
        itEnd = m_map.lower_bound(keyEnd);
        if ( itEnd!=m_map.end() && keyEnd < itEnd->first ) {
            endHasExtra = true;
            typename std::map<K,V>::iterator extraIt = itEnd;
            --extraIt;
            endExtra = std::make_pair(keyEnd, extraIt->second);
            // closeRange for erase is this iterator
            // insert (keyEnd, prevIterator->second) as well!
        }

        // 4 canonical conflicts:
        //   beginExtra w/ mid
        //   before-mid w/ mid (beginHasExtra==false)
        //   mid w/ endExtra
        //   mid w/ after-mid (endHasExtra==false)

        bool insertMid = true;
        if (beginHasExtra) {
            if (beginExtra.second == val)
                insertMid = false;
        } else {
            if (itBegin != m_map.begin()) {
                typename std::map<K,V>::iterator beforeMid = itBegin;
                --beforeMid;
                if (beforeMid->second == val)
                    insertMid = false;
            }
        }


        if (endHasExtra) {
            if ( (insertMid && endExtra.second == val) || (!insertMid && endExtra.second == beginExtra.second) )
                endHasExtra = false;
        } else {
            if ( (insertMid && itEnd!=m_map.end() && itEnd->second == val) || (!insertMid && itEnd!=m_map.end() && itEnd->second == beginExtra.second) )
                itEnd = m_map.erase(itEnd);
        }

        itBegin = m_map.erase(itBegin, itEnd);
        if (beginHasExtra)
            itBegin = m_map.insert(itBegin, beginExtra);
        if (insertMid)
            itBegin = m_map.insert(itBegin, std::make_pair(keyBegin, val));
        if (endHasExtra)
            m_map.insert(itBegin, endExtra);
  }

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

Key type

K

• besides being copyable and assignable, is less-than comparable via operator<
• is bounded below, with the lowest value being std::numeric_limits::lowest()
• 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

===========================================================================

This code works perfectly fine on my local machine. However after submitting the code I got You must adhere to the specification of the key and value type given above. Can anyone tell me what I did wrong? I know I should've used const_iterator for my iterators but the error is talking about K, V.

===========================================================================

The following paragraphs from the final draft of the C++1x ISO standard describe the available 
operations on a std::map container, their effects and their complexity.

23.2.1 General container requirements 

§1 Containers are objects that store other objects. They control allocation and deallocation of 
these objects through constructors, destructors, insert and erase operations.

§6 begin() returns an iterator referring to the first element in the container. end() returns 
an iterator which is the past-the-end value for the container. If the container is empty, 
then begin() == end();

24.2.1 General Iterator Requirements

§1 Iterators are a generalization of pointers that allow a C++ program to work with different 
data structures.

§2 Since iterators are an abstraction of pointers, their semantics is a generalization of most 
of the semantics of pointers in C++. This ensures that every function template that takes 
iterators works as well with regular pointers.

§5 Just as a regular pointer to an array guarantees that there is a pointer value pointing past 
the last element of the array, so for any iterator type there is an iterator value that points 
past the last element of a corresponding sequence. These values are called past-the-end values. 
Values of an iterator i for which the expression *i is defined are called dereferenceable. 
The library never assumes that past-the-end values are dereferenceable. Iterators can also have 
singular values that are not associated with any sequence. [ Example: After the declaration of 
an uninitialized pointer x (as with int* x;), x  must always be assumed to have a singular 
value of a pointer. -end example ] Results of most expressions are undefined for singular 
values; the only exceptions are destroying an iterator that holds a singular value, the 
assignment of a non-singular value to an iterator that holds a singular value, and, for 
iterators that satisfy the DefaultConstructible requirements, using a value-initialized 
iterator as the source of a copy or move operation.

§10 An invalid iterator is an iterator that may be singular. (This definition applies to 
pointers, since pointers are iterators. The effect of dereferencing an iterator that has been 
invalidated is undefined.)

23.2.4 Associative containers

§1 Associative containers provide fast retrieval of data based on keys. The library provides 
four basic kinds of associative containers: set, multiset, map and multimap.

§4 An associative container supports unique keys if it may contain at most one element for each 
key. Otherwise, it supports equivalent keys. The set and map classes support unique keys; the 
multiset and multimap classes support equivalent keys.

§5 For map and multimap the value type is equal to std::pair<const Key, T>. Keys in an 
associative container are immutable.

§6 iterator of an associative container is of the bidirectional iterator category.
(i.e., an iterator i can be incremented and decremented: ++i; --i;)

§9 The insert member functions (see below) shall not affect the validity of iterators and 
references to the container, and the erase members shall invalidate only iterators and 
references to the erased elements.

§10 The fundamental property of iterators of associative containers is that they iterate 
through the containers in the non-descending order of keys where non-descending is defined by 
the comparison that was used to construct them.

Associative container requirements (in addition to general container requirements):

std::pair<iterator, bool> insert(std::pair<const key_type, T> const" t)
Effects: Inserts t if and only if there is no element in the container with key equivalent to 
the key of t. The bool component of the returned pair is true if and only if the insertion 
takes place, and the iterator component of the pair points to the element with key equivalent 
to the key of t.
Complexity: logarithmic

iterator insert(const_iterator p, std::pair<const key_type, T> const" t)
Effects: Inserts t if and only if there is no element with key equivalent to the key of t in 
containers with unique keys. Always returns the iterator pointing to the element with key 
equivalent to the key of t. 
Complexity: logarithmic in general, but amortized constant if t is inserted right before p.

size_type erase(key_type const" k)  
Effects: Erases all elements in the container with key equivalent to k. Returns the number of 
erased elements.
Complexity: log(size of container) + number of elements with key k

iterator erase(const_iterator q) 
Effects: Erases the element pointed to by q. Returns an iterator pointing to the element 
immediately following q prior to the element being erased. If no such element exists, returns 
end().
Complexity: Amortized constant

iterator erase(const_iterator q1, const_iterator q2)
Effects: Erases all the elements in the left-inclusive and right-exclusive range [q1,q2). 
Returns q2.
Complexity: Amortized O(N) where N has the value distance(q1, q2).

void clear() 
Effects: erase(begin(), end())
Post-Condition: empty() returns true
Complexity: linear in size().

iterator find(key_type const" k);
Effects: Returns an iterator pointing to an element with the key equivalent to k, or end() if 
such an element is not found.
Complexity: logarithmic

size_type count(key_type constquot;& k) 
Effects: Returns the number of elements with key equivalent to k
Complexity: log(size of map) + number of elements with key equivalent to k

iterator lower_bound(key_type const" k)
Effects: Returns an iterator pointing to the first element with key not less than k, or end() 
if such an element is not found.
Complexity: logarithmic

iterator upper_bound(key_type const" k)
Effects: Returns an iterator pointing to the first element with key greater than k, or end() 
if such an element is not found.
Complexity: logarithmic

23.4.1 Class template map

§1 A map is an associative container that supports unique keys (contains at most one of each 
key value) and provides for fast retrieval of values of another type T based on the keys. The 
map class supports bidirectional iterators.

23.4.1.2 map element access

T" operator[](const key_type" x);
Effects: If there is no key equivalent to x in the map, inserts value_type(x, T()) into the map. 
Returns: A reference to the mapped_type corresponding to x in *this.
Complexity: logarithmic.

T" at(const key_type" x);
const T" at(const key_type" x) const;
Returns: A reference to the element whose key is equivalent to x.
Throws: An exception object of type out_of_range if no such element is present.
Complexity: logarithmic.

Answer 1

Like others have said, the problem in your code is the assumption that K, V both can be default constructed. This becomes clear when you test a key type that is not default-constructible (see my test below)

'std::pair<K,V>::pair': no appropriate default constructor available

Here's my implementation, which passed the correctness check, but failed the runtime complexity check. I can't see how it is possible to erase N keys but keep the complexity O(logN), consider the following legit scenario:

Before assigning

'A' ................. 'B' ....A MILLION INTERVALS........ 'C' ..........................'A'..

After assigning a new interval, overwriting previous ones:

'A' ......... 'D'................................................................... 'A' ........................

I am pretty sure erasing N nodes takes at least O(N) time, since deallocating the memory for each node alone would be linear. No matter what smart way, dropping nodes between the new begin and new end would be linear. Another equivalent way would be extracting nodes and change their keys; However, that would only shift redundant keys towards the end rather than the middle.

Probably the right answer is somewhere in the newly added member functions - map::extract or map::merge. It would also be possible to find both the start and the end insertion position with just one call, if the declaration of std::map allowed heterogeneous lookup (equal_range with a specifically designed "range key" type). However that wouldn't help the linear O(N) erasure part.

#define CATCH_CONFIG_MAIN
#include "catch.hpp"


#include <map>
#include <limits>

template<typename K, typename V>
class interval_map {
public:
    std::map<K, V> m_map;


    // constructor associates whole range of K with val by inserting (K_min, val)
    // into the map
    interval_map(V const& val) {
        m_map.insert(m_map.end(), std::make_pair(std::numeric_limits<K>::lowest(), val));
    }

    // Assign value val to interval [keyBegin, keyEnd).
    // Overwrite previous values in this interval.
    // Conforming to the C++ Standard Library conventions, the interval
    // includes keyBegin, but excludes keyEnd.
    // 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))
            return;

        typename std::map<K, V>::iterator iterBegin; /*The new begin with val, can be begin()*/
        typename std::map<K, V>::iterator iterEnd;   /*the new end of val, can be end()*/

        auto lowerKeyBegin = m_map.lower_bound(keyBegin); //either end() or some iter whose key is not less than keyBegin. [1st O(logN)]
        auto upperKeyEnd = m_map.upper_bound(keyEnd); //some iter where keyEnd < key, or end()  [2nd O(logN)]
        auto prevKeyEnd = std::prev(upperKeyEnd);

        /*
        The next interval of the new interval starts at keyEnd if the previous value at keyEnd differed from val
        */
        if (!(prevKeyEnd->second == val))
        {
            // prevKeyEnd is either less than the new end we are inserting, or the same (no update to avoid copying from erased node)
            if (!(prevKeyEnd->first < keyEnd) && !(keyEnd < prevKeyEnd->first))
                iterEnd = prevKeyEnd;
            else
                iterEnd = m_map.insert_or_assign(upperKeyEnd, keyEnd, prevKeyEnd->second);
        }
        else
        {
            iterEnd = upperKeyEnd;
        }

        /*
        The new interval starts at keyBegin if the would-be previous interval has a different value.
        Previous interval is either a key in the map less than keyBegin, or non-existent when lower_bound is m_map.begin()
        The new interval's start is merged with previous interval, if the previous interval has the same value.
        */
        if (lowerKeyBegin != m_map.begin())
        {
            auto prevIter = std::prev(lowerKeyBegin); //safe when end(), because we always have at least one value
            if (!(prevIter->second == val))
            {
                iterBegin = m_map.insert_or_assign(lowerKeyBegin, keyBegin, val);
            }
            else iterBegin = prevIter;
        }
        else
        {
            iterBegin = m_map.insert_or_assign(lowerKeyBegin, keyBegin, val);
        }

        /*
        Erase all keys between the new begin and end (excluding) so that there is only one value after iterBegin
        This is fine when iterEnd is end()
        */
        {
            auto nextIterOfBegin = std::next(iterBegin);//somehow msvc doesn't support if-initialization
            if (nextIterOfBegin != m_map.end())
            {
                //I would be very interested in a smarter way to get rid of this part without additional storage ...
                m_map.erase(nextIterOfBegin, iterEnd); 
            }
        }

        ////debug - check canonical
        //for (auto iter = m_map.begin(); iter != m_map.end(); ++iter)
        //{
        //  auto next = std::next(iter);
        //  if (next != m_map.end() && iter->second == next->second)
        //  {
        //      throw;
        //  }
        //}
    }

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

// Many solutions we receive are incorrect. Consider using a randomized test
// to discover the cases that your implementation does not handle correctly.
// We recommend to implement a test function that tests the functionality of
// the interval_map, for example using a map of unsigned int intervals to char.

struct TestKeyType
{
    unsigned int val;
    constexpr TestKeyType(unsigned int val) : val(val) {}
    constexpr bool operator<(const TestKeyType& other) const { return val < other.val; }
};

namespace std {
    template<> class numeric_limits<TestKeyType> {
    public:
        static constexpr TestKeyType lowest() { return TestKeyType(numeric_limits<unsigned int>::lowest()); }
        //static constexpr TestKeyType lowest() { return TestKeyType(-250); }
    };
}

using TestValueType = char;

struct TestFloatKeyType
{
    float val;

    TestFloatKeyType() = default;

    TestFloatKeyType(float val) : val(val) {}
    bool operator< (TestFloatKeyType other) const
    {
        return other.val - val > 1.e-4f;
    }
};

namespace std {
    template<> class numeric_limits<TestFloatKeyType> {
    public:
        static TestFloatKeyType lowest() { return TestFloatKeyType(numeric_limits<float>::lowest()); }
    };
}

TEST_CASE("EmptyRange")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(3, 3, 'B');
    REQUIRE(m.m_map.count(3) == 0);

    m.assign(3, 2, 'B');
    REQUIRE(m.m_map.count(2) == 0);
    REQUIRE(m.m_map.count(3) == 0);
}


TEST_CASE("TrivialRange")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(1, 10, 'B');
    REQUIRE(m[0] == 'A');
    for (int i = 1; i < 10; i++)
    {
        REQUIRE(m[i] == 'B');
    }
    REQUIRE(m[10] == 'A');
}

TEST_CASE("TrivialTwoRange")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(1, 3, 'B');
    m.assign(6, 8, 'C');
    REQUIRE(m[0] == 'A');
    REQUIRE(m[1] == 'B');
    REQUIRE(m[2] == 'B');
    REQUIRE(m[3] == 'A');
    REQUIRE(m[4] == 'A');
    REQUIRE(m[5] == 'A');
    REQUIRE(m[6] == 'C');
    REQUIRE(m[7] == 'C');
    REQUIRE(m[8] == 'A');
}

TEST_CASE("OverwriteLowest")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(std::numeric_limits<TestKeyType>::lowest(), 10000, 'B');
    REQUIRE(m[0] == 'B');
    REQUIRE(m[9999] == 'B');
    REQUIRE(m[10000] == 'A');
}

TEST_CASE("Merge")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(std::numeric_limits<TestKeyType>::lowest(), 10, 'B');
    m.assign(10, 20, 'B');
    REQUIRE(m[0] == 'B');
    REQUIRE(m[10] == 'B');
    REQUIRE(m[19] == 'B');
    REQUIRE(m[20] == 'A');
}

TEST_CASE("FloatKey")
{
    interval_map<TestFloatKeyType, TestValueType> m('A');
    m.assign(1.f, 5.f, 'B');
    REQUIRE(m[0.f] == 'A');
    REQUIRE(m[.999999999f] == 'B');
    REQUIRE(m[1.f] == 'B');
    REQUIRE(m[4.999f] == 'B');
    REQUIRE(m[5.f] == 'A');

}

TEST_CASE("OverlappingRangeComplete")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(3, 5, 'B');
    m.assign(1, 6, 'C');
    REQUIRE(m[0] == 'A');
    REQUIRE(m[1] == 'C');
    REQUIRE(m[2] == 'C');
    REQUIRE(m[3] == 'C');
    REQUIRE(m[4] == 'C');
    REQUIRE(m[5] == 'C');
    REQUIRE(m[6] == 'A');
}

TEST_CASE("OverlappingRangeInner")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(1, 6, 'C');
    m.assign(3, 5, 'B');
    REQUIRE(m[0] == 'A');
    REQUIRE(m[1] == 'C');
    REQUIRE(m[2] == 'C');
    REQUIRE(m[3] == 'B');
    REQUIRE(m[4] == 'B');
    REQUIRE(m[5] == 'C');
    REQUIRE(m[6] == 'A');
}

TEST_CASE("OverlappingRangeSmallToLarge")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(1, 5, 'B');
    m.assign(3, 6, 'C');
    REQUIRE(m[0] == 'A');
    REQUIRE(m[1] == 'B');
    REQUIRE(m[2] == 'B');
    REQUIRE(m[3] == 'C');
    REQUIRE(m[4] == 'C');
    REQUIRE(m[5] == 'C');
    REQUIRE(m[6] == 'A');
}

TEST_CASE("OverlappingRangeLargeToSmall")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(3, 6, 'C');
    m.assign(1, 5, 'B');
    REQUIRE(m[0] == 'A');
    REQUIRE(m[1] == 'B');
    REQUIRE(m[2] == 'B');
    REQUIRE(m[3] == 'B');
    REQUIRE(m[4] == 'B');
    REQUIRE(m[5] == 'C');
    REQUIRE(m[6] == 'A');
}

TEST_CASE("ExtendingRangeBegin")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(3, 5, 'B');
    m.assign(1, 4, 'B');
    REQUIRE(m[0] == 'A');
    REQUIRE(m[1] == 'B');
    REQUIRE(m[2] == 'B');
    REQUIRE(m[3] == 'B');
    REQUIRE(m[4] == 'B');
    REQUIRE(m[5] == 'A');
}

TEST_CASE("ExtendingRangeEnd")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(1, 5, 'B');
    m.assign(3, 6, 'B');
    REQUIRE(m[0] == 'A');
    REQUIRE(m[1] == 'B');
    REQUIRE(m[2] == 'B');
    REQUIRE(m[3] == 'B');
    REQUIRE(m[4] == 'B');
    REQUIRE(m[5] == 'B');
    REQUIRE(m[6] == 'A');
}

TEST_CASE("ExtendingRangeBothBeginEnd")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(2, 3, 'B');
    m.assign(1, 5, 'B');
    REQUIRE(m[0] == 'A');
    REQUIRE(m[1] == 'B');
    REQUIRE(m[2] == 'B');
    REQUIRE(m[3] == 'B');
    REQUIRE(m[4] == 'B');
    REQUIRE(m[5] == 'A');
}

TEST_CASE("OverwriteEndValueSafety")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(2, 5, 'B');
    m.assign(5, 8, 'C');
    m.assign(4, 5, 'A');
}

TEST_CASE("ReusingExistingRangeBothBeginEnd")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(1, 5, 'B');
    m.assign(2, 3, 'B');
    REQUIRE(m[0] == 'A');
    REQUIRE(m[1] == 'B');
    REQUIRE(m[2] == 'B');
    REQUIRE(m[3] == 'B');
    REQUIRE(m[4] == 'B');
    REQUIRE(m[5] == 'A');
}

TEST_CASE("ReusingEnd")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(1, 5, 'B');
    m.assign(4, 6, 'A');
    REQUIRE(m[0] == 'A');
    REQUIRE(m[1] == 'B');
    REQUIRE(m[2] == 'B');
    REQUIRE(m[3] == 'B');
    REQUIRE(m[4] == 'A');
    REQUIRE(m[5] == 'A');
}

TEST_CASE("RestoringInitial")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(1, 5, 'B');
    m.assign(1, 5, 'A');
    REQUIRE(m[0] == 'A');
    REQUIRE(m[1] == 'A');
    REQUIRE(m[2] == 'A');
    REQUIRE(m[3] == 'A');
    REQUIRE(m[4] == 'A');
    REQUIRE(m[5] == 'A');
}

TEST_CASE("RestoringInitial2")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(1, 5, 'B');
    m.assign(0, 7, 'A');
    REQUIRE(m[0] == 'A');
    REQUIRE(m[1] == 'A');
    REQUIRE(m[2] == 'A');
    REQUIRE(m[3] == 'A');
    REQUIRE(m[4] == 'A');
    REQUIRE(m[5] == 'A');
}

TEST_CASE("VeryComplex")
{
    interval_map<TestKeyType, TestValueType> m('A');
    m.assign(3, 6, 'B');
    m.assign(2, 5, 'C');
    m.assign(4, 7, 'A');

    REQUIRE(m[1] == 'A');
    REQUIRE(m[2] == 'C');
    REQUIRE(m[3] == 'C');
    REQUIRE(m[4] == 'A');
    REQUIRE(m[5] == 'A');
    REQUIRE(m[6] == 'A');
    REQUIRE(m[7] == 'A');
}

Answer 2

You are requiring your types to be default constructible:

std::pair<K,V> beginExtra;
std::pair<K,V> endExtra;

That is probably the source of the complaint.