Multimap overkill?

[Volatile Pulse]

So I was playing around with some of the STL containers, and ran across the multimap, so I decided to give it a whirl. My first attempt at using it, I came up with this:

#include <iostream>
#include <vector>
#include <string>
#include <map>

int main() {
   std::cout << "Enter Angler's Name: ";
   std::string strAnglersName;
   std::cin >> strAnglersName;

   std::vector<float> vFishWeight;
   for(int i = 0; i < 5; i ++) {
      std::cout << "Please enter weight for fish " << i + 1 << ": ";
      float fFishWeight;
      std::cin >> fFishWeight;
      if(fFishWeight <= 0)
         break;
      vFishWeight.push_back(fFishWeight);
   }

   std::multimap<std::string, std::vector<float>> mmResults;
   mmResults.insert(std::pair<std::string, std::vector<float>> (strAnglersName, vFishWeight));

   for(auto it : mmResults) {
      std::cout << "Angler Name: " << it.first << "\n";
      for(auto fish : it.second)
         std::cout << "Fish weight: " << fish << "\n";
   }

   return 0;
}

It's going to be getting used in another program, but I was wondering, is this overkill, or is this what it was intended for? The name is going to be a searchable index for the map.

[viliml]

It's kinda overkill, but not much! Since I don't think there will be more anglers with the same name, you should use the regular std::map! The only ovekilling here is using a multimamp where a map would suffice.

[Volatile Pulse]

I've switched it to just a regular map, I didn't realize what the multi meant until you just said something, all of the information between the two were so similar. But now I've been running into an issue. I want the user to be able to type in a string, let's say "Ste" and I want to be able to search my map for any "key" that has "Ste", "ste", "StE", etc. in it, and pop out a result. Is this possible, or would I have to create my own function to modify both it.first and stringSearch and compare them and return a value?

Essentially, I want the map to contain information on all of the anglers that participate in a tournament. It will grab it's keys from the matching string of another map, assign it to itself, and add necessary information for each tournament.

[viliml]

You should make a new comparison class. It shall look something like this:

struct any_case_comp
{
      bool operator ()(const string& a, const string& b)
      {
            for (int i=0; i<a.size(); i++)
            {
                  if (tolower(a[i])!=tolower(b[i])) return tolower(a[i])<tolower(b[i]);
                  }
            return a.size()<b.size();
            }
      };

You can change the name, but the inside shall look pretty muck like that, or something else that has the very same effect.
Then you construct the map like this: std::map<std::string, std::vector<float>, any_case_comp> mResults;
This way the letter case doesn't matter, so in some cases you might need a multimap, but since theese are all names, with the only capital letter on the begginning, you can use a regular map too.

[firedraco]

Just use something like boost::to_lower() on the keys when you put them in. You could pass a custom comparator function if you really want to (like one of boosts possibly).

[Volatile Pulse]

@viliml
Thanks for the extra effort, but the string compare needs to happen before the map is even created, well, before any values are inserted into it. Like I said, the user will search, once a matching string is found in a different map, that string is then placed into this map's "key" to store information for this specific event. Not every member will attend each event, so I can't just copy the keys over either.

@firedraco
I just got boost 1.5.0 installed just a few days ago and haven't been messing around with it a whole lot, but the key's are to remain untouched simply because we need to maintain the formatting on the text. I can generate a separate string to contain the "to lowered" map key, but I also need to store iterators for the map as well.

I have a lot of trial and error to do, but it seems like the map has won my award for making my life complicated again. I will solve this puzzle -.-

[viliml]

Umm, hello? I just done all that in my previous posts! And why use boost if we have everything we need in the standard c++? Now THAT would be overkill!!

[Volatile Pulse]

A more proper example would be to demonstrate what I mean:

std::map<std::string,Contact> memberList;
// memberList is populated from a file
// Example would be: "John Doe", ContactInfo

std::string searchString;
// ask user for name to search for
std::cout << "Please enter a name: ";
std::cin >> searchString;

// How do I search the keys in memberList with searchString?
// searchString will probably only contain the first name
// "John" in this case
// 
// If multiple "John"s exist in memberList, I want iterator's to each element of the map
// From there, a menu will be displayed showing the different names
// When a user selects the name they wanted, that key becomes part of mResults

std::map<std::string,std::vector<float>> mResults;
// Will contain name as key, and vector as information
mResults.insert(pair<std::string,std::vector<float>> (matchedKey, vFishWeight));

