C++ Help Please !!

I have finished first part of my project but for the second part I need to implement a chained hash table in the following code.
no need to code erase function...
So, please help me....



#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <list>
#include <stdexcept>
#include <functional>

using std::cerr;
using std::cout;
using std::string;
using std::vector;
using std::endl;
using std:stringstream;

template <class I, class LessThan = std::less<I> >
class Valli {
class Cell; //forward declaration of nested class is OK only within class!
public:
class iterator;
class const_iterator;
private:
friend class Cell;
friend class iterator;
friend class const_iterator;

LessThan lessThan;
Cell* dummyHead; //used only to make ->prev->next legal for 1st real node
Cell* dummyEnd; //used similarly to speed insert for new max item
vector<Cell*>* mileposts;
size_t ratio;
size_t numItems;
size_t refreshTarget;
//vector<size_t>* segmentSizes;

class Cell { //doubly linked
friend class iterator;
friend class const_iterator;
friend class Valli; //ANSI made this necessary in 1998
I data;
Cell* next;
Cell* prev;
Cell() : data(I()), next(NULL), prev(NULL) { }
Cell(const I& item, Cell* gnext, Cell* gprev)
: data(item), next(gnext), prev(gprev) { }
virtual ~Cell() { }
};

public:
class iterator {
friend class Valli;
friend class Cell; //needed?
friend class const_iterator; //needed! (tho not on timberlake...)
const Valli<I, LessThan>* holder;
Cell* curr;
iterator(const Valli<I, LessThan>* const gholder, Cell* gcurr)
: holder(gholder), curr(gcurr) { }

public:
I& operator*() const {
if (curr != holder->dummyEnd) {
return curr->data;
} else {
cout << holder->str();
throw std::invalid_argument("Attempt to de-reference the end");
}
}
iterator& operator++() {
curr = curr->next;
return *this;
}
iterator operator++(int x) {
iterator old = *this;
curr = curr->next;
return old;
}
bool operator==(const iterator& other) const {
return curr == other.curr;
}
bool operator!=(const iterator& other) const {
return curr != other.curr;
}
};

class const_iterator {
friend class Valli;
friend class Cell; //needed?
//Note asymmetry: in STL "iterator" has no operator==(const_iterator&)
//Hence const_iterators can only be compared on LHS with iterators, i.e.
//citr == itr not itr == citr, and const_iterator doesn't friend iterator
const Valli<I, LessThan>* holder;
Cell* curr;
const_iterator(const Valli<I, LessThan>* const gholder, Cell* gcurr)
: holder(gholder), curr(gcurr) { }
public:
const I& operator*() const {
if (curr != holder->dummyEnd) {
return curr->data;
} else {
throw std::invalid_argument("Attempt to de-reference the end");
}
}
const_iterator& operator++() {
curr = curr->next;
return *this;
}
const_iterator operator++(int x) {
const_iterator old = *this;
curr = curr->next;
return old;
}
bool operator==(const const_iterator& other) const {
return curr == other.curr;
}
bool operator!=(const const_iterator& other) const {
return curr != other.curr;
}

/** Next members needed too---following convention that in any
comparison with a const_iterator, the const_iterator goes on left.
*/
bool operator==(const iterator& other) const {
return curr == other.curr;
}
bool operator!=(const iterator& other) const {
return curr != other.curr;
}

};



public:

Valli()
: lessThan(LessThan())
, dummyHead(new Cell())
, dummyEnd(new Cell())
//, tail(head)
, mileposts(new vector<Cell*>())
, ratio(20)
, numItems(0)
, refreshTarget(40)
//, segmentSizes(new vector<size_t>())
{
dummyHead->next = dummyEnd;
dummyEnd->prev = dummyHead;
mileposts->push_back(dummyHead->next); //which == dummyEnd
mileposts->push_back(dummyEnd);
//segmentSizes->push_back(0); //just 1 segment
}

Valli(size_t gratio)
: lessThan(LessThan())
, dummyHead(new Cell())
, dummyEnd(new Cell())
//, tail(head)
, mileposts(new vector<Cell*>())
, ratio(gratio)
, numItems(0)
, refreshTarget(2*gratio)
//, segmentSizes(new vector<size_t>())
{
dummyHead->next = dummyEnd;
dummyEnd->prev = dummyHead;
mileposts->push_back(dummyHead->next); //which == dummyEnd
mileposts->push_back(dummyEnd);
//segmentSizes->push_back(0); //just 1 segment
}

virtual ~Valli() { //mainly cannibalized from SLIst!
while (dummyHead != NULL) {
Cell* delendum = dummyHead;
dummyHead = delendum->next;
delete(delendum);
}
//delete(head);
delete(mileposts); // since we had pointer-to-vector
}
/** Iterator to first list data that doesn't compare < item
Will be first data if item is new min, end() if item is new max.
On empty container, j = 1, i = 0, so curr == limit and end() is ret.
*/
iterator lower_bound(const I& item) const {
size_t j = binsearch(item); //always j > 0
int i = j-1;
while (i > 0 && !lessThan(mileposts->at(i)->data , item)) {
i--;
}
Cell* limit = mileposts->at(j);
Cell* curr = mileposts->at(i);
while (curr != limit && lessThan(curr->data , item)) {
curr = curr->next;
}
return iterator(this, curr);
}

/** Pointer to first item that compares >, or end-NULL if nonesuch.
*/
iterator upper_bound(const I& item) const {
Cell* curr = mileposts->at(binsearch(item)); //always i > 0
while (curr != dummyHead && lessThan(item , curr->data)) {
curr = curr->prev;
}
return iterator(this, curr->next);
}


/** Add item, maintaining CLASS INV: linked list is sorted by lessThan.
Adds at first permissible location, does not check for duplicates.
Refreshes if segment size has grown to next multiple of r.
*/
iterator insert(const I& item) {
iterator itr = lower_bound(item); //calls binary search
itr = insert(itr, item);
numItems++;
if (numItems >= refreshTarget) {
refresh();
refreshTarget = 2*numItems;
} else if (itr.curr == dummyHead->next) {
mileposts->at(0) = itr.curr;
}
return itr;
}

/** Iterator to first stored item that compares <> to item,
end() if no such item. NOTE that end() is a const_iterator since
this method is "const", so end() must be on the LHS of the comparison!
*/
iterator find(const I& item) const {
iterator itr = lower_bound(item);
if (end() == itr || item < *itr) {
//return end();
return iterator(this, mileposts->back());
} else {
return itr;
}
}


void erase(iterator itr) {
Cell* delendum = itr.curr;
size_t i = binsearch(*itr); // throws exception if itr == end
size_t j = i-1;
bool refreshFlag = false;
while (j >= 0 && !lessThan(mileposts->at(j)->data , *itr)) {
if (mileposts->at(j) == delendum) {
refreshFlag = (mileposts->at(j+1) == delendum->next);
mileposts->at(j) = delendum->next;
break; //out of while loop
}
}
delendum->prev->next = delendum->next;
delendum->next->prev = delendum->prev; //cell now unlinked
delete(delendum);
numItems--;
if (refreshFlag) {
refresh();
}
}

iterator begin() {
return iterator(this, dummyHead->next);
}
iterator end() {
return iterator(this, dummyEnd);
}

const_iterator begin() const {
return const_iterator(this, dummyHead->next);
}
const_iterator end() const {
return const_iterator(this, dummyEnd);
}

size_t size() const {
return numItems;
}
bool empty() const {
return numItems == 0;
}

void refresh(size_t newRatio) {
mileposts->clear();
Cell* curr = dummyHead->next;
size_t count = 0;
while (curr != dummyEnd) {
if (count % newRatio == 0) {
mileposts->push_back(curr); //copy
}
curr = curr->next;
count++;
}
mileposts->push_back(curr); // pushes back dummyEnd
}
void refresh() { refresh(this->ratio); }
string str() const {
string str = " start \n";

str = str + " | \n"
+ " | \n"
+ " V \n";
//iterator itr = begin();
Cell* curr = mileposts->at(0);
size_t i = 0;
string arr, num;
while (curr != dummyEnd) {
// str = str + "[o | o]--->" + current->item->toString() + "\n"
// causes Seg Fault if item is a null pointer.
if (i < mileposts->size() && curr == mileposts->at(i)) {
arr = "-->";
ostringstream oss;
oss << segmentSize(i);
num = oss.str();
i++;
} else {
arr = " ";
num = "";
}
str = str + arr + "[o | o]--->" + (curr->data).str() + "\n"
+ " | " + num + "\n"
+ " | \n"
+ " V \n";
curr = curr->next;
}
arr = (curr == dummyEnd) ? "-->" : " ";
str += arr + "end(), here NULL\n";
return str;
}

/*-------------------------------------------------------------------------
Private Utility Methods.
*///-----------------------------------------------------------------------

private:
/** Insert before cell "pos" is on.
*/
iterator insert(const iterator& pos, const I& item) {
pos.curr->prev = pos.curr->prev->next = new Cell(item,
pos.curr, pos.curr->prev);
return iterator(this, pos.curr->prev);
}

/** Return min i such that mileposts->at(i)'s item is > argument item
This includes end()---implicitly end()'s item is a super-max. Hence
INV: left's item <= item < right's item.
*/
size_t binsearch(const I& item) const {
size_t left = 0;
size_t right = mileposts->size() - 1; //initially dummyEnd
while (right - left > 1) {
size_t mid = (left + right) / 2; // INV: left < mid < right
if (item < mileposts->at(mid)->data) {
right = mid;
} else {
left = mid;
}
}
return right;
}


/** Distance from mileposts->at(i) to mileposts->at(i+1), or to end().
*/
size_t segmentSize(size_t i) const {
if (i >= mileposts->size() || mileposts->at(i) == dummyEnd) {
return 0;
} // else
Cell* head = mileposts->at(i);
Cell* stop = mileposts->at(i+1); //might be end()
size_t count = 0;
while (head != stop) {
count++;
head = head->next;
}
return count;
}


}; //end of class Valli.

 

Sorry I'm not clear. What's the help you need?

 

I need to implement a hash table into it using a hash function....and 2 template parameters/.....

 

So... what did you try that didn't work?

 

explain whats the exact error you are getting or issues..no one can dig that huge code for free mate

 

true says