Tuesday, 7 June 2011

Multisets and Multimaps

I was trying to understand where multisets would be used as compared to multimaps and I didnt find any straightforward answer. I found this simple explanation at StackOverflow:

multimap

  • With ZIP code as a key, all people which have that ZIP code
  • With account ID as key, all open orders of that person/account
  • A dictionary, with per keyword various explanations

multiset

is in essence a map with a key and a integer count.

  • The inventory of a shop, all products have their key and the amount still available is the value
  • accumulated sales data of a shop, every time a product is sold the product id get's added to the multiset thereby increasing the amount sold

As a result I created this example below. This is probably not the best of examples but I didnt want to change it. The main problem below is that multimap's are not strictly speaking required in the example below. I could have used a map. Multimap would be needed if there was no quantity_ in the class and then I can add the products one by one. I could have then used the count method to get the quantity.

Anyway, program as follows:


//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//Simple example of multiset

#include <iostream>
#include <string>
#include <set>
#include <map>
#include <algorithm>

using namespace
std;

class
Product //Keeping this simple
{
public
:
Product(string name, int code, int price) :
name_(name), productCode_(code), price_(price)
{

quantity_ = 10; //Lets fix this value for simplicity
}
bool
availableForSale()
{

if
(quantity_ > 0)
{

quantity_--;
return
true;
}

return
false;
}

string name_;
int
productCode_;
int
price_;
int
quantity_;
private
:
Product(); //Disabled the default constructor
};

void
sellProduct(string name, multimap<string, Product*>& inventory, multiset <int> &soldItems)
{

multimap<string, Product*>::iterator it = inventory.find(name);
if
(it != inventory.end())
{

if
((*it->second).availableForSale())
{

soldItems.insert((*it->second).productCode_);
}
}

else

{

cout << "Unknown product : " << name << endl;
}
}


void
soldItemsList(multimap<string, Product*>& inventory, multiset <int> &soldItems)
{

multimap<string, Product*>::iterator it = inventory.begin();
for
(it = inventory.begin(); it != inventory.end(); ++it)
{

int
soldCount = soldItems.count((*it->second).productCode_);
cout<<"Product = " << (*it->second).name_ << ", Quantity Sold = " << soldCount << endl;
}
}


int
checkSales(multimap<string, Product*>& inventory, multiset <int> &soldItems)
{

int
totalSales = 0;
multimap<string, Product*>::iterator it;
for
(it = inventory.begin(); it != inventory.end(); ++it)
{

int
soldCount = soldItems.count((*it->second).productCode_);
totalSales += soldCount * (*it->second).price_;
}

return
totalSales;
}


int
main()
{

//There is no special reason to use multimap instead of a map
//If you wanted to add same product and create quantity multimap is required
multimap<string, Product*> inventory;
Product* prod1 = new Product("product1", 2334, 10);
Product* prod2 = new Product("product2", 4556, 50);
inventory.insert(pair<string, Product*>("product1",prod1));
inventory.insert(pair<string, Product*>("product2",prod2));

multiset <int> soldItems;

sellProduct("product1", inventory, soldItems);
sellProduct("product2", inventory, soldItems);
sellProduct("apple", inventory, soldItems);
sellProduct("product1", inventory, soldItems);
sellProduct("product1", inventory, soldItems);
sellProduct("product2", inventory, soldItems);

soldItemsList(inventory, soldItems);

cout<<"Total sales = " << checkSales(inventory, soldItems) << endl;

delete
prod1;
delete
prod2;
return
0;
}



The output as follows:

No comments:

Post a Comment