CS计算机代考程序代写 data structure compiler Maps

Maps

Data Structures and Abstractions
MAPS

Lecture 20

Note 1
When you compile some STL code in VC++ you might get a warning: [1]

ICT283\Code\Sets\SetDifference.cpp(59) : warning C4786: ‘std::pair,std::allocator>::_Kfn,std::less,std::allocator >::const_iterator,std::_Tree,std::allocator>::_Kfn,std::less,std::allocator >::const_iterator>’ : identifier was truncated to ‘255’ characters in the debug information

This is the only warning you can ignore completely (a debug identifier)
If it really annoys you, then add the following code before the includes in the file that is generating the warning:

#pragma warning (disable : 4786)
Do not disable any other warning!!

1
Not likely with these days. Might happen in older versions of VC++
*

Note 2
If you get an error message such as:

ICT283\Code\Map\Map.cpp(57) : error C2440: ‘initializing’ : cannot convert from ‘class std::_Tree,class std::allocator >,struct std::pair IntSet;
{
IntSet::iterator itr = aset.begin(); // itr can be used to modify
}
To solve it, use a const_iterator, instead of an iterator: [2]

void DoSomething (const IntSet &aset)
{

IntSet::const_iterator itr = aset.begin();
}

*
[1]
stuff like this is covered in the textbook – so please read the textbook.
See section on typedef const_iterator, Chapter on STL
Lecture notes wouldn’t contain everything in the textbook.

[2]
Note that aset is declared as a const reference.
Setting a normal iterator can’t guarantee the const declaration, so the compiler would not be happy as it
can’t enforce your design decision.

so you need a const iterator.

Maps
An association (pairing) is a connection between two things, for example the word “sanity” (key) is associated with the definition (value) “the state of having a normal healthy mind”*
A dictionary or map is then a collection of key-value associations [1].
The first part of the pair is often called a key.
The data in maps is inserted, deleted and found using the key. So key needs to be unique but value need not be. [2]
For example, if one had a map that was an English dictionary, then we would expect to be able to retrieve the definition of sanity using something like:

dictionary.GetDefinition (“sanity”);
or even
dictionary[“sanity”];
* Australian Dictionary, Collins, 2005

*
[1] Sometimes called Associative array

[2] Multimaps are used if keys are not unique.

Also see unordered_map (C++11). Hashing is used on the key for fast access. Operator[] is fast.

The STL Map
The STL map is a very nice template indeed.
The declaration requires two data types, the first being the key and the second being the data to be stored in association with the key. [1]
For example, consider a class taking a vote on who should be the class president. We want to associate names with an integer number of votes:

#include

…
map Popularity;
…
Popularity pop;

*
[1] Like set in STL, map in STL is an associative container so sorted automatically on insertion. It is sorted on Key called first.

A Simple Map Program
// Normal comments up here

#include

#include
#include
#include

using namespace std;

//——————————————————

const string END = “end”; // string object

//——————————————————

typedef map Popularity;
typedef Popularity::iterator PopItr;
typedef Popularity::const_iterator PopCItr; // see textbook chapter on STL

It can be really useful to define an iterator for each STL type you use

//——————————————————

void AddData (Popularity &pop);
void Output (const Popularity &pop);

//——————————————————

int main ()
{
Popularity pop;

AddData (pop);
Output (pop);

cout << endl; return 0; } //------------------------------------------------------ void AddData (Popularity &pop) { string name; // Prime the while loop cout << "Enter vote name, or “ << END << “ to finish: "; getline (cin, name); while (name != "end") // is this comparison efficient? [1] { // If they are part of the map already, this adds 1 // to their score. If they are not, it puts them // in the map and gives them a score of 1. // see missing code in the notes section [2] cout << "Enter vote name, or 'end' to finish: "; getline (cin, name); } } * [1] What is happening behind the scenes? name is a string object, but “end” is a null terminated char array. Types are different. If it was some other class comparison? What happens if the user enters “end” as the first data? [2] // If this person is not yet in the map if (pop.find(name) == pop.end()) { // Add them to the map pop[name] = 1; } else { // Otherwise just increment the number of votes in the map pop[name]++; Just using pop[name] on its own can insert the value in name into pop, with this value being a new key, with the corresponding value an empty string. So, it is better to use find. Operator[] of map has logrithmic complexity. This operator on unordered_map is faster – constant complexity, as hashing is used //------------------------------------------------------ void Output (const Popularity &pop) { PopCItr winner = pop.begin(); // set a temp winner as the first item // For each entry in the map for (PopCItr itr = pop.begin(); itr != pop.end(); itr++) { // Output the first and second parts of the pair (association) cout << setw(20) << itr->first << “ : " << itr->second << endl; // Now check if this person should be the winner if (winner->second < itr->second) // compare the value [1]
{
winner = itr;
}
}

// Output the winner
cout << endl << "The new class president is " << winner->first
<< " with " << winner->second << " votes" << endl; [2] } //------------------------------------------------------ * [1] the map is sorted by key but we are not interested in sorting by key, but looking for the highest value. Members first and second are public of struct pair. Map stores elements of struct pair. [2] What happens if all candidates get the same vote? Readings Textbook: Chapter on Standard Template Library.

Related Posts