Why is C still that more popular than C++!?

[frek]

Please delete this thread

[dutch]

You must adhere to the specification of the key and value type given above.

The spec says the keys are "less-than comparable via operator<" and do not implement any other operations. You are using >=. You need to use !(keyBegin < keyEnd) instead.

And the spec seems clear enough to me. :-)
EDIT: re-reading it, one thing that is not clear is whether or not keyEnd should be included or not in the assigned range. It kind of seems like it should be included. You could try it both ways.
EDIT2: reading the given code's comments it is clear that keyEnd is not included in the interval.

[frek]

Ow shit! My bad. Do you mean my solution was correct but was rejected only because of that tiny mistake?

Had you seen that data structure before?

[dutch]

I haven't tested your solution but since you say you're unclear as to the spec I'd bet money it's not correct.
Not a lot of money, of course.
But I'd put fifty on it. :-)

Had you seen that data structure before?

I've seen very similar ideas before.

[frek]

Fifty dollars or Euros? Hhhhhhh

Kidding aside, it's important to me to know if the solution is correct or not. I added a minimal main() function to run the code and as I said it worked without errors.

int main() {

system ("pause");
return 0;

} 

[dutch]

I thought you said there's a website to run it on.
What does it say?
Do I owe you 50 dollars?

[frek]

The webpage is temporary I think, dedicated to that assignment, in a limited time space. I lost it! :( :(
For the compilation step, it, too, said: "Looks good!" or something like that. Their compiler reported no error. There was, however, a button to submit the code, when I pressed that the above message "you must adhere to ..." turned up!
I reviewed the code a couple of times. It looks fine to the task, not sure of course. But it's important for me to know.

[dutch]

The webpage is temporary I think

Strange. Oh well.

How could I possibly tell you if it's correct?
It depends on your interpretation of the instructions.
There's a very good chance it's incorrect given the warning at the end of the given code.
I would still literally bet money it's wrong and would almost certainly win.
And I haven't even looked closely at your code.

it's important for me to know.

Well, we'll never know now.

[frek]

Thank you

[dutch]

The answer was not accepted, it's obvious, because of that mistake I made.

I'm obviously not talking about that.
All I'm saying is that I would bet 50 dollars that your current code is incorrect.
You make a bet when you feel the odds are on your side, not when you are 100 percent certain.
I feel the odds are very much on my side for the reasons I've already given.
It's strange that you would be so confident when you are not even sure of your interpretation of the assignment.
And I don't even see a test function.
Did you even test it?
It's madness!

[dutch]

As an example, I feel that the following test code:

int main()
{
    interval_map<int,char> m('A');
    m.assign(1, 3, 'B');
    for (int i = -2; i <= 5; ++i)
        std::cout << std::setw(2) << i << ' ' << m[i] << '\n';
}

should yield this result:

-2 A
-1 A
 0 A
 1 B
 2 B
 3 A
 4 A
 5 A

[frek]

All I'm saying is that I would bet 50 dollars that your current code is incorrect.

What part of it is incorrect? I merely aim at learning.

I didn't understand the assignment description well enough, but the comments on line 13 to 18, as I said, are very vivid and using that I step forward to design the assign function.

let me paraphrase my question: if you evaluate the solution (the assign function) for that assignment - apart from that if mistake - is it correct? If not why? Where else have I made a mistake?

[dutch]

Look at my last post.
Run the code.
Do you get that result?
If not, then in my opinion your code is incorrect.

[dutch]

Another example of a test:

// print_map needs to be a friend of interval_map:
//   friend void print_map(const interval_map<K,V>& m);

void print_map(const interval_map<int,char>& m)
{
    bool comma = false;
    std::cout << '{';
    for (const auto& p: m.m_map)
    {
        if (comma) std::cout << ',';
        std::cout << '{' << p.first << ',' << p.second << '}';
        comma = true;
    }
    std::cout << "}\n";
}

void print(const interval_map<int,char>& m, int lo, int hi)
{
    print_map(m);
    for (int i = lo; i <= hi; ++i)
        std::cout << std::setw(2) << i << ' ' << m[i] << '\n';
    std::cout << "\n\n";
}

int main()
{
    interval_map<int,char> m('A');
    m.assign(1, 3, 'B');
    m.assign(4, 6, 'C');
    m.assign(7, 9, 'D');
    print(m, 0, 9);
    m.assign(2, 8, 'E');
    print(m, 0, 9);
}

{{1,B},{3,A},{4,C},{6,A},{7,D},{9,A}}
 0 A
 1 B
 2 B
 3 A
 4 C
 5 C
 6 A
 7 D
 8 D
 9 A

{{1,B},{2,E},{8,D},{9,A}}
 0 A
 1 B
 2 E
 3 E
 4 E
 5 E
 6 E
 7 E
 8 D
 9 A

Please delete this thread

Why?
And it's a total dick move to delete your post content.
You even change the title of the thread!

Anyway, you need to learn how to test your code.

[dutch]

This was the original content that frek overwrote in the first post.
I don't remember what the original thread title was.


interval_map<K,V> is a data structure that associates keys of type K with values of type V. It is designed to be used efficiently in situations where intervals of consecutive keys are associated with the same value. 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. For more information on std::map, you may refer to cppreference.com.

Each key-value-pair (k,v) in interval_map<K,V>::m_map means that the value v is associated with all keys from k (including) to the next key (excluding) in m_map. The member interval_map<K,V>::m_valBegin holds the value that is associated with all keys less than the first key in m_map.

Example: let M be an instance of interval_map<int,char> where

M.m_valBegin=='A',
M.m_map=={ (1,'B'), (3,'A') },
then M represents the mapping
...
-2 -> 'A'
-1 -> 'A'
0 -> 'A'
1 -> 'B'
2 -> 'B'
3 -> 'A'
4 -> 'A'
5 -> 'A'
...
The representation in the std::map must be canonical, that is, consecutive map entries must not contain the same value: ..., (3,'A'), (5,'A'), ... is not allowed. Likewise, the first entry in m_map must not contain the same value as m_valBegin. Initially, the whole range of K is associated with a given initial value, passed to the constructor of the interval_map<K,V> data structure.

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

#include <map>

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

        // PUT YOUR CODE HERE

    }

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

// 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 int intervals to char.  

This was his attempt:

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 lower bound of keyBegin to see if the container includes the keyBegin
    auto beginIter = m_map.lower_bound(keyBegin);

    if (beginIter->first != keyBegin) {
        // the container doesn't already contain an element with an 
       // equivalent key, so insert the element into the container
        beginIter = m_map.insert(beginIter, std::pair<K, V>(keyBegin, val));

        // The element at begin_iter already has the correct the value 
        ++beginIter;
    }

    // Search for the lower bound of keyEnd and use it as the 
    // exclusive upper boundary 
    auto endIter = m_map.lower_bound(keyEnd);

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

[dutch]

This little fucker says that deleting his post content and changing the thread title to something entirely different isn't abusing the site. What an asshole!

[z05DSL3A]

dutch,
Simply don't send him any help in the future...there's no need to be abusive it puts others off.