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

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

Re: std::set preallocate?

Show all headers | View raw

>> BTW, do you need a set? Maybe a hashset? Maybe a vector?
>>
>> Edek

> Container needs to act like a queue more or less. I fill it with items
> that I need to do operations on, do the operations, then erase them
> from the container. However, the container has to guarentee that the
> items are unique. Because the methods where they are used may receive
> the same items multiple times before the time comes around to do the
> operations on them.
>
> So, I need some kind of container that is a queue of unique items.

There are some improvisations possible. Like, on plain vectors,

1) store the 'queue' as a vector
2) store incoming items in a separate vector (unsorted, with duplicates)
3) when you need to fetch some,
    a) merge vectors, sort, remove duplicates by remove_copy_if
    b) take some (and do operations on them)
    c) create a new separate vector for point 2

This is just from the top of my head as an example. It
will not fit every scenario (or maybe even any ;) )

a + b could be like:

struct DuplicateRemover
{
     last = someComparingAsFalse;

     bool operator () (next) {
        if (next == last) return true;

        last = next;

        return false;
    }
}

struct FirstN {
      FirstN (int n , iterator toHandle, iterator toStore)
    ... fields init, count=0 {}

      void operator () (next) {
          if (count ++ < n )
              put next in toHandle
          else
              put next in toStore
      }
}

copy (incoming.begin(), incoming.end(), merge.end());

... sort merge ...

remove_copy_if (merge.begin(), merge.end (),
        make_function_output_iterator(
              FirstN (100, toHandleVector.begin(), new_store.begin()),
	DuplicateRemover());

throw out merge, new_store is left items, handle the toHandle...

As you see, there is a lot of copying and comparing involved,
so maybe this is a not so good idea, if the 'set' is huge
and you only take a couple of items very often.

But you certainly can preallocate.

Edek

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

Thread

std::set preallocate? Christopher <cpisz@austin.rr.com> - 2011-06-10 13:01 -0700
  Re: std::set preallocate? Pete Becker <pete@versatilecoding.com> - 2011-06-10 10:32 -1000
  Re: std::set preallocate? Edek <edek.pienkowski@gmail.com> - 2011-06-10 22:57 +0200
    Re: std::set preallocate? Christopher <cpisz@austin.rr.com> - 2011-06-10 14:51 -0700
      Re: std::set preallocate? Carlo Milanesi <carlo.nospam.milanesi@libero.it> - 2011-06-11 00:42 +0200
      Re: std::set preallocate? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2011-06-11 10:44 +0000
      Re: std::set preallocate? Edek <edek.pienkowski@gmail.com> - 2011-06-11 18:14 +0200
  Re: std::set preallocate? Juha Nieminen <nospam@thanks.invalid> - 2011-06-11 04:52 +0000

csiph-web