Overview
Examples
Screenshots
Comparisons
Applications
Download
Documentation
Tutorials
Bazaar
Status & Roadmap
FAQ
Authors & License
Forums
Funding Ultimate++
Search on this site
Search in forums












SourceForge.net Logo
Home » Developing U++ » U++ Developers corner » A new container in works: Flex - fast insertion vector
Re: A new container in works: Flex - fast insertion vector [message #11674 is a reply to message #11672] Fri, 21 September 2007 01:52 Go to previous messageGo to previous message
sergei is currently offline  sergei
Messages: 94
Registered: September 2007
Member
luzr wrote on Fri, 21 September 2007 01:34

sergei wrote on Thu, 20 September 2007 18:44

Have you benched this against Array? Array should be better than Vector in insert/delete (and maybe other things) for large-sized elements (not int, something like large classes).


Sergei, I have designed Array, I am well aware about that Smile

But you can cheat the O numbers only to some degree. Both Array and Vector have basic insertion complexity O(n), while this new beast has something like O(sqrt(N)).

Note also that once you have base Flex implemented, adding ArrayFlex is trivial..

Mirek


O(sqrt(N))? Nice... Are there downsides vs. Vector for this container (besides slightly slower on small-sized containers)? And does it basically require moveable?

P.S. Are there any sorted containers in U++, like set/multiset/map/multimap? I prefer that over GetSortOrder.
 
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Previous Topic: New FileSel(elector).
Next Topic: GDI, and therefore, Draw performance on Vista
Goto Forum:
  


Current Time: Mon Jun 23 10:18:26 CEST 2025

Total time taken to generate the page: 0.03541 seconds