Barend, there are a couple of problems with your test.
The space complexity is only quadratic in the case where the map's value types for overlapping intervals are all stored. OK, I see. But you didn't mention that in your review. So yes, I understand, if you store names to the intervals as sets, and split an interval each time, you will get a fragmented map of fragmented sets. However, I did this at start, so read on. Looking at your example code:
typedef itl::interval_map<int, int> map; map livetimes; ... livetimes += std::make_pair(itl::interval<int>(p.indi.birth.date.year, death_date), 1);
You are just storing the number of people living on any particular date. Try changing your code to record all of the names, e.g. something like: Yes, I did this in my review. The first version of my program listed
Hi Phil, like this: typedef boost::itl::set<std::string> itl_set_string; typedef boost::itl::interval_map<int, itl_set_string> itl_map; (...) itl_set_string person; person.insert(p.indi.name); int death_date = p.indi.death.date.hasdate ? p.indi.death.date.year : 9999; livetimes.add(std::make_pair( boost::itl::interval<int>::rightopen(p.indi.birth.date.year, death_date), person)); (...) itl_set_string const& who = it->second; stream << when.first() << " - " << when.upper() << " : " << who.size() << std::endl; But I then realized that this did too much, because I only wanted to know how much persons are alive in what period. So I did a second implementation and timing. Also this first test did have no noticeable delay. It is subsecond, and I did also write the names of all these persons in this test which should not be timed, so it is not problematic.
typedef itl::interval_map<int, string> map; map livetimes; .. livetimes += std::make_pair(itl::interval<int>(p.indi.birth.date.year, death_date), p.name);
More fundamentally, you are taking my observation that it has poor space complexity and then measuring the execution time. This is obviously flawed, as time and space complexity are different things.
but to do so it needs worst-case O(N2) space and I think it needs O(N2 log N) time to build that structure. so I measured time and, admitted, I didn't measure space. I only observe
You mentioned the time as well: that it runs fast in the example you are giving. Regards, Barend