U++ forum: Welcome to the forum

Status & Roadmap

Authors & License

Funding Ultimate++

Search on this site

Search in forums

Home » Developing U++ » U++ Developers corner » A new container in works: Flex - fast insertion vector

Show: Today's Messages :: Show Polls :: Message Navigator
E-mail to friend

Return to the default flat view

Create a new topic

Submit Reply

Re: A new container in works: Flex - fast insertion vector [message #11687 is a reply to message #11685]

Fri, 21 September 2007 15:06

mirek is currently offline

mirek
Messages: 14261
Registered: November 2005

Ultimate Member

Quote:

Sorting would beat it for a static set. But would it, if the set was changing (adding/removing elements), and at any given time I might need the order? Add/remove is O(logn), iteration should be linear, and sorting would cause the iteration to become O(nlogn) (sort+iterate), unless add/remove maintains sort order. And even in the best case of flex, add/remove would be O(sqrtn), worse than O(logn), right?

That is correct,

- there is a bit more about O - something like "generic speed". Flex seems to be faster up to 160 elements (in fact, even sorted U++ Vector is faster there than std::set).

- I believe I do a lot of programming, yet I never had encountered a problem that would require continual sorted iteration.

(BTW, I have another idea of container, something much more traditional, basically sorted variant of Index based on tree implemention; with method GetNextSorted that returns the index of next element in sequence. Given my experience with Index v.s. node based hashmap, I dare to say that such linearized tree implementation will be faster than node based.)

Report message to a moderator

Send a private message to this user

[Message index]

		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

Previous Topic:	New FileSel(elector).
Next Topic:	GDI, and therefore, Draw performance on Vista

Goto Forum:

-=] Back to Top [=-

[ Syndicate this forum (XML) ] [

] [

PDF

]

Current Time: Sun Jun 22 18:14:12 CEST 2025

Total time taken to generate the page: 0.03415 seconds