I believe my only choice will be to create a custom function for this since I know of no other way to get an iterator, which will be used in a vector as well, and compare parts of a string.

Edit: I believe I've come up with an efficient way to search.

Edit: This is what I came up with in regards to searching. It's not pretty, but it does what I need it to do:

#include <iostream>
#include <vector>
#include <string>
#include <cctype>
#include <map>

bool CompareStrings(std::string partialString, std::string fullString) {
   // Convert partialString to all lowercase
   for (auto & i : partialString)
      i = tolower(i);

   // Convert fullString to all lowercase
   for (auto & i : fullString)
      i = tolower(i);

   // Search the length of fullString minus the length of partialString
   for (int i = 0; i < (fullString.length() - partialString.length()); i ++)

      // Check the substring of fullString against partialString
      if (fullString.substr(i, partialString.length()) == partialString)
         // If it matches, return true
         return true;

   // Otherwise, false
   return false;
}

int main() {
   std::cout << "Enter Angler's Name: ";
   std::string strAnglersName;
   std::cin >> strAnglersName;

   std::vector<float> vFishWeight;

   for (int i = 0; i < 5; i ++) {
      std::cout << "Please enter weight for fish " << i + 1 << ": ";
      float fFishWeight;
      std::cin >> fFishWeight;

      if (fFishWeight <= 0)
         break;

      vFishWeight.push_back(fFishWeight);
   }

   std::map<std::string, std::vector<float>> mPersonalResults;
   mPersonalResults.insert(std::pair<std::string, std::vector<float>> ("Jane", vFishWeight));
   mPersonalResults.insert(std::pair<std::string, std::vector<float>> ("Steve", vFishWeight));
   mPersonalResults.insert(std::pair<std::string, std::vector<float>> ("Victor", vFishWeight));
   mPersonalResults.insert(std::pair<std::string, std::vector<float>> (strAnglersName, vFishWeight));

   std::cout << "\n";

   for (auto it : mPersonalResults) {
      if (CompareStrings("VOL", it.first))
         std::cout << "\nString Compared!\n";

      std::cout << "Angler Name: " << it.first << "\n";

      for (auto fish : it.second)
         std::cout << "Fish weight: " << fish << "\n";
   }

   return 0;
}

Enter Angler's Name: Volatile
Please enter weight for fish 1: 0

Angler Name: Jane
Angler Name: Steve
Angler Name: Victor

String Compared!
Angler Name: Volatile

Process returned 0 (0x0)   execution time : 4.906 s
Press any key to continue.

I'm not sure if there is a better way to do this (Read: more efficient or cleaner code), but it definitely works, and since I'm already looping through the iterator's, I can add them into my vector as well. Any comments would be nice. And I know there is an unsigned type conversion in my function, but I threw it together quickly to get it to work.

[viliml]

Oh, so you need the partial checking too! I guess it can be easiely modified, but I just can't do it now.

[rollie]

You can clean up your search function a bit with

return fullString.find(partialString) != string::npos;

after converting the strings to lowercase. I might change the name from 'CompareStrings' to something like 'Contains', as readers of your code might be confused what this function does.

[Volatile Pulse]

Thanks for the replies, but I had already changed it but didn't update it. I will work on the Function name a bit though.

[JLBorges]

These are the two (four) options:

#include <map>
#include <string>
#include <iostream>
#include <vector>

int main()
{
    {
        std::multimap< std::string, int > pbook =
        {
            { "abcd", 1234 }, { "abcd", 5678 }, { "abcd", 9012 } ,
            { "efgh", 1111 }, { "efgh", 2222 }, { "efgh", 3333 }, { "efgh", 4444 },
            { "ijkl", 9876 }
        } ;

        const std::string key = "efgh" ;
        for( auto pair = pbook.equal_range(key) ; pair.first != pair.second ; ++pair.first )
            std::cout << pair.first->second << '\n' ;
    }

    {
        std::map< std::string, std::vector<int> > pbook =
        {
            { "abcd", { 1234, 5678, 9012 } },
            { "efgh", { 1111, 2222, 3333, 4444 } },
            { "ijkl", { 9876 } }
        } ;

        const std::string key = "efgh" ;
        auto iter = pbook.find(key) ;
        if( iter != pbook.end() )
            for( int number : iter->second ) std::cout << number << '\n' ;
    }
}

