• No results found

• The “string” class

N/A
N/A
Protected

Academic year: 2022

Share "• The “string” class"

Copied!
31
0
0

Loading.... (view fulltext now)

Full text

(1)

IIT Bombay

Computer Programming

Dr. Deepak B Phatak Dr. Supratik Chakraborty

Department of Computer Science and Engineering IIT Bombay

Session : Template Class “map”

(2)

IIT Bombay

• Object-oriented programming with structures and classes

• Template classes and functions

• C++ Standard Library

• The “string” class

• The “vector” class

2 Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay

Quick Recap of Relevant Topics

(3)

IIT Bombay

• The template class “map”

Overview of This Lecture

(4)

IIT Bombay

Acknowledgment

• Much of this lecture is motivated by the treatment in An Introduction to Programming Through C++

by Abhiram G. Ranade

McGraw Hill Education 2014

Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay 4

(5)

IIT Bombay

The “map” class

• For representing associative one-dimensional arrays/vectors

• Arrays in which index is not necessarily an integer

• Indices are objects of specified types, e.g. string, V3, …

• Example usage: marks[“Shyam”], position[“BA207”]

• Notation: key (or index) and value

Key type and value type are completely independent Key values must be ordered by (overloaded) < operator

Array of double values Indexed by strings

Array of V3 values (3-dimensional vectors)

Indexed by strings

(6)

IIT Bombay

The “map” class

• For representing associative one-dimensional arrays/vectors

• Template class : Can be instantiated with key type and value type

• Internally, elements stored as (key, value) pairs and sorted by key

• Internal representation: binary search tree

• Dynamic memory management built in

• “map” objects are container objects

• Must use #include <map> at start of program

• Large collection of member functions

• We’ll see only a small subset

Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay 6

(7)

IIT Bombay

The “pair” Template Class in Maps

• C++ Standard Library provides a template class pair<T1, T2> with two data members named first (of type T1) and second (of type T2)

• Every map<key_type, value_type> object is really a collection of

(key, value) pairs stored as pair<key_type, value_type> objects

(8)

IIT Bombay

Simple Programming using “map”

#include <iostream>

#include <map>

using namespace std;

int main() {

map<string, double> marks;

string stName; double stMarks;

while (true) {

cout << “Give name of student: “; cin >> stName;

if (stName == “end”) {cout << “Bye!!!” << endl; break;}

else { cout << “Give marks: “; cin >> stMarks; marks[stName] = stMarks; } }

… Some other code …

}

Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay 8

Key type: string Value type: double

Name of map

(9)

IIT Bombay

Simple Programming using “map”

#include <iostream>

#include <map>

using namespace std;

int main() {

map<string, double> marks;

string stName; double stMarks;

while (true) {

cout << “Give name of student: “; cin >> stName;

if (stName == “end”) {cout << “Bye!!!” << endl; break;}

else { cout << “Give marks: “; cin >> stMarks; marks[stName] = stMarks; } }

… Some other code …

}

Create an empty map of

(string, double) pairs

(10)

IIT Bombay

Writing/Inserting “map” Elements

Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay 10

Accessing an element indexed by string

#include <iostream>

#include <map>

using namespace std;

int main() {

map<string, double> marks;

string stName; double stMarks;

while (true) {

cout << “Give name of student: “; cin >> stName;

if (stName == “end”) {cout << “Bye!!!” << endl; break;}

else { cout << “Give marks: “; cin >> stMarks; marks[stName] = stMarks; } }

… Some other code …

}

(11)

IIT Bombay

Writing/Inserting “map” Elements

If (key, value) pair with key matching stName does not exist in marks, create a new (stName, stMarks) pair and add

to marks

#include <iostream>

#include <map>

using namespace std;

int main() {

map<string, double> marks;

string stName; double stMarks;

while (true) {

cout << “Give name of student: “; cin >> stName;

if (stName == “end”) {cout << “Bye!!!” << endl; break;}

else { cout << “Give marks: “; cin >> stMarks; marks[stName] = stMarks; } }

… Some other code …

}

(12)

IIT Bombay

Writing/Inserting “map” Elements

Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay 12

If (key, value) pair with key matching stName already exists in marks, update the value of this pair to stMarks and

erase the previous value

#include <iostream>

#include <map>

using namespace std;

int main() {

map<string, double> marks;

string stName; double stMarks;

while (true) {

cout << “Give name of student: “; cin >> stName;

if (stName == “end”) {cout << “Bye!!!” << endl; break;}

else { cout << “Give marks: “; cin >> stMarks; marks[stName] = stMarks; } }

… Some other code …

}

(13)

IIT Bombay

Over-writing “map” Elements

• What happens if we execute the following code ? marks[stName] = stMarks;

