REVISED: Sunday, March 3, 2013
CONTENTS:
I. ASSUMPTIONS
II. C++ MAP AND MULTIMAP VOCABULARY
III. INSTANTIATING A MAP AND MULTIMAP OBJECT
IV. INSERTING ELEMENTS INTO A STL MAP AND MULTIMAP
V. FINDING ELEMENTS IN A STL MAP AND MULTIMAP
VI. BASIC MAP AND MULTIMAP MEMBER FUNCTIONS
VII. STL MAP AND MULTIMAP EXAMPLE PROGRAM SOURCE CODE
VIII. STL MAP AND MULTIMAP PROGRAM ANALYSIS
YOU WILL LEARN:
1. C++ map and multimap vocabulary.
2. How to instantiate a map and multimap object.
3. How to insert elements into a STL map and multimap.
4. How to find elements in a STL map and multimap.
5. Member functions used by a map and multimap.
• I. ASSUMPTIONS
I assume you have never programmed using C++ STL map and multimap functionality.
I assume you have a C++ compiler.
• II. C++ MAP AND MULTIMAP VOCABULARY
A. What is STL?
STL is the Standard Template Library. The STL contains six kinds of components:
2. Container Adapters
3. Iterators
4. Algorithms
5. Function Objects
6. Function Adapters
To understand and use the STL, you must have a complete understanding of the C++ language, including pointers, references, and templates.
Containers are objects that hold other objects.
Iterators are objects that act, more or less, like pointers. They give you the ability to cycle through the contents of a container in much the same way that you would use a pointer to cycle through an array.
The map and multimap are key-value pair containers that allow for a lookup on the basis of a key. The difference between map and multimap is that only the latter allows for duplicates, whereas the former can store only unique keys. Map and multimap are container classes that help with applications that require frequent and quick searches. Most functions in a map and multimap work in a similar fashion; accept similar parameters; and return similar value types. To use the STL map and multimap classes you need to use #include <map>.
STL map and multimap are template classes that need to be instantiated before you can use any of their member functions.
A. A STL map and multimap instantiation has three parameters:
2. value type
3. an optional binary predicate
Any data type for which a comparison operator can be defined can be used as a key.
Each element in a multimap is identified by its key value; and multiple elements can have the same key value.
B. A predicate is a special type of function. There are two types of predicates:
2. binary
A unary predicate takes one argument while a binary predicate takes two. A binary predicate is the most common map and multimap instantiation syntax parameter.
C. The example program contains the following two instantiations.
Is a multimap instantiation of the object words with a key of type string, a value type int, using the default sort criterion. A multimap can have duplicate keys. This means using a multimap each word is a key and each line is a value. Therefore, the words are sorted upon insertion alphabetically by line number. Duplicate words are in alphabetical groups sorted by line number.
Is a map instantiation of the object lines with a key type of int, and a value type string, using the default sort criterion. A map has to have unique keys, no duplicates allowed. This means using a map each line is a key and each string of words is a value. Therefore, the lines are sorted upon insertion numerically, and each matching strings of words is sorted alphabetically. Duplicate words can appear alphabetically within a string on one line; and on more than one line, alphabetically within strings.
• IV. INSERTING ELEMENTS INTO A STL MAP AND MULTIMAP
As with all the containers, you can use a map or a multimap to store objects of types you create. Values can be inserted into a map or a multimap using the insert() operation. Note that the argument must be a key-value pair. The first field in each pair is taken to be a key, while the second field is a value.
The example program creates a file named example.txt; and inserts six sentences into example.txt.
The int SearchExampleTxtFile(); function uses the insert(); function to insert example.txt into a map and a multimap. example.txt consists of lines and words. The line numbers are unique. The words in each line are not unique.
The map can not have duplicate keys. Each line number is unique; therefore, it becomes the key for the map. The words in each line are not unique; however, as a string of words they become a value. This provides the compiler with ordered pairs of lines and strings of words for the map.
The multimap can have duplicate keys. Each word becomes a key for the multimap. Each line becomes a value for the multimap. This provides the compiler with ordered pairs of words and lines for the multimap.
• V. FINDING ELEMENTS IN A STL MAP AND MULTIMAP
Maps are sorted containers. Elements inserted into a map or multimap are sorted on insertion.
Associative containers such as map and multimap feature a member function called find() that allows you to find a value given a key.
The attached sample program int SearchExampleTxtFile(); function uses the member function find() to find words requested by the user. The iterator returned by the find() member function points to the first element found.
The member function called count() is used to determine the number of pairs in the map that have the same key.
A map or multimap arrange all elements of a value in sequential positions. When using a multimap, we simply move the iterator that many elements forward to access other pairs containing the same key.
The bounds of the range are supplied by functions lower_bound() and upper_bound().
The following basic map and multimap member functions are used in the example program.
count(); with a key as an argument, will return a count of the number of entries found corresponding to the key. A map count() return value can only be 0 or 1 because a map only allows unique keys. A multimap allows duplicates; therefore, the count() return value depends on the number of duplicates.
find(); function returns an iterator to the matching element or to the end of the map if the key is not found. Once the map has been initialized with keys and values, you can search for a value given its key by using the find(); function. When a match is found, the value associated with the key is contained in the second member pair.
C. insert();
insert(); function allows you to insert one or more pairs into a map.
D. iterator();
iterator(); function is any object that, pointing to some element in a range of elements such as a container, has the ability to iterate through the elements of that range.
lower_bound(); function finds the first point in the sequence that is not less than a specified value.
F. make_pair();
make_pair(); function is defined as a template function, so it automatically deduces the type for the pair from the argument types you supply. The advantage of make_pair() is that the types of the objects being stored are determined automatically by the compiler rather than being explicitly determined by the programmer.
G. pair();
pair(); function, key/value pairs are stored in a map as objects of type pair. The pair template class is used to construct the key/value pairs. The data types specified by pair must match those of the map into which the pairs are being inserted. pair(); returns a pair of iterators that point to the first and last elements in the map that contain the specified key.
H. upper_bound();
upper_bound(); function finds the last point in a sequence that is not greater than some value.
Please copy and paste the example program into a file your compiler can read. Then build, compile, and debug the program. Following along, back and forth, between the tutorial and your copy of the program will help you understand the map and multimap functionality.
//C++ STL MAP AND
//MULTIMAP CONTAINER
//CLASSES TUTORIAL
//***********************
#include <fstream>
//Needed for file I/O.
#include <iomanip>
//Needed for format
//manipulation.
#include <iostream>
#include <map>
//Needed for STL classes map
//and multimap.
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
//Needed for converter
//functions.
#include <string>
using std::istringstream;
//Needed for STL classes map
//and multimap.
using std::ifstream;
//Needed for STL classes map
//and multimap.
using std::string;
//Needed for STL classes map
//and multimap.
using std::cout;
//Needed for STL classes map
//and multimap.
using std::cin;
//Needed for STL classes map
//and multimap.
using std::cerr;
//Needed for STL classes map
//and multimap.
using std::map;
//Needed for STL classes map
//and multimap.
using std::multimap;
//Needed for STL classes map
//and multimap.
using namespace std;
//***********************
//In general, C++ strings are
//preferred over C strings.
//***********************
int UserLoop();
//This function is the user
//prompted loop.
void UserPause();
//This function prompts the
//user to continue.
int UserMenu();
//This function prints a menu
//to the console.
void UserSwitch(int choice);
//This function is a switch.
void CreateExampleTxtFile();
//This function creates a file
//named example.txt.
void PrintExampleTxtFile();
//This function reads and
//prints a file named
//example.txt.
void SizeExampleTxtFile();
//This function computes and
//prints the size of the
//example.txt file.
int SearchExampleTxtFile();
//This function searches
//example.txt file for a user
//inputted string.
//***********************
//This is the main function.
int main(int argc, char* argv[])
{
UserLoop();
return 0;
}
//***********************
//This function is the user
//prompted loop.
int UserLoop()
{
int choice = 0;
//Instantiates choice as an
//object of class type int,
//initializing it's value to 0.
bool exitt = false;
//Instantiates exitt as an
//object of class type bool
//initializing it's value to false.
do
{
UserMenu();
cout << endl << endl << endl;
cout << " Type the number 1 and press return to run this program again." << endl << endl << endl;
cout << " Type any key and press return to exit ==> ";
cin >> choice;
if (choice == 1)
exitt = false;
else
exitt = true;
}while(exitt == false);
UserPause();
return 0;
}
//***********************
//This function prompts the
//user to continue.
void UserPause()
{
cout << endl << endl << endl;
cout << " ";
system("PAUSE");
}
//***********************
//This function prints a menu
//to the console.
int UserMenu()
{
int choice = 0;
//Instantiates choice as an
//object of class type int,
//initializing it's value to 0.
system("CLS");
cout << endl << endl << endl;
cout << " MENU" << endl;
cout << " ************************" << endl << endl;
cout << " 1 Create a new file." << endl;
cout << " 2 Print a new file." << endl;
cout << " 3 Size a new file." << endl;
cout << " 4 Search a new file." << endl << endl;
cout << " Enter 0 to exit." << endl << endl;
cout << " Please type a number from 0 to 4 and then press enter ==> ";
//Get customer input.
cin >> choice;
UserSwitch(choice);
//Test validity of user input data.
return 0;
}
//***********************
//This function is a switch.
void UserSwitch(int choice)
{
switch(choice)
{
//Call class member functions.
case 0:
break;
case 1:
CreateExampleTxtFile();
//Create new file.
break;
case 2:
PrintExampleTxtFile();
//Print new file.
break;
case 3:
SizeExampleTxtFile();
//Size new file.
break;
case 4:
SearchExampleTxtFile();
//Search new file.
break;
default:
cout << endl << endl << endl;
cout << " Please select again." << endl << endl;
break;
}
}
//***********************
//This function creates a
//file named example.txt
//and inserts six sentences
//into example.txt.
void CreateExampleTxtFile()
{
ofstream myfile;
//ofstream class initialization
//of object myfile.
myfile.open ("example.txt");
//Opens myfile initialized with
//example.txt.
if (myfile.is_open())
//Checks to see if example.txt
//file is open.
{
system("CLS");
cout << endl << endl << endl;
myfile << "one two three four five\n";
//Extracts text line to
//example.txt line at a time.
cout << " ";
cout << "one two three four five\n";
myfile << "two three four five six\n";
cout << " ";
cout << "two three four five six\n";
myfile << "three four five six seven\n";
cout << " ";
cout << "three four five six seven\n";
myfile << "four five six seven eight\n";
cout << " ";
cout << "four five six seven eight\n";
myfile << "five six seven eight nine\n";
cout << " ";
cout << "five six seven eight nine\n";
myfile << "six seven eight nine ten\n";
cout << " ";
cout << "six seven eight nine ten\n";
myfile.close();
//Closes example.txt.
}
else cout << " Unable to open file";
}
//***********************
//This function reads and
//prints a file named
//example.txt.
void PrintExampleTxtFile()
{
string line;
//Instantiates line as
//an object of class type string.
ifstream myfile ("example.txt");
system("CLS");
if (myfile.is_open())
//Checks to see if
//example.txt file is open.
{
cout << endl << endl << endl;
while (! myfile.eof())
//eof(); returns true
//when end of file
//has been reached,
{
//otherwise it returns false.
getline (myfile, line);
cout << " " << line << endl;
}
myfile.close();
//Closes example.txt.
}
else cout << " Unable to open file";
}
//***********************
//This function computes
//and prints the size
//of the example.txt file.
void SizeExampleTxtFile()
{
long begin;
//Instantiates begin
//as an object of class
//type long.
long end;
//Instantiates end
//as an object of
//class type long.
ifstream myfile ("example.txt");
//Determine whether the
//stream object is currently
//associated with a file, if so,
//file is open.
begin = myfile.tellg();
//tellg(); is used to get the
//beggining position in the
//stream
myfile.seekg (0, ios::end);
//after it has been moved
//with seekg(); to the end of
//the stream;
//therefore, determining the
//size of the file.
end = myfile.tellg();
//tellg(); is used to get the
//ending position in the stream
myfile.close();
//closes file.
system("CLS");
cout << endl << endl << endl;
cout << " File size is: " << (end - begin) << " bytes.\n";
//end - begin determines size
//of the file.
}
//***********************
//This function searches
//example.txt file for a user
//inputted string.
int SearchExampleTxtFile()
{
const int SIZE = 200;
//Constant for size of
//character string.
char fileName[SIZE];
//Holds user file name.
ifstream inputFile;
//Input file.
int counter = 0;
//Counts string occurences.
system("CLS");
//***********************
//Get user's file name.
cout << endl << endl << endl;
cout << " Enter the name of the file you want to search.\n\n";
cout << " For example;
example.txt \n\n";
cout << " Then press return ==> ";
cin >> fileName;
//FileName is example.txt.
//***********************
//Open user's file.
inputFile.open(fileName);
if(!fileName)
{
cout << endl << endl << endl;
cout << " Cannot open " << fileName << endl;
cout << endl << endl << endl;
cout << " ";
system("pause");
}
//***********************
//Loads example.txt into
//multimap and map
multimap<string, int> words;
//Key words and Value lines;
//multimap can take duplicate
//key values.
map<int, string> lines;
//Key lines and Value words;
//map can not take duplicate
//key values.
string str;
//Instantiates str as an object
//of type string.
ifstream input(fileName);
//ifstream provides an
//interface to read data from
//files as input streams.
if(input.fail())
//Test if example.txt opened.
{
cerr << "\n The file could not be opened.";
//Error message if example.txt
//not opened.
return -1;
//Returns -1 if example.txt not
//opened.
}
//***********************
//Close user's file.
inputFile.close();
//Closes example.txt.
//***********************
//Insert into words and lines
int i = 1;
//Instantiates i as an object of
//class type int, initializing it
//value to 1.
while(getline(input, str))
{
istringstream in(str);
string s;
//Instantiates s as an object of
//class type string.
while(in >> s)
{
words.insert(make_pair(s, i));
//Insert into object words
}
lines.insert(make_pair(i, str));
//Insert into object lines
i++;
}
//***********************
string search;
cout << endl << endl << endl;
cout << " Enter the word or string of words you are searching for.\n\n";
cout << " For example; six \n\n";
cout << " Then press return ==> ";
cin >> search;
system("CLS");
//***********************
cout << "\n The number of matches = " << words.count(search) << '\n';
//count() function returns
//number pairs with same key;
//for multimap key is a word.
multimap < string,int>::iterator it1 = words.lower_bound(search);
//lower_bound() function
//returns start of range of
//pairs with same key; for
//multimap key is a word.
multimap < string,int>::iterator it2 = words.upper_bound(search);
//upper_ bound() function
//returns end of range of pairs
//with same key; for multimap
//key is a word.
while(it1 != it2)
{
int x = it1->second; //example.txt line; second
//contains the value; for map
//value is string of words
map<int, string>::iterator iter = lines.find(x);
cout << '\n' << " Key => Line " << x << " Value => " << iter->second << '\n';
//example.txt line; x is line
//number; second contains the
//value; for map value is string
//of words.
it1++;
while(true)
{
if(it1 != it2 && it1->second == x)
//example.txt line; second is
//the value; for map value is
//string of words.
{
it1++;
}
else
{
break;
}
}
}
return 0;
}
//***********************
• IX. STL MAP AND MULTIMAP EXAMPLE PROGRAM ANALYSIS
The example program consists of the following eight functions.
int UserLoop(); function is the only function in the main() function. It is called when the program begins. It is used to contain a user prompted loop to exit the program or for repeated use of the program. This function calls the int UserMenu(); function.
B. void UserPause();
Function contains system(“PAUSE”);
void UserPause(); function contains system(“PAUSE”); which prompts the user to press any key to continue. It is used to hold information on the console long enough for the user to read the information. This function does not call any other functions.
function is called by the int UserLoop();
int UserMenu(); function is called by the int UserLoop(); function when the program
begins. It is used to contain the program menu. The menu provides the user with five options: create a new file; print the new file; size the new file; search the new file; or exit the program. This function prompts the user to pick one of the five options. After the user makes a selection, this function calls the UserSwitch(choice); function.
void UserSwitch(int choice); function is called by the int UserMenu(); function. It is a switch with five cases: 0 to exit the program; 1 to create a new file; 2 to print the new file; 3 to size the new file; and 4 to search the new file. Choice 1 calls the void CreateExampleTxtFile(); function. Choice 2 calls the void PrintExampleTxtFile(); function. Choice 3 calls the void SizeExampleTxtFile(); function. Choice 4 calls the int SearchExampleTxtFile(); function.
void CreateExampleTxtFile();
function is called by the void UserSwitch(int choice); function. It creates a file named example.txt. Opens the file, inserts six sentences into example.txt one line at a time. As each line is inserted into the file it is echo printed to the console. Then it closes the file. This function does not call any other functions.
F. void PrintExampleTxtFile();
void PrintExampleTxtFile(); function is called by the void UserSwitch(int choice); function. Opens the file, prints the file to the console; and, closes the file. This function does not call any other functions.
G. void SizeExampleTxtFile();
void SizeExampleTxtFile(); function is called by the void UserSwitch(int choice); function. Opens the file, sizes the file, prints the size to the console; and, closes the file. This function does not call any other functions.
int SearchExampleTxtFile(); function is called by the void UserSwitch(int choice); function. It prompts the user for a file name. Opens the file the user requests. Reads the file and inserts the files contents into a map and multimap. Closes the user requested file. Prompts the user for a word or string of words to search for. Finds the word or string of words per the user’s request. Prints the word or string of words on the console.
1. C++ map and multimap vocabulary.
2. How to instantiate a map and multimap object.
3. How to insert elements into a STL map and multimap.
4. How to find elements in a STL map and multimap.
5. Member functions which can be used with a map and multimap.
Elcric Otto Circle
How to Link to My Home Page
It will appear on your website as:"Link to ELCRIC OTTO CIRCLE's Home Page"
No comments:
Post a Comment