Indexing of file in C++

[Man4ish]

I am trying to index the flat file in order to speed up the searching keyword. How this can be done efficiently? Thanks in advance

Manish

[weaknessforcats]

Read each record of the file and create an STL pair<> object containing the key and the offset of the record from the beginning of the file. Insert the pair<> object into a map<> container.

To access by key, you reas the map<> to get the offset and then read the file and fetch the record at that offset.

[Man4ish]

@weaknessforcats
I think for this whole map need to roll but data structure like B tree is used less comparison will be used but i don't know how to use it.

[weaknessforcats]

A map<> is a B tree. There is a structure there already. It is the pair<> object.

Here is your file:

Hello
world

The first letter of each word is the key:

H offset 0
w offset 5

Create pair objects with H 0 and w 5.

Insert these in a map<>

To locate world, search the map for w as the key. You will get yout pair object returned ( w 5). Now read your file by doing a seek to 5 and then a read.

[Man4ish]

@weaknessforcats
Thanks, but i have one confusion why value of w is 5. and also if there are two values with lilke water and world then there may be ambiguity.How to overcome that pblm.

[weaknessforcats]

Hello occupies positions 0,1,2,3,4. world starts in position 5. However, if world is another record, then there will be one or two line control characters after hello. That would start world in position 7 or 8.

The only way to know is to read your file and do a tell on the first letter of each word. Then create your pair<> with the key to that word plus the offset you got from the tell.

This read pass of the disc file to get the offsets and puttting them in a map<> container as pair<> objects is called creating an index.

If you have multiple words with the same key, then use a multimap<>. Then when you access the multimap<> using a key, you have to call both the lower_range and upper_range methods. multimap<>::lower_range returns an interator to the lowest positioned word with that key. multimap<>::upper_range returns an iterator that is one beyond that highest positioned occurrance of the key.

You then use these two iterators as you wouild begin() and end() to iterate the words between those two values. You will get all of the words with that key. Your loop must choose which one it wants.

[Man4ish]

@weaknessforcats
Thank you very much for you answer.