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 #11678 is a reply to message #11674] |
Fri, 21 September 2007 09:00   |
 |
mirek
Messages: 14261 Registered: November 2005
|
Ultimate Member |
|
|
sergei wrote on Thu, 20 September 2007 19:52 |
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 
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)?
|
Sure While operator[] is O(1), it is slower than both Vector::operator[] and Array::opertor[] (BTW, Array::[] is much slower than Vector::[] too).
Also, appending at the end can be slower too.
Quote: |
And does it basically require moveable?
|
I guess that "vector-flavor" will. In fact, I am considering to introduce up to 4 variants with varying characteristics.
Quote: |
P.S. Are there any sorted containers in U++, like set/multiset/map/multimap? I prefer that over GetSortOrder.
|
No. But that is definitely one of potential uses of this new container. I have already tried to implement sorted array with this and benchmarked it against set, for 160 000 String elements, "unique" operation is about 2.5x slower than with std::set, while find only scenario is even a bit faster. Note also that std::set was using U++ allocator in this test; with vendor allocators it would be slower.
Mirek
|
|
|
 |
|
A new container in works: Flex - fast insertion vector
By: mirek on Wed, 29 August 2007 19:00
|
 |
|
Re: A new container in works: Flex - fast insertion vector
By: unodgs on Wed, 29 August 2007 21:13
|
 |
|
Re: A new container in works: Flex - fast insertion vector
By: mirek on Wed, 29 August 2007 22:22
|
 |
|
Re: A new container in works: Flex - fast insertion vector
By: nasos_i on Thu, 20 September 2007 23:02
|
 |
|
Re: A new container in works: Flex - fast insertion vector
By: mirek on Thu, 20 September 2007 23:19
|
 |
|
Re: A new container in works: Flex - fast insertion vector
By: sergei on Fri, 21 September 2007 00:44
|
 |
|
Re: A new container in works: Flex - fast insertion vector
By: mirek on Fri, 21 September 2007 01:34
|
 |
|
Re: A new container in works: Flex - fast insertion vector
By: sergei on Fri, 21 September 2007 01:52
|
 |
|
Re: A new container in works: Flex - fast insertion vector
By: mirek on Fri, 21 September 2007 09:00
|
 |
|
Re: A new container in works: Flex - fast insertion vector
By: sergei on Fri, 21 September 2007 13:51
|
 |
|
Re: A new container in works: Flex - fast insertion vector
By: mirek on Fri, 21 September 2007 14:30
|
 |
|
Re: A new container in works: Flex - fast insertion vector
By: sergei on Fri, 21 September 2007 14:51
|
 |
|
Re: A new container in works: Flex - fast insertion vector
By: mirek on Fri, 21 September 2007 15:06
|
 |
|
Re: A new container in works: Flex - fast insertion vector
By: sergei on Fri, 21 September 2007 15:17
|
 |
|
Re: A new container in works: Flex - fast insertion vector
By: mirek on Fri, 21 September 2007 16:36
|
Goto Forum:
Current Time: Mon Jun 23 00:06:14 CEST 2025
Total time taken to generate the page: 0.04202 seconds
|