By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,928 Members | 1,173 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,928 IT Pros & Developers. It's quick & easy.

need an efficient data structure

P: n/a

i need to store a lot of integers(say 10,000) in a datastructure.
The constraints are:
1. It should be fast.
2. It should be orderded or sorted.
3.Insterting and deleting should be fast.
4. The no. of elements can change at runtime and hence it should be dynamic.
Right now i am using SortedVector , but it is very slow.
So, can u pls suggest a suitable Datastructure.
Jul 22 '05 #1
Share this Question
Share on Google+
10 Replies


P: n/a

"Raghavendra Mahuli" <ra************@in.bosch.com> wrote in message
news:c9**********@ns1.fe.internet.bosch.com...

i need to store a lot of integers(say 10,000) in a datastructure.
The constraints are:
1. It should be fast.
2. It should be orderded or sorted.
3.Insterting and deleting should be fast.
4. The no. of elements can change at runtime and hence it should be dynamic. Right now i am using SortedVector , but it is very slow.
So, can u pls suggest a suitable Datastructure.


std::set or std::multiset if you want duplicates.

john
Jul 22 '05 #2

P: n/a
On Thu, 27 May 2004 09:30:01 +0100, "John Harrison"
<jo*************@hotmail.com> wrote:

"Raghavendra Mahuli" <ra************@in.bosch.com> wrote in message
news:c9**********@ns1.fe.internet.bosch.com...

i need to store a lot of integers(say 10,000) in a datastructure.
The constraints are:
1. It should be fast.
2. It should be orderded or sorted.
3.Insterting and deleting should be fast.
4. The no. of elements can change at runtime and hence it should be

dynamic.
Right now i am using SortedVector , but it is very slow.
So, can u pls suggest a suitable Datastructure.


std::set or std::multiset if you want duplicates.


And make sure you have a fast memory allocator! A pool allocator would
help a lot here, if your std::allocator isn't already optimized in
that way.

Tom
--
C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
Jul 22 '05 #3

P: n/a
Raghavendra Mahuli wrote:
i need to store a lot of integers(say 10,000) in a datastructure.
The constraints are:
1. It should be fast.
There will be trade-offs. Which operations should be fastest?
2. It should be orderded or sorted.
Must that property be maintained at all times, or do you plan to do a
bunch of insertions or deletions between reads? What I mean is, if you
will insert 100 elements in a row, does the collection really need to
re-sort itself after each insertion?
3.Insterting and deleting should be fast.
Inserting and deleting where? If you need to maintain the ordering
after absolutely every insertion, a std::set or std::multiset may be
best, as JohnH suggested. If you only need it to be sorted once all
elements have been inserted, a std::vector may be more efficient by a
constant factor in both time and space.
4. The no. of elements can change at runtime and hence it should be dynamic.


The standard library has dynamically growable collections for almost all
your containment needs. :)
Jul 22 '05 #4

P: n/a
"Raghavendra Mahuli" <ra************@in.bosch.com> wrote in message
i need to store a lot of integers(say 10,000) in a datastructure.
The constraints are:
1. It should be fast.
2. It should be orderded or sorted.
3.Insterting and deleting should be fast.
4. The no. of elements can change at runtime and hence it should be dynamic. Right now i am using SortedVector , but it is very slow.
So, can u pls suggest a suitable Datastructure.


In addition to the fine points raised by everyone else, will the integers be
in a range (say 0 to 65535), and can each number occur more than once?
Jul 22 '05 #5

P: n/a
I'll clarify my situation further.....
1. Having a fast structure, what i mean is insertion of elements anywhere
(and deletion anywhere) should not take much time....Also access time, i.e.
time required to read a particular element should also be fast....I know it
is a tough requirement (But thats why i posted the question to this group).
2. Also each integer can occur more than once but not more than twice.....

If no standard structure satisfies these constraints, can u suggest a new
idea that would satisfy the needs.....
Jul 22 '05 #6

P: n/a

"Jeff Schwab" <je******@comcast.net> wrote in message
news:Tr********************@comcast.com...
Raghavendra Mahuli wrote:
i need to store a lot of integers(say 10,000) in a datastructure.
The constraints are:
1. It should be fast.


There will be trade-offs. Which operations should be fastest?

--------- Insertion , deletion & searching should be fast
2. It should be orderded or sorted.


Must that property be maintained at all times, or do you plan to do a
bunch of insertions or deletions between reads? What I mean is, if you
will insert 100 elements in a row, does the collection really need to
re-sort itself after each insertion?