Which is more efficient would depend on:

1. The type of the key
2. Do all keys map to multiple values or only a few of them?
3. How often do we need to insert/erase key/data pairs?
and so on.

[viliml]

OK Volatile Pulse, I finaly did it, and made it work on ALL the criteria you set! Here:

bool comp_helper(string a, string b)
{
   for(int i=0; i<a.size(); i++)
      a[i]=tolower(a[i]);

   for(int i=0; i<b.size(); i++)
      b[i]=tolower(b[i]);
   
   if (a==b) return true;
   
   if (b.size()>=a.size())
   for(int i=0; i<(b.size()-a.size()); i++)

      if(b.substr(i, a.size())==a)
         return true;
   
   else
   for(int i=0; i<(a.size()-b.size()); i++)

      if(a.substr(i, b.size())==b)
         return true;
   
   return false;
}

struct comp
{
       bool operator()(string a, string b)
       {
            if (comp_helper(a, b)) return false;
            return a<b;
            }
       };

Use "comp" as the third template argument in the definition of your map, and everything will work, with clean code!

I'm not sure if there is a better way to do this (Read: more efficient or cleaner code)

Yes, there is! And I just gave you the code!

[Volatile Pulse]

@JLBorges
That is case sensitive though and must match the key exactly. This will not be the case in my program. I also don't need the elements stored within the map, I just need to make sure that the key exists in a previous map that was populated from a file.

@viliml
That seems a lot longer than my final solution. Also, doesn't that only sort the map? The sorting features of the map will be adequate enough for what I need, but I am not trying to sort the map, I just need to check if a key exists against a partial string the user inputs. I'll create another example to show what the final product will be closest to.

[viliml]

Also, doesn't that only sort the map?

Yes, and no! It does *only* sort the map, but the sorting is the way that it acceses the elements! See, it doesn't use operator==, but the comparison object, in the following way: In the template, it has a class parameter that is a comarer class. Then it constructs an object of that class, let's call it "comparer", and instead of operator==, it uses !comparer(a, b) && !comparer(b, a)! And, as you can see from your own comarer function, if they are equal, it returs false for both function clals, so it reaturn that one! Try this example out:

map<string, int, comp> a;
    a["abcDEF"]=1;
    a["ABC"]=2;
    cout<<a["a"];

With the above comapre class of course! And you'll see that it prints 2, which meant that it treats "abcDEF", "ABC" and "a" as the same, and I think that's what you wanted!

[bartoli]

I didn't read the last posts, but i'd advise filling the vectors after having added them to the map. As you are doing now, you fill a vector, then you have to make a copy of the vector object and all its content. Filling directly the vector created in the map would remove those useless copies

[Volatile Pulse]

@bartoli
I did switch to initializing a vector instead of using the same variable over and over again. I just did it simply to speed things up.

@viliml
I had another post started and Cubbi had informed me about boost having a prebuilt non case sensitive function built in so I used that. I have been adding tweaks to the code, but my current version is this:

// Needed to search case insensitive strings
#include <boost/algorithm/string/predicate.hpp>
#include <iostream>
#include <vector>
#include <string>
#include <map>

