interval_map::operator-= leaves phantom covering intervals

[chuzhe-as-a-dev]

Summary

After building up interval_map<std::string, std::size_t> with one += over a large interval and a second += over a singleton inside it, subtracting the large interval with -= produces an end state that extends beyond where any live count remains. Each subsequent -= that matches a prior += exactly still leaves the map non-empty.

Minimal reproducer

#include <boost/icl/interval_map.hpp>
                                                                                                                                                              
#include <iostream>
#include <string>                                                                                                                                             
                                                                    
int main() {
    boost::icl::interval_map<std::string, std::size_t> m;
    const auto big   = boost::icl::interval<std::string>::closed("key", "kez");
    const auto point = boost::icl::interval<std::string>::closed("key", "key");                                                                               
                                                                                                                                                              
    auto dump = [&](const char* step) {                                                                                                                       
        std::cout << step << "  ->  ";                                                                                                                        
        if (m.empty()) std::cout << "{}";                                                                                                                     
        for (const auto& [iv, v] : m) {
            std::cout << (boost::icl::is_left_closed(iv.bounds()) ? '[' : '(')                                                                                
                      << boost::icl::lower(iv) << ',' << boost::icl::upper(iv)                                                                                
                      << (boost::icl::is_right_closed(iv.bounds()) ? ']' : ')')                                                                               
                      << ":" << v << ' ';                                                                                                                     
        }                                                                                                                                                     
        std::cout << '\n';                                                                                                                                    
    };                                                                                                                                                        
 
    m += std::pair{big,   std::size_t{1}};  dump("+= [key,kez]:1");                                                                                           
    m += std::pair{point, std::size_t{1}};  dump("+= [key,key]:1");                                                                                           
    m -= std::pair{big,   std::size_t{1}};  dump("-= [key,kez]:1");                                                                                           
    m -= std::pair{point, std::size_t{1}};  dump("-= [key,key]:1");                                                                                           
}                                                                                                                                                             

Compile:

clang++ -std=c++17 -I <boost-include-dir> repro.cc -o repro && ./repro

Expected output

+= [key,kez]:1  ->  [key,kez]:1
+= [key,key]:1  ->  [key,key]:2 (key,kez]:1                                                                                                                   
-= [key,kez]:1  ->  [key,key]:1
-= [key,key]:1  ->  {}                                                                                                                                        

After every point in [key,kez] is decremented by 1:

• point key: 2 − 1 = 1 (kept)
• (key,kez]: 1 − 1 = 0 (removed)

Leaving just [key,key]:1. The final balanced -= should empty the map.

Actual output

+= [key,kez]:1  ->  [key,kez]:1
+= [key,key]:1  ->  [key,key]:2 (key,kez]:1
-= [key,kez]:1  ->  [key,kez]:1                                                                                                                               
-= [key,key]:1  ->  (key,kez]:1

After the third step the map covers [key,kez] again with count 1 — the point kez, which had count 1 before the subtract and should be gone, is still mapped. The leftover (key,kez]:1 after the fourth step is purely phantom: every += has been matched by a -= with the exact same interval and value.

Environment

• Boost: 1.88.0 and 1.90.0 (both reproduce identically)
• Compiler: Homebrew Clang 22.1.3, -std=c++17 -O0 and -std=c++17 -O3 -DNDEBUG
• Standard library: libc++
• OS: macOS 15.7.4, arm64