How to set an interval to std::map [closed]

Question

This code belongs to a contest. I tried to apply the range of data to a std::map. The contest system however warns me that the implementation of the assign function is not valid. I don't know which part of the code is written incorrectly, hence the system doesn't reveal any details except that the implementation is erroneous.

---

Edit: I also added the test class that I used for testing the interval_map class. I tried to test every possible aspect of what could possibly go wrong. The test runs without any problem.

        void assign(unsigned char first, unsigned char last, unsigned char value) 
        {
            test();

            interval_map::assign(first, last, value);
                for (int i = first; i < last; ++i)
                    vector_cont[i] = value;

            test();
        }
```

Answer 1

Quite frankly it seems that you did not do what was asked from you.

The text above assign gives you the requirements

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

So you have to find all elements in the map that are in the range [keyBegin, keyEnd) and assign val to them. Then you should insert keyBegin and keyEnd with the value val into the map.

Actually you are quite close to what was asked with the calls to lower_bound

    void assign(K const& keyBegin, K const& keyEnd, V const& val) {
        // keyBegin < keyEnd indicates an empty interval, so the function simply returns
        if (!(keyBegin < keyEnd))
            return;

        ....
    }

This is already a problem as the comment is incorrect. It should read keyEnd < keyBegin

        auto begin_lower_iter = m_map.lower_bound(keyBegin);
        auto end_upper_iter = m_map.upper_bound(keyEnd);

The first call is obviously correct. However, the second call is the wrong one. upper_bound returns the first element that is greater than the key. Now consider if keyEnd is in the map. As the interval is half opened you would have to decrement twice in that case and once if it is not in the map.

Rather than that you can simply use lower_bound here too

        auto begin_iter = m_map.lower_bound(keyBegin);
        auto end_iter = m_map.lower_bound(keyEnd);

Now we have to consider the bounds. First you should check, whether keyBegin is already in the map. Otherwise you should insert it so that the left boundary is inclusive. Note that in that case we can use begin_iter as a hint so that the complexity is an amortized constant

        if (begin_iter->first != keyBegin) {
            begin_iter = m_map.insert(begin_iter, val);
            // The element at begin_iter already has the correct value so increment 
            ++begin_iter;
        }

It is slightly different for the upper boundary, as that is exclusive. As far as i understand it, that means that you should insert an element with the value the interval had previously so that it is the inclusive left border of the new interval.

If end_iter is at keyEnd it already has the correct value and we do not have to do anything. However if it is not in the map, then we have to insert the value of the previous element at position keyEnd

        if (end_iter->first != keyEnd) {
            V const& oldVal = std::prev(end_iter, 1)->second;  
            end_iter = m_map.insert(end_iter, oldVal);
        }

Now to a completely different topic. As you might have seen insert returns an updated iterator. While there is no iterator invalidation in std::map,i would not risk it. So the insertion should happen right after you get the iterator.

        auto begin_iter = m_map.lower_bound(keyBegin);
        if (begin_iter->first != keyBegin) {
            begin_iter = m_map.insert(begin_iter, val);
            // The element at begin_iter already has the correct value so 
            ++begin_iter;
        }

        auto end_iter = m_map.lower_bound(keyEnd);
        if (end_iter->first != keyEnd) {
            V const& oldVal = std::prev(end_iter, 1)->second;  
            end_iter = m_map.insert(end_iter, oldVal);
        }

Also this is still not correct. Lets assume begin_iter was not less that the first element in the map smaller than keyEnd. In that case we would have overwritten the original value of the -larger- interval. Therefore, the insertion of the upper bound needs to happen first.

Now that we handeled the borders, we should update the elements int the range

        while(begin_iter != end_iter) {
            begin_iter->second = val;
            ++begin_iter;
        }

Finally, there is still an elephant in the room. While the whole file seems to be not fully consistent, the arguments to the function are camelCase. Yet you named your variables using snake_case. For me that is already a minus as you do not adopt to the existing codebase and inconsistent naming is a constant source of confusion and a huge drain on mental capacity.

So lets put it together

    void assign(K const& keyBegin, K const& keyEnd, V const& val) {
        // keyBegin < keyEnd indicates an empty interval, so the function simply returns
        if (!(keyBegin < keyEnd)) {
            return;
        }

        // Search for the upper bound and if necessary include a border element
        // with the value of the old interval
        auto endIter = m_map.lower_bound(keyEnd);
        if (endIter->first != keyEnd) {
            // As the intervals are half open we need to take the value of the left element and insert it at keyEnd 
            V const& oldVal = std::prev(endIter, 1)->second;  
            endIter = m_map.insert(endIter, oldVal);
        }

        // Search for the lower bound and if necessary include the element
        auto beginIter = m_map.lower_bound(keyBegin);
        if (beginIter->first != keyBegin) {
            beginIter = m_map.insert(beginIter, val);
            // The element at begin_iter already has the correct value so 
            ++beginIter;
        }

        // Update the values within the range [beginIter, endIter)
        while(beginIter != endIter) {
            beginIter->second = val;
            ++beginIter;
        }
    }

Answer 2

It is possible the interview failed because of the 4th line in the code:

using namespace std;

Code such as a template class will generally be in a header file, and it is very bad practice to have the using namespace std; within a header file, it breaks all the reasons for having namespaces. What happens if someone wants to use this class as a base class but needs to write special cin and cout overloads, or overload any of the library functions provided by namespace std?

In general professions will never default to the std namespace. Namespaces are used to prevent collisions of functions see this stackoverflow question.

The second problem with using namespace std is that it isn't necessary, the code compiles without it.