int main() {
   // mMembersList contains Key:String, Value:Contact
   // For all intensive purposes, Value is not important here
   std::map<std::string, int> mMembersList;
   // mMembersList is populated from a file, since file isn't available
   // Create basic map with random keys:value
   mMembersList.insert(std::pair<std::string, int> ("Bob Jordan", 2));
   mMembersList.insert(std::pair<std::string, int> ("George Jeremy", 2));
   mMembersList.insert(std::pair<std::string, int> ("Donald Richardson", 3));
   mMembersList.insert(std::pair<std::string, int> ("Robert Newman", 8));
   mMembersList.insert(std::pair<std::string, int> ("John Doe", 20));
   mMembersList.insert(std::pair<std::string, int> ("Richard Stevenson", 12));
   mMembersList.insert(std::pair<std::string, int> ("Steve Davidson", 1));

   //mPersonalResults contains Key:String, Value:Vector<Float>
   std::map<std::string, std::vector<float>> mPersonalResults;
   // mMembersList is populated from a file, since file isn't available
   // Create basic map with random keys:value
   mPersonalResults.insert(std::pair<std::string, std::vector<float>> ("Bob Jordan", {60.5, 17.3, 15.4}));
   mPersonalResults.insert(std::pair<std::string, std::vector<float>> ("Donald Richardson", {60.6, 17.3, 12.7}));
   mPersonalResults.insert(std::pair<std::string, std::vector<float>> ("John Doe", {59.2, 20.1}));

   /* NOT INCLUDED IN MAIN PROGARM */
   // Display members in list
   std::cout << "Members:\n";
   for (auto it : mMembersList)
      std::cout << "\t" << it.first << "\n";

   // Display members already entered
   std::cout << "\nMembers that already completed event:\n";
   for (auto it : mPersonalResults)
      std::cout << "\t" << it.first << "\n";

   /* INCLUDED IN MAIN PROGRAM */
   // Create variable for number of participants
   int iParticipants;
   // Ask user for number of members in <EVENT NAME>
   std::cout << "How many members are participating in <EVENT NAME>? ";
   // Store number of participants in iParticipants
   std::cin >> iParticipants;
   std::cin.ignore(80, '\n');
   do {

      // Create a vector to store found names
      std::vector<std::string> vFoundNames;

      // Create a strSearch used to find any valid keys in mMembersList
      std::string strSearch;
      do {
         std::cout << "\nPlease enter a name to search for: ";
         getline(std::cin, strSearch);
         // Search mMembersList
         for (auto member : mMembersList)
            // If a member matched the search
            if (boost::algorithm::icontains(member.first, strSearch))
               // Make sure member doesn't exist in mPersonalResults
               if (mPersonalResults.find(member.first) == mPersonalResults.end())
                  // Add unused members to vFoundNames
                  vFoundNames.push_back(member.first);
      } while (!vFoundNames.size());

      // Used to store which member to select
      int iMember;

      // If more than one name was found
      if (vFoundNames.size() > 1) {
         // Display vFoundNames
         for (unsigned int i = 0; i < vFoundNames.size(); i ++)
            std::cout << i + 1 << ") " << vFoundNames[i] << "\n";

         // Let used select name they want
         std::cin >> iMember;
         std::cin.ignore(80, '\n');
      }
      // Otherwise, automatically select the only member
      else
         iMember = 1;

      // Create int to hold number of fish
      int iFish;
      // Ask the user how many fish <MEMBER> caught
      std::cout << "\nHow many fish did " << vFoundNames[iMember - 1] << " catch? ";
      // Store number of fish in iFish
      std::cin >> iFish;
      std::cin.ignore(80, '\n');

      // Create int to hold number of dead fish
      int iDeadFish;
      // Ask the user how many dead fish <MEMBER> caught
      std::cout << "\nHow many dead fish did " << vFoundNames[iMember - 1] << " have? ";
      // Store number of dead fish in iDeadFish
      std::cin >> iDeadFish;
      std::cin.ignore(80, '\n');

      // Create vector to hold fish's weight
      std::vector<float> vFishWeight;

      // Notify user to enter weights for the member they selected, or only member
      std::cout << "Enter Weights for " << vFoundNames[iMember - 1] << ":\n";
      // Allow up to 5 fish's weight to be entered
      for (int i = 0; i < 3; i ++) {
         // Enter total weight first
         if (i == 0)
            std::cout << "\tEnter total weight: ";
         // Enter largest fish after
         else
            // Notify the user which fish they're entering weights for
            std::cout << "\tLargest Fish " << i << ": ";
         // Create a temporary variable to store the fish's weight
         float fFishWeight;
         // Have the user enter the weight
         std::cin >> fFishWeight;
         std::cin.ignore(80, '\n');

         // If the weight was 0 or less
         if (fFishWeight <= 0)
            // Break the loop since it's not a valid weight
            break;
         // Add the weight to the vector
         vFishWeight.push_back(fFishWeight);
      }

      // Add member and fish weights to mPersonResults
      mPersonalResults.insert(std::pair<std::string, std::vector<float>> (vFoundNames[iMember - 1], vFishWeight));
   } while (mPersonalResults.size() < iParticipants);

   // Display mPersonal Results
   for (auto it : mPersonalResults) {
      // Display Key
      std::cout << "\n" << it.first << ":\n";
      // Make sure member caught fish
      if (it.second.size() != 0)
         // Display weights
         for (auto it2 : it.second)
            std::cout << "\t" << it2;
      // Otherwise
      else
         std::cout << "\tDidn't catch any fish!";
   }

   return 0;
}