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 #11685 is a reply to message #11684]

Fri, 21 September 2007 14:51

sergei is currently offline

sergei
Messages: 94
Registered: September 2007

Member

luzr wrote on Fri, 21 September 2007 14:30

sergei wrote on Fri, 21 September 2007 07:51

When I said sorted containers what I needed is not find/unique (hash could do that too), but to iterate over all elements, from smallest ro largest / reverse. You say operator[] is slow. Would such iteration be slower than in set, or not?

Not actually measured, but iterating through link structures tends to be slow with modern CPUs, so I would say that the linear iteration would be about the same.

That said, it is a bit surprising that you would prefer sorted container only to get items in order. Using Index (or generally a hash_map) and Sorting the result beats this in most cases.

For me, the main advantage of such container would be the lower and upper bounds.

Quote:

I don't know how allocators work, but what have you done to get it faster than default? Some kind of buffering to allocate once for several small elements?

The algorithm of latest U++ allocator is described in the Core/srcimp.tpp.

Mirek

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?

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: Mon Jun 23 00:12:13 CEST 2025

Total time taken to generate the page: 0.04105 seconds