We are going to create a MapSet data structure. You cannot use either a STL map
ID: 3738524 • Letter: W
Question
We are going to create a MapSet data structure. You cannot use either a STL map or a set in the process of building this data structure, but you may use vector, string and pair and you can use (are encouraged to use) any appropriate STL algorithms except sort. You cannot use sort! You need to keep the MapSet sorted by putting elements into the underlying vector in sorted order. Like STL sets, no two elements with the same key can exist in a set. That is, there is no duplication of a key-value pair in a MapSet
Assignment Overview In this assignment you will practice creating a combination data structure, MapSet, which combines a map and a set, without using either of their STL counterparts (map and set). You will create a class to do this work. It is due 04/09, Monday, before midnight on Mimir. That's two weeks because of the midterm on Wed, 3/28. Project is worth 60 pointer (6% of your overall grade). Background We are going to create a MapSet data structure. You cannot use either a STL map or a set in the process of building this data structure, but you may use vector, string and pair and you can use (are encouraged to use) any appropriate STL algorithms except sort. You cannot use sort You need to keep the MapSet sorted by putting elements into the underlying vector in sorted order. Like STL sets, no two elements with the same key can exist in a set. That is, there is no duplication of a key-value pair in a MapSet Details We provide a header file, projo9_mapset.h, which provides details of type for all the required methods and functions for the class MapSet. The basics are this. The MapSet class maintains a private data member vector v We interpret the pair as a key-value pair, that is the string is a key and the long is a value. That vector should always in sorted order of the string part of each pair, the key. The order is from smallest to largest as defined by the string STL type. We describe the methods below vector pair >::iterator find_key (string key) This is a private method only usable by other MapSet methods (not from a main program). Uses lower bound, returns an iterator to apair that is either the first pair in the vector that is equal to (by key) or greater than the key, orv.end (the last two meaning that the key isn't in v_). It must be private because v is private and we cannot return an iterator to a private data. To make lower bound work, you are either going to have to write a function or a lambda that compares a pair and a string. See lower bound below This function is not tested in the Mimir test set but necessary everywhere. However, it is essentially the use of lower_bound. It is a good to isolate it however for future projects. MapSet (initializer_listExplanation / Answer
*** proj09_mapset.h***
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
class MapSet {
private:
vector< pair <string, long> > v_;
public:
MapSet(initializer_list< pair <string, long> > list);
int size();
pair<string, long> get(string key);
bool update(string key, long value);
bool remove(string key);
bool add(string key, long value);
int compare(MapSet &ms);
MapSet mapset_union(MapSet &new_ms);
MapSet mapset_intersection(MapSet &new_ms);
vector< pair <string, long> > getData();
vector< pair <string, long> >::iterator find_key(string key);
vector< pair <string, long> >::iterator lower_bound(vector< pair <string, long> >::iterator first, vector< pair <string, long> >::iterator last, string val);
friend ostream& operator<<(ostream &out, MapSet &ms) ;
};
*** proj09_mapset.cpp ***
#include "proj09_mapset.h"
#include <iostream>
MapSet::MapSet(initializer_list< pair <string, long> > list) : v_(list) {
}
vector< pair <string, long> >::iterator MapSet::find_key(string key) {
return lower_bound(v_.begin(), v_.end(), key);
}
int MapSet::size() {
return v_.size();
}
pair<string, long> MapSet::get(string key) {
vector< pair <string, long> >::iterator it = lower_bound(v_.begin(), v_.end(), key);
pair<string, long> *pr = &*it;
return make_pair(pr->first, pr->second);
}
bool MapSet::update(string key, long value) {
vector< pair <string, long> >::iterator it = lower_bound(v_.begin(), v_.end(), key);
it->second = value;
return true;
}
bool MapSet::remove(string key) {
vector< pair <string, long> >::iterator it = lower_bound(v_.begin(), v_.end(), key);
v_.erase(it);
return true;
}
bool MapSet::add(string key, long value) {
v_.push_back( make_pair(key, value) );
return true;
}
int MapSet::compare(MapSet &ms) {
}
MapSet MapSet::mapset_union(MapSet &new_ms) {
}
MapSet MapSet::mapset_intersection(MapSet &new_ms) {
}
vector< pair <string, long> > MapSet::getData() {
return v_;
}
ostream& operator<<(ostream &out, MapSet &ms) {
vector< pair <string, long> > vect = ms.getData();
for (int i=0; i<ms.size(); i++)
{
out << (i==0 ? "" : ", ") << vect[i].first << ":"
<< vect[i].second ;
}
out << endl;
}
vector< pair <string, long> >::iterator MapSet::lower_bound(vector< pair <string, long> >::iterator first,
vector< pair <string, long> >::iterator last, string val) {
for(vector< pair <string, long> >::iterator it = first; it != last; it++) {
if((it->first.compare(val)) == 0)
return it;
}
return last;
}
*** main.cpp ***
#include <iostream>
#include "proj09_mapset.h"
using namespace std;
int main()
{
MapSet mapset = {};
mapset.add("Ann", 1234);
mapset.add("Bob", 3456);
mapset.add("Charlie", 5678);
cout << endl << "Size of mapset : " << mapset.size() << endl;
cout << endl << mapset;
vector< pair <string, long> >::iterator it = mapset.find_key("Bob");
cout << endl << "Record found : " << it->first << ":" << it->second;
pair <string, long> pr = mapset.get("Ann");
cout << endl << "Record found : " << pr.first << ":" << pr.second;
mapset.update("Charlie", 1111);
mapset.remove("Charlie");
cout << endl << "Size of mapset after remove : " << mapset.size() << endl;
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.