For this assignment you will implement the Map ADT using a binary search tree. Your code should conform to the requirements for std::map. Note that this is remarkably like std::unordered_map from two assignments ago with the exception that the iterator is bidirectional. Also, you won't be providing a hash function. Unlike std::map you will assume that the key type, K, used with your class will have implementations of the comparison operators. Call your class BSTMap and put it in BSTMap.h. The following code defines the class you should write.
I have put in TODO comments in some locations. Note that any place that I have provided the body of a function, you can give an alternate implementation if you desire.
template<typename K,typename V>
class BSTMap {
// TODO: Define your Node
// TODO: specify whatever member data you need.
public:
typedef K key_type;
typedef V mapped_type;
typedef std::pair<K,V> value_type;
class const_iterator;
class iterator {
// TODO: Iterator data. I keep a Node* and a bool that tells me if it is at end.
public:
friend class const_iterator;
iterator(/*TODO*/)/*:...*/ { /*TODO*/ }
// TODO: Other constructors as needed.
bool operator==(const iterator &i) const { /*TODO*/ }
bool operator!=(const iterator &i) const { return !(*this==i); }
std::pair<K,V> &operator*() { /*TODO*/ }
iterator &operator++() {
// TODO
return *this;
}
iterator &operator--() {
// TODO
return *this;
}
iterator operator++(int) {
iterator tmp(*this);
++(*this);
return tmp;
}
iterator operator--(int) {
iterator tmp(*this);
--(*this);
return tmp;
}
};
class const_iterator {
// TODO: iterator data
public:
friend class BSTMap<K,V>; // You might not need this in your code, but it helped me.
const_iterator(/*TODO*/)/*:...*/ { /*TODO*/ }
// TODO: Other constructors as needed.
const_iterator(const iterator &iter)/*:...*/ {}
bool operator==(const const_iterator &i) const { /*TODO*/ }
bool operator!=(const const_iterator &i) const { /*TODO*/ }
const std::pair<K,V> &operator*() { /*TODO*/ }
const_iterator &operator++() {
// TODO
return *this;
}
const_iterator &operator--() {
// TODO
return *this;
}
const_iterator operator++(int) {
const_iterator tmp(*this);
++(*this);
return tmp;
}
const_iterator operator--(int) {
const_iterator tmp(*this);
--(*this);
return tmp;
}
};
BSTMap() {
// TODO
}
~BSTMap() {
// TODO
}
BSTMap(const BSTMap<K,V> &that) {
// TODO
}
BSTMap &operator=(const BSTMap<K,V> &that) {
// TODO
}
bool empty() const { /*TODO*/ }
unsigned size() const { /*TODO*/ }
iterator find(const key_type& k);
const_iterator find(const key_type& k) const;
unsigned int count(const key_type& k) const;
std::pair<iterator,bool> insert(const value_type& val);
template <class InputIterator>
void insert(InputIterator first, InputIterator last) {
for(auto iter = first; iter!=last; ++iter) {
insert(*iter);
}
}
iterator erase(const_iterator position);
unsigned int erase(const key_type& k);
void clear();
mapped_type &operator[](const K &key);
bool operator==(const BSTMap<K,V>& rhs) const;
bool operator!=(const BSTMap<K,V>& rhs) const;
iterator begin() { return iterator(/*TODO*/); }
const_iterator begin() const { return const_iterator(/*TODO*/); }
iterator end() { return iterator(/*TODO*/); }
const_iterator end() const { return const_iterator(/*TODO*/); }
const_iterator cbegin() const { return const_iterator(/*TODO*/); }
const_iterator cend() const { return const_iterator(/*TODO*/); }
};