Which class offers the fastest search ???

Beginner

Occupation: Software Engineer

Monday, May 9th 2005, 1:53pm

I want to implement a cache in my program. Which data structure in Qt can I use for that. There is QMap, QPtrDIct, QIntCache. But i want to use the one which is fast in searching ( lookup ). Which one offers the best lookup speed???

Go to the top of the page

wysota

Sage

Posts: 4,276

Location: Warsaw, POLAND

2

Monday, May 9th 2005, 2:49pm

RE: Which class offers the fastest search ???

Hmm... the proper answer is "it depends". The real answer is probably "none of them". You didn't even tell us what do you want to cache.

QtCentre.org - the largest Qt community site and forum where questions get answered

Go to the top of the page

myfairlady

Beginner

Posts: 35

Occupation: Software Engineer

3

Tuesday, May 10th 2005, 1:20pm

RE: Which class offers the fastest search ???

It depends on what ??
My problem is I have to implement a cache which stores some details abt a particular class ( just like key-value pairs in a hash ) . So for this I shuld use either a QMap or a QPtrDict ( i came across these two in the docs). So My declaration will be say,
QMap< int, Class*> .
At a later stage i need to lookup the values given a particular id( the key ).
So i want to know which of these 2 ( QMap/ QPtrdict ) offers better searching speed. I want the lookup to be very fast even if insertion is slow.

In the docs it is given that QMap is a value-based and QPtrDict is pointer-based, so does tht mean that QPtrDict is faster in searching ???
Which has faster lookup and why ???

Go to the top of the page

dimitri

Professional

Posts: 1,311

Occupation: Engineer

4

Tuesday, May 10th 2005, 2:12pm

RE: Which class offers the fastest search ???

Ah, but this is not a cache, not with the usual meaning at least.

Go to the top of the page

wysota

Sage

Posts: 4,276

Location: Warsaw, POLAND

5

Tuesday, May 10th 2005, 3:40pm

RE: Which class offers the fastest search ???

I think lookup time will be the same for both of these classes. But I think you should use a binary tree instead

Or even a B-tree. The latter are used for database indexes, so you can say they are pretty fast

QtCentre.org - the largest Qt community site and forum where questions get answered

Go to the top of the page

jacek

Master

Posts: 2,729

Location: Warsaw, Poland

6

Tuesday, May 10th 2005, 4:23pm

RE: Which class offers the fastest search ???

Quoted

Originally posted by wysota
Or even a B-tree. The latter are used for database indexes, so you can say they are pretty fast

B-trees are fast because they require less IO operations, but they won't outrun a balanced binary tree, if it fits in the memory.

Quoted

Originally posted by myfairlady
In the docs it is given that QMap is a value-based and QPtrDict is pointer-based, so does tht mean that QPtrDict is faster in searching ???
Which has faster lookup and why ???

QMap is value based (i.e. it holds copies of your objects), so every time you insert something it will make a copy. QPtrDict doesn't make copies, so insertions should be faster, but I don't see any reason why QMap should have lower lookup speed.

You could write a little benchmark to check which one is really faster.

You can meet me at Qt Centre - The Ultimate Qt Community site.