boostorg / boostorg/icl

interval_map::operator-= leaves phantom covering intervals

Open
#55 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
16
Forks
50
PR merge metrics
No merged PRs in 30d

Description

## Summary

After building up `interval_map` 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

```cpp
#include

#include
#include

int main() {
boost::icl::interval_map m;
const auto big = boost::icl::interval::closed("key", "kez");
const auto point = boost::icl::interval::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 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

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.