I have an array of CStrings (yes I know mfc is a pain but I didnt know that when i began using it and now I just havent got the time to change it to win32). This array can be very big (20,000 is the biggest Ive needed it so far). In the array are names suck as "Horatio_00_00", "Horatio_01_00","Hamlet_00_00" etc. Now I need to be able to extract and return a CString array of every occurance of the name Horatio that has a different end number (so basically if the original array was : "Horatio_00_00", "Horatio_01_00", "Horatio_00_01", "Horatio_01_01", "Horatio_00_06", "Horatio_01_06", "Horatio_00_13", "Horatio_01_13", then my returned array would be: "Horatio_00_00", "Horatio_00_01", "Horatio_00_06", "Horatio_00_12", I can do this fine except when I got the array with 20,000 CStrings I noticed a slight slowdown (it took 15 minutes just to get through the first 1000). I know the reason for this iwas using a nested loop where x and y started off at 0 and went up to 20,000 like so: for (int x=0;x<NumElements;x++) { for (int y=0;y<NumElements;y++) { } } I was having to do this twice. Once to find out how many Elements I needed in my resultant array (so that i could allocate the memory) and then again to actually put it in the array. Of course this is fine if I have only a few elements in my array but way too long and inefficient if i have many. There has to be another way to get just the few elements of the array I need without having to loop through it like this but I cant think of any other way to do it. If anyone could hlep me I would be very grateful. Thanks

Thanks for your reply WarMage.

There arent actually any duplicates in my array as the CStrings are FileNames (of images) so if there are duplicates they need to be there because they are different images (i.e. a different path).

Now as for your hash table you have intrigued me (and pretty much lost me lol), I would much much much prefer to use more memory than for it to be so slow (6000 small images took me 1/2 hour to process and all i am doing to the images is compressing them and possibly converting them from 16bit to 24bit or vice versa- this should not take as long as it is doing). So id rather do this hash table thing. Could you perhaps explain it a bit more in depth?

Thanks again for the reply

Thanks Stoffel and AP.

AP>Yeah its definately this extracting thing. Ive put
TRACE("Processing") in the first loop:

for (int x=0;x{
for (int y blah blah)
{
}
TRACE("Processing")
}

And then Ive watched it in my debug window and its definately here that it spends 90% of its time.

Stoffel>This is the format of the CStrings CharacterName_Direction_Pose

So for Hamlet_00_00 it means the image is of Hamlet it is the first direction and the first pose. What Im trying to do is group all the poses for each name together so that i can pass along a CString* that contains all of the Hamlet_Directions_00 etc and convert them/compress them and put them in a dat file.

Hmmmm I still dont think im explaining this too well. I cant see a way a multidimensional array can help and im not sure what you or WarMage mean by hash table/map.

Thanks again for the help guys

Have you considered a tree? Your aim is to get a list of pictures that some property, right?

How about this structure:

Horatio|+-- 00|   ||   +-- Horatio_00_00|   ||   +-- Horatio_00_01|   ||   +-- Horatio_00_06|   ||   +-- Horatio_00_13|+-- 01    |    +-- Horatio_01_00    |    +-- Horatio_01_01    |    +-- Horatio_01_06    |    +-- Horatio_01_13 

And so on. That way, all you gotta do is return a pointer to the '00' node or '01' node and so forth.

You have a tiny overhead for insertion and deletion (if you want them sorted/balanced) but it worth it if you can speed up searching. log (n) + n... I think. log(n) to get the node and n to traverse the rest.

---
PAGE FAULT: Please insert "Swap File, Disk 2"
and press any key to continue.

Edited by - OberonZ on September 24, 2001 6:29:10 PM

Edited by - OberonZ on September 24, 2001 6:31:07 PM

Thanks guys. Im not too sure whether im gonna go for the hash table thingy or the tree, I guess ill try both and see which is faster. Thanks a lot for the help

Using the STL Multimap you can store and find any type of data. The following example uses STL strings ...

Note. Multimap needs the data to be entered in a sorted order.

#pragma warning(disable:4786)

#include &ltmap>
#include &ltstring>
#include &ltiostream>

using namespace std;

void main()
{
multimap&ltstring, string> mMap; // this line generates Warning 4786
multimap&ltstring, string>::iterator mMapIterator;
multimap&ltstring, string>::iterator mMapIteratorStart;
multimap&ltstring, string>::iterator mMapIteratorEnd;

mMap.insert(map&ltstring, string>::value_type("Horatio_00", "_01"));
mMap.insert(map&ltstring, string>::value_type("Horatio_00", "_02"));
mMap.insert(map&ltstring, string>::value_type("Horatio_00", "_03"));
mMap.insert(map&ltstring, string>::value_type("Horatio_00", "_04"));
mMap.insert(map&ltstring, string>::value_type("Horatio_01", "_01"));
mMap.insert(map&ltstring, string>::value_type("Horatio_01", "_02"));
mMap.insert(map&ltstring, string>::value_type("Horatio_01", "_03"));
mMap.insert(map&ltstring, string>::value_type("Horatio_01", "_04"));

mMapIteratorStart = mMap.equal_range("Horatio_00").first;
mMapIteratorEnd = mMap.equal_range("Horatio_00").second;

for (mMapIterator = mMapIteratorStart; mMapIterator != mMapIteratorEnd; mMapIterator++)
{
cout << (*MapIterator).first << (*mMapIterator).second << "\n";
}
}

Hope it helps