C++区间映射（Interval Map）assign方法实现错误排查求助

Let's break down the issues in your code that are likely causing the test failures, even if your self-test cases passed. First, let's recap the core requirement for assign(keyBegin, keyEnd, val): it should set all keys in [keyBegin, keyEnd) to val, while maintaining the interval map's invariant—no adjacent entries with the same value.

Key Issues in Your Code #

1. Undefined Behavior for Empty Maps #

Your code starts with:

auto nextInterval = --m_map.upper_bound(keyEnd);

If m_map is empty, upper_bound(keyEnd) returns end(), and decrementing end() is undefined behavior. This will crash or produce incorrect results in empty container scenarios.

2. Flawed Initialization of prevInterval #

You initialize prevInterval as the predecessor of nextInterval, which has no logical connection to keyBegin. This leads to incorrect handling of the interval containing keyBegin, especially when keyBegin is far from keyEnd. The correct approach is to directly locate the interval related to keyBegin using lower_bound or upper_bound.

3. Unchecked Iterator Decrements #

In multiple places (e.g., --prevInterval), you don't check if the iterator is at begin() before decrementing. This triggers undefined behavior when working with the first element of the map.

4. Broken Interval Merging Logic #

Your code fails to properly merge adjacent intervals with the same value after modification. For example, if the interval before keyBegin already has value val, your code doesn't merge it with the new interval, leaving redundant entries that violate the map's invariant.

5. Confused Interval Splitting Logic #

When splitting intervals at keyBegin or keyEnd, your logic for deciding when to split or skip is inconsistent. For example, when nextInterval->second == val, you increment nextInterval without considering whether the entire interval overlaps with [keyBegin, keyEnd), leading to incorrect erasure or retention of entries.

Corrected Implementation #

Here's a revised version of assign that fixes these issues, with comments explaining each step:

#include <map>
#include <iterator>

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

public:
    void assign(const K& keyBegin, const K& keyEnd, const V& val) {
        // Early exit if interval is invalid
        if (!(keyBegin < keyEnd)) {
            return;
        }

        // Step 1: Handle the right boundary (keyEnd)
        auto it_end = m_map.upper_bound(keyEnd);
        bool split_right = false;
        if (it_end != m_map.begin()) {
            auto it_end_prev = std::prev(it_end);
            if (it_end_prev->second != val) {
                // Split the interval if it overlaps keyEnd
                if (it_end_prev->first < keyEnd) {
                    it_end = m_map.emplace_hint(it_end, keyEnd, it_end_prev->second);
                    split_right = true;
                }
            } else {
                // Merge with existing val interval, move it_end left
                it_end = it_end_prev;
            }
        }

        // Step 2: Handle the left boundary (keyBegin)
        auto it_begin = m_map.lower_bound(keyBegin);
        bool split_left = false;
        if (it_begin != m_map.begin()) {
            auto it_begin_prev = std::prev(it_begin);
            if (it_begin_prev->second == val) {
                // Merge with existing val interval, use it as the start
                it_begin = it_begin_prev;
            } else {
                if (it_begin_prev->first < keyBegin) {
                    // Split the interval to insert the new val at keyBegin
                    it_begin = m_map.emplace_hint(it_begin, keyBegin, val);
                    split_left = true;
                } else {
                    // keyBegin matches an existing key, update its value
                    it_begin->second = val;
                    // Merge with previous if possible
                    if (it_begin != m_map.begin() && std::prev(it_begin)->second == val) {
                        m_map.erase(it_begin);
                        it_begin = std::prev(it_begin);
                    }
                }
            }
        } else {
            // Handle empty map or keyBegin is before the first key
            if (it_begin == m_map.end() || keyBegin < it_begin->first) {
                it_begin = m_map.emplace_hint(it_begin, keyBegin, val);
                split_left = true;
            } else {
                // keyBegin matches the first key, update its value
                it_begin->second = val;
            }
        }

        // Step 3: Erase all intervals between it_begin and it_end (they're covered by val)
        if (std::next(it_begin) != it_end) {
            m_map.erase(std::next(it_begin), it_end);
        }

        // Step 4: Merge with right interval if values match
        if (it_end != m_map.end() && it_end->second == val) {
            m_map.erase(it_end);
        }

        // Step 5: Merge with left interval if values match (only if we split left)
        if (split_left && it_begin != m_map.begin() && std::prev(it_begin)->second == val) {
            m_map.erase(it_begin);
        }
    }
};

Test Cases to Validate #

To ensure correctness, test these edge cases:

• Empty map: assign(1, 5, 10) should result in {1:10}
• Overwrite entire existing map: {1:2, 5:3} → assign(1, 10, 4) should result in {1:4}
• Merge adjacent same values: {1:5, 3:5, 7:5} → assign(2, 6, 5) should leave the map unchanged
• Split left interval: {1:2, 5:3} → assign(3, 6, 4) should result in {1:2, 3:4, 6:3}
• Split right interval: {1:2, 5:3} → assign(0, 3, 4) should result in {0:4, 3:2, 5:3}

内容的提问来源于stack exchange，提问作者Roman Maltsev