FreeOrion

cami wrote:std::list can be merged and split in constant time using std::list<>::splice().

FWIW, this is true for GNU, but not MS. In c++11's STL, it will not be true for any conforming implementation.

Well, I hoped the emote showed this was a half-joke. I didn't plan to keep the adapter code, but I planned to make ObjectSet a real class adhering the Multiple Simple Associative Container interface (but not running time constraints). I could also choose names suggesting the real computation costs ...

In fact, I politely refuse to inline all the adapter code manually :þ I'm convinced it's futile, error-prone and hard to maintain. http://www.freeorion.org/forum/download/file.php?mode=view&id=1092 I think we have different views on what maintainability means. I understand that you don't want t...

Looking at those numbers again. it seems that all of the difference between list and vector is coming from insert and erase, not copying. I also notice that your adapter is doing a lot more than "push_back()" and "*it = back(); pop_back()", respectively. This leads me to believe ...

That's really interesting that list is faster than vector. I wonder if a few calls to vector::reserve() might fix that? Do you have any idea what the average size of these vectors is?

If that's too much trouble to investigate, I'd settle for a std::list implementation without the set adapter.

Ok, I assume this means you want std::vector hard-coded. Yes. This will require a lot more work. In the meantime, here's my experimental results (gzipped, 3.2MB) using an adaptor on std::list : Can you time it as below with std::vector instead of std::list, using the swap-with-back()-before-pop_bac...

KISS. Let's use vector everywhere.

I think there might be a problem with the present WithinhStarlaneJumps code. In Universe::JumpDistance why is 1 subtracted from the number looked up in m_system_jumps? With it there, I get natives in the wrong places, and few elsewhere, and without it, things look correct... To be honest, I don't k...

All the more reason for us to have regression tests for ValueRefs, Conditions, and Effects.

Carsten, now that we've talked this through a bit, would you care to work on a patch?

Even better.

We might want to consider a spatially-efficient lookup table of some kind for the WithinDistance condition in particular. Such a thing might have all the problems Geoff mentioned in another thread about keeping caches in sync with the main data structures.

Hmm, well I'm definitely wrong about Not. I still feel like we need both sets to be kept in sync. I don't remember the exact reason why, but I looked into doing something really similar to what you've proposed a few weeks ago, and I concluded at the time that it was not currently possible. I may hav...

ConditionBase::Eval doesn't erase by address or ID; it erases by iterator, so there's no need to be able to erase quickly by ID or address: for ( ; it != end_it; ) { ObjectSet::iterator temp = it++; bool match = Match(ScriptingContext(parent_context, *temp)); if ((search_domain == MATCHES &&...

Nevertheless, there is no need to replace the current mechanism, we just shouldn't enforce it. I don't quite understand this sentence, but if it means you don't think we need to maintain both lists as long as each Condition does not know if it will be negated by being nested inside a Not, I think y...