Sample Input 2

  

3           (# "good" pairings <= 100,000)
A B
G L
J K
2           (# "bad" pairings <= 100,000)
D F
D G
4           (# paired groups <= 100,000)
A C G
B D F
E H I
J K L

How to store the data

What is the problem with this representation of the input data ? 

3           
A B        GoodPair[0][0] = "A" GoodPair[0][1] = "B"
G L	   GoodPair[1][0] = "G" GoodPair[1][1] = "L"
J K	   GoodPair[2][0] = "J" GoodPair[2][1] = "K"
2           
D F	   BadPair[0][0] = "D"  BadPair[0][1] = "F"
D G	   BadPair[1][0] = "D"  BadPair[1][1] = "G"
4           
A C G      Grp[0][0] = "A" Grp[0][1] = "C" Grp[0][2] = "G"
B D F	   Grp[1][0] = "B" Grp[1][1] = "D" Grp[1][2] = "F"
E H I	   Grp[2][0] = "E" Grp[2][1] = "H" Grp[2][2] = "I"
J K L	   Grp[3][0] = "J" Grp[3][1] = "K" Grp[3][2] = "L"

How to store the data

Problem:   we need to search (a large array to finr the group of any name 

3           
A B        GoodPair[0][0] = "A" GoodPair[0][1] = "B"
G L	   GoodPair[1][0] = "G" GoodPair[1][1] = "L"
J K	   GoodPair[2][0] = "J" GoodPair[2][1] = "K"
2           
D F	   BadPair[0][0] = "D"  BadPair[0][1] = "F"
D G	   BadPair[1][0] = "D"  BadPair[1][1] = "G"
4           
A C G      Grp[0][0] = "A" Grp[0][1] = "C" Grp[0][2] = "G"
B D F	   Grp[1][0] = "B" Grp[1][1] = "D" Grp[1][2] = "F"
E H I	   Grp[2][0] = "E" Grp[2][1] = "H" Grp[2][2] = "I"
J K L	   Grp[3][0] = "J" Grp[3][1] = "K" Grp[3][2] = "L"



 Finding the group for any name (GoodPair[2][0] = "J") needs a search !

Importance of data structure

 

  • How well you can represent the information used by you program is more important than how well you can program/code !!

  • There are usually many different ways to present the same information

  • How you store the data can affect:

      • How long your program will run

      • How much information your progarm need to store

  • The inefficiency of our program arised from how we store the paired groups

  • Let's look at how to represent the paired groups in more detail

Index and value

 

  • Index = the item used to access some information

  • Value = the information that you want to access

    Eample: 

     Grp[2][1] = "H"
     ^  ^     ^
     |  |     |
    indexes   value

  • Looking up values using an index(es) is a fast operation in a computer program

    (Because the data is organized in a way that makes this access fast)

The group# --> node represention

The current representation of a paired group maps a group# to the members (names) of the group: 

4           
A C G      Grp[0][0] = "A" Grp[0][1] = "C" Grp[0][2] = "G"  <-- group 0
B D F	   Grp[1][0] = "B" Grp[1][1] = "D" Grp[1][2] = "F"  <-- group 1
E H I	   Grp[2][0] = "E" Grp[2][1] = "H" Grp[2][2] = "I"  <-- group 2
J K L	   Grp[3][0] = "J" Grp[3][1] = "K" Grp[3][2] = "L"  <-- group 3
               ^        ^               ^               ^
               |        |               |               |
            group#      +---------------+---------------+
                               members in the group

Strength:    when given a group # (index), it is efficient to find (any or all) members for that group

Weakness:   when given a member (value), it is inefficient to find the group for that member

Our program need to do the latter a lot of times !!! (and never need to do the former !!)

The node --> group# represention

Alternatively, we can represent a paired group by mapping a member name to the group # like this: 

4           
A C G      Grp["A"] = 0    Grp["C"] = 0    Grp["G"] = 0     <-- group 0
B D F	   Grp["B"] = 1    Grp["D"] = 1    Grp["F"] = 1     <-- group 1
E H I	   Grp["E"] = 2    Grp["H"] = 2    Grp["I"] = 2     <-- group 2
J K L	   Grp["J"] = 3    Grp["K"] = 3    Grp["L"] = 3     <-- group 3
                ^     ^
                |     |
             member  group#
             name

Strength:    when given a member (index), it is efficient to find the group for that member

Weakness:   when given a group # (value), it is inefficient to find (any or all) members for that group

That's what we want for our program !!

The C++ map data type

 

  • The C++ map class is a storage stucture to store pairs of values: 

           (key, value)

    in a way that the pairs of values can be accessed QUICKLY using key

  • How to define a map variable: 

       #include <map>

 map<keyType,valueType> mapVarName;

The C++ map data type

 

  • How to store a (key, value) pair in a map: 

         mapVarName[ key ] = value ;

    Note:   the syntax of a map looks like that of an array, but a map is not an array!
    (In C++, a map is stored as a binary search tree....)

  • How to retrieve the value indexed by a key in a map: 

          mapVarName[ key ]

  • I will show you a program using a map variable next

A simple program using a map variable 
#include <iostream>
#include <map>

using namespace std;

int main ()
{
   // Define a map that stores: (key:string, value:int)
   map<string,int> myMap;

   // Adding (key -> value) to map
   myMap["john"]=1;
   myMap["mary"]=2;
   myMap["jake"]=3;
   myMap["anne"]=4;

   cout << "myMap[\"john\"] = " << myMap["john"] << endl;
   cout << "myMap[\"mary\"] = " << myMap["mary"] << endl;
   cout << "myMap[\"jake\"] = " << myMap["jake"] << endl;
   cout << "myMap[\"anne\"] = " << myMap["anne"] << endl;
   cout << endl;

   myMap["john"]=99;   // Updates associated value

   cout << "myMap[\"john\"] = " << myMap["john"] << endl;
   cout << "myMap[\"mary\"] = " << myMap["mary"] << endl;
   cout << "myMap[\"jake\"] = " << myMap["jake"] << endl;
   cout << "myMap[\"anne\"] = " << myMap["anne"] << endl;
   cout << endl;

   // test if a key is in the map
   cout << "myMap.count(\"john\") = " << myMap.count("john") << endl;
   cout << "myMap.count(\"mary\") = " << myMap.count("mary") << endl;
   cout << "myMap.count(\"x\") = " << myMap.count("x") << endl;

   return 0;
}

Demo: ../../DataStruct/map/01-string.cc

How to store the data

New representation: 

3           
A B        GoodPair[0][0] = "A" GoodPair[0][1] = "B"
G L	   GoodPair[1][0] = "G" GoodPair[1][1] = "L"
J K	   GoodPair[2][0] = "J" GoodPair[2][1] = "K"
2           
D F	   BadPair[0][0] = "D"  BadPair[0][1] = "F"
D G	   BadPair[1][0] = "D"  BadPair[1][1] = "G"
4           
A C G      Grp["A"] = 0    Grp["C"] = 0    Grp["G"] = 0     <-- group 0
B D F	   Grp["B"] = 1    Grp["D"] = 1    Grp["F"] = 1     <-- group 1
E H I	   Grp["E"] = 2    Grp["H"] = 2    Grp["I"] = 2     <-- group 2
J K L	   Grp["J"] = 3    Grp["K"] = 3    Grp["L"] = 3     <-- group 3

Write the program

Next:   write the program using the data structure than we have chosen : 

3           
A B        GoodPair[0][0] = "A" GoodPair[0][1] = "B"
G L	   GoodPair[1][0] = "G" GoodPair[1][1] = "L"
J K	   GoodPair[2][0] = "J" GoodPair[2][1] = "K"
2           
D F	   BadPair[0][0] = "D"  BadPair[0][1] = "F"
D G	   BadPair[1][0] = "D"  BadPair[1][1] = "G"
4           
A C G      Grp["A"] = 0    Grp["C"] = 0    Grp["G"] = 0     <-- group 0
B D F	   Grp["B"] = 1    Grp["D"] = 1    Grp["F"] = 1     <-- group 1
E H I	   Grp["E"] = 2    Grp["H"] = 2    Grp["I"] = 2     <-- group 2
J K L	   Grp["J"] = 3    Grp["K"] = 3    Grp["L"] = 3     <-- group 3

 for each "good" pair: 
    if pair not found in pair group: NViolations++

Write the program

Next:   write the program using the data structure than we have chosen : 

3           
A B        GoodPair[0][0] = "A" GoodPair[0][1] = "B"
G L	   GoodPair[1][0] = "G" GoodPair[1][1] = "L"
J K	   GoodPair[2][0] = "J" GoodPair[2][1] = "K"
2           
D F	   BadPair[0][0] = "D"  BadPair[0][1] = "F"
D G	   BadPair[1][0] = "D"  BadPair[1][1] = "G"
4           
A C G      Grp["A"] = 0    Grp["C"] = 0    Grp["G"] = 0     <-- group 0
B D F	   Grp["B"] = 1    Grp["D"] = 1    Grp["F"] = 1     <-- group 1
E H I	   Grp["E"] = 2    Grp["H"] = 2    Grp["I"] = 2     <-- group 2
J K L	   Grp["J"] = 3    Grp["K"] = 3    Grp["L"] = 3     <-- group 3

 for (int i=0; i < N1; i++) 
    if pair not found in pair group: NViolations++

Write the program

Next:   write the program using the data structure than we have chosen : 

3           
A B        GoodPair[0][0] = "A" GoodPair[0][1] = "B"
G L	   GoodPair[1][0] = "G" GoodPair[1][1] = "L"
J K	   GoodPair[2][0] = "J" GoodPair[2][1] = "K"
2           
D F	   BadPair[0][0] = "D"  BadPair[0][1] = "F"
D G	   BadPair[1][0] = "D"  BadPair[1][1] = "G"
4           
A C G      Grp["A"] = 0    Grp["C"] = 0    Grp["G"] = 0     <-- group 0
B D F	   Grp["B"] = 1    Grp["D"] = 1    Grp["F"] = 1     <-- group 1
E H I	   Grp["E"] = 2    Grp["H"] = 2    Grp["I"] = 2     <-- group 2
J K L	   Grp["J"] = 3    Grp["K"] = 3    Grp["L"] = 3     <-- group 3

 for (int i=0; i < N1; i++)
    if ( Grp[GoodPair[i][0]] != Grp[GoodPair[i][1]] ) NViolations++

 (You can code the "bad pair" as exercise...)

Demo: CCC/2022/Progs/j4-map.cc