Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #11214

Re: Fast Container

Show all headers | View raw

On 11/2/2011 11:21 AM, Thomas Lehmann wrote:
> There are written so many articles but no article is really providing
> the answer I'm looking for.
>
> Given a scenario with 100000 data elements the day (500000 the week).
> Potential we might have 3000-5000 updates for individual elements
> each second.
>
> Imagine a filter that decides on each update the a data element will
> be added, updated or removed.
>
> The final container which is sorted by a user defined criteria must be
> able to handle this amount of data.
>
> Info: basically each value of that sorted container is a pointer to the
> real data.
>
> Final scope: we display the data in a table which provides index based
> positions (row)
>
> NOW, what is the right way to implement a fast container for this?
>
> Some of the problems I was confronted with:
> - Using a std::vector deletion/insertion is expensive, is it?
> - Using a std::set I have no index access. Or is there a way to handle this properly?
> - Somebody told me something about a weighted balanced tree as possible solution.
> - Somebody else told me to use standard containers only.

You didn't say whether the order of the objects in a container is 
important.  If you can define deletion from your custom vector as 
swapping with the last element and resizing by -1, it's fast.  Insertion 
at the end is not too bad, and causes reallocation only once in a while 
(when the vector grows past its capacity), and you can kind of control 
that by managing the capacity at "calm" times (shooter's rule: reload 
when you have a chance, don't wait 'til you're empty).

Also, consider std::deque, it's appends are even faster than vector's.

V
-- 
I do not respond to top-posted replies, please don't ask

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Fast Container Thomas Lehmann <thomas.lehmann.private@googlemail.com> - 2011-11-02 08:21 -0700
  Re: Fast Container Leigh Johnston <leigh@i42.co.uk> - 2011-11-02 15:43 +0000
    Re: Fast Container jacob navia <jacob@spamsink.net> - 2011-11-02 18:09 +0100
      Re: Fast Container Leigh Johnston <leigh@i42.co.uk> - 2011-11-02 17:24 +0000
    Re: Fast Container Thomas Lehmann <thomas.lehmann.private@googlemail.com> - 2011-11-03 07:12 -0700
      Re: Fast Container Leigh Johnston <leigh@i42.co.uk> - 2011-11-03 14:37 +0000
  Re: Fast Container Victor Bazarov <v.bazarov@comcast.invalid> - 2011-11-02 12:40 -0400
    Re: Fast Container Leigh Johnston <leigh@i42.co.uk> - 2011-11-02 16:56 +0000
    Re: Fast Container Thomas Lehmann <thomas.lehmann.private@googlemail.com> - 2011-11-03 07:01 -0700
      Re: Fast Container Victor Bazarov <v.bazarov@comcast.invalid> - 2011-11-03 10:13 -0400
  Re: Fast Container Werner <werasm@gmail.com> - 2011-11-02 14:06 -0700
    Re: Fast Container Werner <werasm@gmail.com> - 2011-11-02 14:11 -0700
  Re: Fast Container Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-11-03 08:45 -0700

csiph-web