Reply With QuoteDoes it have to be a vector? Because a map might be as easy to do, but sounds like it matches what you want to do much better than a vector does (at least in a logical sense).
A map creates a hash array where you have a key (in your case a single character 'a'-'z') and a value (in your case BST<string> or BST<char *>). The only thing is that all keys must be unique (if you need to have multiple instances of the same key you have to use a multimap--mmap). But, according to what you want to do, a map will be fine. Something like this would work:
Hope that isn't way more than you want. But, at the very least, you now have an idea of what a map is!Code:#include <map> #include <vector> #include <string> #include <cctype> // toupper() function // Typedef your BST thing to MyBST here int main(int argc, char **argv){ map<char, MyBST> my_hashmap; // Hash for the object map<char, MyBST>::iterator hash_it // Iterator to loop through the map vector<string> words; // Holder for all the parsed words vector<string>::iterator it; // Iterator to loop through the words // Parse the words into the vector here // Loop through the words and insert them... for(it = words.begin(); it != words.end(); it++) my_hashmap[toupper(*it[0])].YourInsertMethod(*it); // Loop through the map and do something... for(hash_it = my_hashmap.begin(); hash_it != my_hashmap.end(); hash_it++){ // (*hash_it).first refers to the char in map<char, MyBST> // (*hash_it).second refers to the instance of MyBST that relates to char in map<char, MyBST> (*hash_it).second.YourMethodHere(); } // End for } // End main()
If you are dead set on a vector, then you can do something like this:
Notice we are using the expression ' toupper(first character of word) - 'A' '. This is a quick way to convert A to 0, B to 1, ... Z to 25, by subtracting the ASCII value of 'A' from the first character in uppercase form. After all, a char is really just a short int--so, you can do integer math on it. Nifty, huh?Code:#include <vector> #include <string> #include <cctype> // toupper() function // Typedef your BST thing to MyBST here int main(int argc, char **argv){ vector<MyBST> my_bst(26); // Vector for the object vector<MyBST>::iterator bst_it; // Iterator to loop through the vector vector<string> words; // Holder for all the parsed words vector<string>::iterator it; // Iterator to loop through the words // Parse the words into the vector here // Loop through the words and insert them... for(it = words.begin(); it != words.end(); it++) my_bst[toupper(*it[0]) - 'A'].YourInsertMethod(*it); // Loop through the vector and do something... for(bst_it = my_bst.begin(); bst_it != my_bst.end(); bst_it++){ *bst_it.YourMethodHere(); } // End for } // End main()
In either scenerio, it'll take the roughly the same amount of code to do what you want. However, the map fits a little better into the logic that you presented.
Two things I should mention about vectors, that you might be interested in. Little "F.Y.I." things that really only matter to those of us who optimize their programs.
First, you were correct in your assumption on how to set the initialized capacity. However, you should be aware that once you set a value in the vector the actual capacity could very well be around 85 cells or more.
Vectors and lists work kinda weird. They have predefined reserve "blocks", once you exceed a block, they add another block. Let's assume there is a reserve size of 256, the first item you insert creates storage for 256 items, when you insert the 256th item your storage size increases to 512 items, and so forth. The default size is compiler/library dependent (the 256 is the size for a int in the RogueWave library). Keep in mind, this is "un-indexed" reserved space on the heap--if you insert 4 items (in cells 0-3) and try to access cell 200, you will get a segmentation fault (coredump). You can set the reserve size manually (example: 'myvec.reserve(100);' will create 100 item blocks). More is better, as creating blocks causes overhead that slows execution speed.
Second, vectors and lists are very similar in use. However, vectors are faster when dealing with a small amount of simple classes as items or a small amount of types as items ("small" amounts would be less than say 15 million items). For large amounts, or complex classes, a list is much faster.
Bookmarks