------ At a time, i'll be inserting only 2 elemnts in a row.....it should
reorder itself immediately.
3.Insterting and deleting should be fast.


Inserting and deleting where? If you need to maintain the ordering
after absolutely every insertion, a std::set or std::multiset may be
best, as JohnH suggested. If you only need it to be sorted once all
elements have been inserted, a std::vector may be more efficient by a
constant factor in both time and space.

--------I need to maintain ordering after every 2 insertions...
Jul 22 '05 #7

P: n/a
Raghavendra Mahuli wrote:
"Jeff Schwab" <je******@comcast.net> wrote in message
news:Tr********************@comcast.com...
Raghavendra Mahuli wrote:
i need to store a lot of integers(say 10,000) in a datastructure.
The constraints are:
1. It should be fast.
There will be trade-offs. Which operations should be fastest?


--------- Insertion , deletion & searching should be fast


Is O(ln2 n) good enough for all of those operations?
2. It should be orderded or sorted.


Must that property be maintained at all times, or do you plan to do a
bunch of insertions or deletions between reads? What I mean is, if you
will insert 100 elements in a row, does the collection really need to
re-sort itself after each insertion?

------ At a time, i'll be inserting only 2 elemnts in a row.....it should
reorder itself immediately.


Sounds like std::multiset might be your best bet.
3.Insterting and deleting should be fast.


Inserting and deleting where? If you need to maintain the ordering
after absolutely every insertion, a std::set or std::multiset may be
best, as JohnH suggested. If you only need it to be sorted once all
elements have been inserted, a std::vector may be more efficient by a
constant factor in both time and space.


--------I need to maintain ordering after every 2 insertions...


Is the number of possible values bounded? If so, how many possible
values of elements are there? 10,000? 2^32? I don't mean how many
elements you need to store in your container, but how many different
values might exist for the type of your integer; for example, if you're
using 16-bit integers, there are 2^16=65536 possible values.
Jul 22 '05 #8

P: n/a
> Is O(ln2 n) good enough for all of those operations?
--------I think that is sufficient

Is the number of possible values bounded? If so, how many possible
values of elements are there? 10,000? 2^32? I don't mean how many
elements you need to store in your container, but how many different
values might exist for the type of your integer; for example, if you're
using 16-bit integers, there are 2^16=65536 possible values.


-----i am storing memory addresses....So all values in the range are
possible.....but they'll generally be multiples of 4...........And
maximum
possible value is 2^32.

Jul 22 '05 #9

P: n/a
"Raghavendra Mahuli" <ra************@in.bosch.com> wrote in message
news:c96ls6$ju6
-----i am storing memory addresses....So all values in the range are
possible.....but they'll generally be multiples of 4...........And
maximum
possible value is 2^32.


Try the map idea suggested by John, along with the allocator suggested by
tom_usenet.

A direct address table, hinted at in my post, is out of the question since
the range of values is so big (basically you have an array whose size equals
to the number of different possible elements).

You can use a hybrid approach, which could very well be a hashtable.
Something like: all of the numbers in [0, 2^32] hash to one of 32 different
values with equal probability, which still means many numbers could hash to
the same value, and so you store the different numbers in a map (with custom
pool allocator) data structure. See if your implementation has a
hash_table.
Jul 22 '05 #10

P: n/a
Raghavendra Mahuli wrote:
Is O(ln2 n) good enough for all of those operations?


--------I think that is sufficient
Is the number of possible values bounded? If so, how many possible
values of elements are there? 10,000? 2^32? I don't mean how many
elements you need to store in your container, but how many different
values might exist for the type of your integer; for example, if you're
using 16-bit integers, there are 2^16=65536 possible values.

-----i am storing memory addresses....So all values in the range are
possible.....but they'll generally be multiples of 4...........And
maximum
possible value is 2^32.


For the values that aren't multiples of 4, stick them in a std::set.
The access time for them will be logarithmic with the cardinality of the
set, but since that cardinality is small, the performance should be good.

This leaves 2^(32-2) = 2^30 values to store; you could use a sequence of
bits, initialized to zero, to represent whether each value is in the
collection. Since you allow up to two of each element, you'll probably
want an extra bit per element to show whether it has been inserted more
than once. This means you need 2^31 bits. I would recommend using two
std::vector<bool>: one to represent whether each value had been
inserted at least once, and another to represent whether each value had
been inserted more than once. You'll need at least 256 MB of RAM, plus
space for the std::set. The machines where I work typically have
multiple GB of RAM, so this is probably the solution I would choose if
performance were critical.
Jul 22 '05 #11

This discussion thread is closed

Replies have been disabled for this discussion.