FWIW, this is true for GNU, but not MS. In c++11's STL, it will not be true for any conforming implementation.cami wrote:std::list can be merged and split in constant time using std::list<>::splice().
Search found 1062 matches
- Fri Oct 07, 2011 3:40 pm
- Forum: Programming
- Topic: [RESOLVED] Condition::Contains implementation
- Replies: 115
- Views: 13118
Re: Condition::Contains implementation
- Fri Oct 07, 2011 3:35 pm
- Forum: Programming
- Topic: [RESOLVED] Condition::Contains implementation
- Replies: 115
- Views: 13118
Re: Condition::Contains 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 ...
- Fri Oct 07, 2011 1:33 pm
- Forum: Programming
- Topic: [RESOLVED] Condition::Contains implementation
- Replies: 115
- Views: 13118
Re: Condition::Contains implementation
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...
- Fri Oct 07, 2011 2:16 am
- Forum: Programming
- Topic: [RESOLVED] Condition::Contains implementation
- Replies: 115
- Views: 13118
Re: Condition::Contains implementation
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 ...
- Fri Oct 07, 2011 2:07 am
- Forum: Programming
- Topic: [RESOLVED] Condition::Contains implementation
- Replies: 115
- Views: 13118
Re: Condition::Contains implementation
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.
If that's too much trouble to investigate, I'd settle for a std::list implementation without the set adapter.
- Wed Oct 05, 2011 7:00 pm
- Forum: Programming
- Topic: [RESOLVED] Condition::Contains implementation
- Replies: 115
- Views: 13118
Re: Condition::Contains implementation
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...
- Wed Oct 05, 2011 1:01 pm
- Forum: Programming
- Topic: [RESOLVED] Condition::Contains implementation
- Replies: 115
- Views: 13118
Re: Condition::Contains implementation
KISS. Let's use vector everywhere.
- Wed Oct 05, 2011 1:01 pm
- Forum: Programming
- Topic: [PATCH] WithinStarlaneJumps implementation
- Replies: 78
- Views: 8358
Re: [PATCH] WithinStarlaneJumps implementation
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...
- Tue Oct 04, 2011 9:54 pm
- Forum: Programming
- Topic: [PATCH] WithinStarlaneJumps implementation
- Replies: 78
- Views: 8358
Re: [PATCH] WithinStarlaneJumps implementation
All the more reason for us to have regression tests for ValueRefs, Conditions, and Effects.
- Tue Oct 04, 2011 9:06 pm
- Forum: Programming
- Topic: [RESOLVED] Condition::Contains implementation
- Replies: 115
- Views: 13118
Re: Condition::Contains implementation
Carsten, now that we've talked this through a bit, would you care to work on a patch?
- Tue Oct 04, 2011 9:06 pm
- Forum: Programming
- Topic: [RESOLVED] Condition::Contains implementation
- Replies: 115
- Views: 13118
Re: Condition::Contains implementation
Even better.
- Tue Oct 04, 2011 9:05 pm
- Forum: Programming
- Topic: WithinDistance Implementation
- Replies: 4
- Views: 742
Re: WithinDistance Implementation
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.
- Tue Oct 04, 2011 9:01 pm
- Forum: Programming
- Topic: [RESOLVED] Condition::Contains implementation
- Replies: 115
- Views: 13118
Re: Condition::Contains implementation
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...
- Tue Oct 04, 2011 7:59 pm
- Forum: Programming
- Topic: [RESOLVED] Condition::Contains implementation
- Replies: 115
- Views: 13118
Re: Condition::Contains implementation
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 &&...
- Tue Oct 04, 2011 7:56 pm
- Forum: Programming
- Topic: [RESOLVED] Condition::Contains implementation
- Replies: 115
- Views: 13118
Re: Condition::Contains implementation
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...