marks[stName] = stMarks + 10;

Insert/update (key, value) pair

Update value in (key, value) pair

(14)

IIT Bombay

Reading “map” Elements

Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay 14

Accessing an element indexed by string

Gives value associated with key stName

#include <iostream>

#include <map>

using namespace std;

int main() {

map<string, double> marks;

string stName; double stMarks;

… Some other code … while (true) {

cout << “Give name of student: “; cin >> stName;

if (stName == “end”) {cout << “Bye!!!” << endl; break;}

else { cout << “Marks of “ << stName << “ is: “ << marks[stName] << endl; } }

return 0;}

(15)

IIT Bombay

Reading “map” Elements

What if stName is “Abdul” but no (key, value) pair with key matching “Abdul” exists in marks?

#include <iostream>

#include <map>

using namespace std;

int main() {

map<string, double> marks;

string stName; double stMarks;

… Some other code … while (true) {

cout << “Give name of student: “; cin >> stName;

if (stName == “end”) {cout << “Bye!!!” << endl; break;}

else { cout << “Marks of “ << stName << “ is: “ << marks[stName] << endl; } }

return 0;}

(16)

IIT Bombay

Reading “map” Elements

Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay 16

#include <iostream>

#include <map>

using namespace std;

int main() {

map<string, double> marks;

string stName; double stMarks;

… Some other code … while (true) {

cout << “Give name of student: “; cin >> stName;

if (stName == “end”) {cout << “Bye!!!” << endl; break;}

else { cout << “Marks of “ << stName << “ is: “ << marks[stName] << endl; } }

return 0;}

A new (key, value) pair is created with key set to “Abdul” and value obtained from default

constructor of value type (here, double)

What if stName is “Abdul” but

no (key, value) pair with key

matching “Abdul” exists in marks?

(17)

IIT Bombay

Reading “map” Elements

#include <iostream>

#include <map>

using namespace std;

int main() {

map<string, double> marks;

string stName; double stMarks;

… Some other code … while (true) {

cout << “Give name of student: “; cin >> stName;

if (stName == “end”) {cout << “Bye!!!” << endl; break;}

else { cout << “Marks of “ << stName << “ is: “ << marks[stName] << endl; } }

return 0;}

A new (key, value) pair is created with

key = “Abdul” and value = value returned by default constructor of double

What if stName is “Abdul” but no (key, value) pair with key matching “Abdul” exists in marks?

Garbage: value returned by

default constructor of double

(18)

IIT Bombay

Accessing Elements using at

• Like vectors, we can use

marks.at(stName) instead of marks[stName]

If stName doesn’t match the key of any (key, value) pair in marks, an out_of_range exception is thrown

Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay 18

(19)

IIT Bombay

Comparing Key Values

• (key, value) pairs are stored sorted by key values Requires a comparison operator for key values Preferable: operator< defined for key type map<string, double> marks;

operator< already defined in string class:

Lexicographic (dictionary) order

“Abdul” < “Ajanta” < “Bobby”

(20)

IIT Bombay

Comparing Key Values

• (key, value) pairs are stored sorted by key values Preferable: operator< defined for key type

What if operator< is not pre-defined for key type?

Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay 20

Custom-define operator< function (operator overloading) bool operator<(key_type &a, key_type &b) { … }

Must ensure that < is transitive and anti-symmetric

a < b and b < c implies a < c a < b implies b < a

(21)

IIT Bombay

Comparing Key Values

• (key, value) pairs are stored sorted by key values Preferable: operator< defined for key type

What if operator< is not pre-defined for key type?

Custom-define operator< function (operator overloading) bool operator<(key_type &a, key_type &b) { … }

Must ensure that < is transitive and anti-symmetric

Must ensure that every pair of distinct keys are ordered

a and b distinct implies either a < b or b < a

(22)

IIT Bombay

Comparing Key Values

• (key, value) pairs are stored sorted by key values Preferable: operator< defined for key type

What if operator< is not pre-defined for key type?

Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay 22

Custom-define operator< function (operator overloading) bool operator<(key_type &a, key_type &b) { … }

Must ensure that < is transitive and anti-symmetric

Must ensure that every pair of distinct keys are ordered

Custom-define separate comparison function and indicate in map declaration

Won’t cover in our discussions ….

(23)

IIT Bombay

Iterator Related Functions in “map” Class

#include <iostream>

#include <map>

using namespace std;

int main() {

map<string, double> marks;

marks[“Ajanta”] = 10.0; marks[“Bobby”] = 15.0; marks[“Abdul”] = 25.0;

map<string, double>::iterator it;

for (it = marks.begin(); it != marks.end(); it++) { cout << it->first << “ : “ << it->second << endl;

}

return 0;

}

begin(), end()

member functions

Abdul: 25.0 Ajanta : 10.0 Bobby : 15.0 Recall: elements of map

are (key, value) pairs

(24)

IIT Bombay

Iterator Related Functions in “map” Class

#include <iostream>

#include <map>

using namespace std;

int main() {

map<string, double> marks;

marks[“Ajanta”] = 10.0; marks[“Bobby”] = 15.0; marks[“Abdul”] = 25.0;

map<string, double>::reverse_iterator rit;

for (rit = marks.rbegin(); rit != marks.rend(); rit++) { cout << rit->first << “ : “ << rit->second << endl;

}

return 0;

}

Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay 24

rbegin(), rend() member functions

Bobby: 15.0

Ajanta : 10.0

Abdul: 25.0

(25)

IIT Bombay

Finding if an Element Exists in a Map

int main() {

map<string, double> marks; string stName;

… Some other code … while (true) {

cout << “Give name of student: “; cin >> stName;

if (stName == “end”) {cout << “Bye!!!” << endl; break;}

else { if (marks.count(stName) > 0) {cout << “Marks: “ << marks[stName] << endl;}

else { cout << “No student with name: “ << stName << endl;}

} }

return 0;}

(26)

IIT Bombay

Finding if an Element Exists in a Map

Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay 26

int main() {

map<string, double> marks; string stName;

… Some other code … while (true) {

cout << “Give name of student: “; cin >> stName;

if (stName == “end”) {cout << “Bye!!!” << endl; break;}

else { if (marks.count(stName) > 0) {cout << “Marks: “ << marks[stName] << endl;}

else { cout << “No student with name: “ << stName << endl;}

} }

return 0;}

Counts number of pairs with key same as stName

Returns 1 if map contains an element with

key stName, otherwise returns 0

(27)

IIT Bombay

Finding if an Element Exists in a Map

int main() {

map<string, double> marks;

… Other code …

map<string, double>::iterator it = marks.find(stName);

if (it != marks.end()) {cout << “Marks: “ << it->second << endl;}

else { cout << “No student with name: “ << stName << endl;}

return 0;

}

Returns an iterator to (key, value)

pair with key matching stName

(28)

IIT Bombay

Finding the Count of Elements in a Map

Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay 28

int main() {

map<string, double> marks;

marks[“Ajanta”] = 10.0; marks[“Bobby”] = 15.0;

marks[“Abdul”] = 25.0;

cout << “Size : “ << marks.size() << endl;

marks[“Alex”] = 14.5; marks[“Ajanta”] = 11.0;

cout << “Size : “ << marks.size() << endl;

return 0;

}

Size : 3

Size : 4

(29)

IIT Bombay

Deleting Elements from a Map

int main() {

map<string, double> marks;

marks[“Ajanta”] = 10.0; marks[“Bobby”] = 15.0;

marks[“Abdul”] = 25.0;

map<string, double>::iterator it = marks.find(“Abdul”);

marks.erase(it); marks.erase(“Bobby”);

cout << “Size : “ << marks.size() << endl;

for (it = marks.begin(); it != marks.end(); it++) { cout << it->first << “ : “ << it->second << endl;

}

return 0;

}

Ajanta : 10.0

Size : 1

(30)

IIT Bombay

Maps of Complex Data Types

• “map” is a template class

Can be instantiated to maps of complex data types map<string, V3> flightPosition;

map<string, map<double, V3> > timedFlightPosition;

Dr. Deepak B. Phatak & Dr. Supratik Chakraborty, IIT Bombay 30

Note the space

(31)

IIT Bombay

Summary

• “map” class and its usage

• Only some features studied

• Several more features exist …

References

Related documents

• Hierarchy/ Levels still form the foundation for Total Reward structures however the new world of work may challenge the status quo - Organisations with pure dependence

o The new item can be added using assignment operator or The value of existing items can be updated using assignment operator. o If the key is already present, value gets updated,

Observations on the output of oospores, their liberation, viabiliiy and germination in SaAgfassi/m swez/z/V (Turn) C. Semi Sea Salt and Piants, CSMCRI, Bhavnagar, pp. An estimate

Inland fish culture is also showing very good signs where increased production could be achieved but there are several constraints, particu- larly in relation to

The contents of this publication, at a glance, are functioning of administrative units in the State, population, economic profile, State Budget, agriculture and

Global energy-related CO 2 emissions are expected to reduce by 8% in 2020, the largest contraction since the World War II. But that will not be anything to celebrate. What matters

(iii) The light and heavy key components are identified. au&lt;JHK at the average column temperature is calculated. 4 and Napt is calculated. The resulting values are

Static group signatures consist of four polynomial time algorithm[27] namely key generation where system generates group public key with the secret key generation for signing