fork download
copy 
  1. #include <iostream>
  2.  
  3. class HashMap {
  4.     int c;
  5.     int s;
  6.     struct Node {
  7.         char x;
  8.         Node* next;
  9.     };
  10.     Node* a;
  11. public:
  12.     HashMap() {
  13.         c = 10;
  14.         s = 0;
  15.         a = new Node[c];
  16.         for(int i = 0; i != c; ++i) {
  17.             a[i].x = 0;
  18.             a[i].next = NULL;
  19.         }
  20.     }
  21.     HashMap(int n) {
  22.         c = n;
  23.         s = 0;
  24.         a = new Node[c];
  25.         for(int i = 0; i != c; ++i) {
  26.             a[i].x = 0;
  27.             a[i].next = NULL;
  28.         }
  29.     }
  30.     ~HashMap() {
  31.         clear();
  32.         Node* tmp_n;
  33.         for(int i = 0; i != c; ++i) {
  34.             tmp_n = a[i].next;
  35.             delete tmp_n;
  36.         }
  37.         c = 0;
  38.         Node* tmp_a = a;
  39.         delete[] tmp_a;
  40.         a = NULL;
  41.     }
  42.     HashMap(const HashMap& src) {
  43.         c = src.c;
  44.         s = src.s;
  45.         a = new Node[c];
  46.         for(int i = 0; i != c; ++i) {
  47.             a[i].x = src.a[i].x;
  48.             a[i].next = src.a[i].next;
  49.         }
  50.     }
  51.     HashMap& operator=(const HashMap& src) {
  52.         if(&src==this) {
  53.             return *this;
  54.         }
  55.         else {
  56.             c = src.c;
  57.             s = src.s;
  58.             a = new Node[c];
  59.             for(int i = 0; i != c; ++i) {
  60.                 a[i].x = src.a[i].x;
  61.                 a[i].next = src.a[i].next;
  62.             }
  63.             return *this;
  64.         }
  65.     }
  66.     int hash(int key) { return (key % c); }
  67.     bool insert(int key, char value);
  68.     bool remove(int key, char& value);
  69.     bool search(int key, char& value);
  70.     void clear();
  71.     bool is_empty() { return (s==0) ? true : false; }
  72.     std::size_t capacity() { return c; }
  73.     std::size_t size() { return s; }
  74.     double load();
  75.     std::ostream& print(std::ostream& out);
  76. };
  77.  
  78. bool HashMap::insert(int key, char value) {
  79.     if(s==c)
  80.         return false;
  81.     int k = hash(key);
  82.     if(a[k].x == 0) {
  83.         ++s;
  84.     }
  85.     a[k].x = value;
  86. }
  87.  
  88. bool HashMap::remove(int key, char& value) {
  89.     int k = hash(key);
  90.     if(is_empty() || (a[k].x == 0)) {
  91.         return false;
  92.     }
  93.     value = a[k].x;
  94.     --s;
  95.     a[k].x = 0;
  96.     return true;
  97. }
  98.  
  99. bool HashMap::search(int key, char& value) {
  100.     int k = hash(key);
  101.     if(a[k].x != 0) {
  102.     	value = a[k].x;
  103.     	return true;
  104.     }
  105.     return false;
  106. }
  107.  
  108. void HashMap::clear() {
  109. 	for(int i = 0; i != c; ++i) {
  110. 		a[i].x = 0;
  111. 	}
  112. 	s = 0;
  113. }
  114.  
  115. double HashMap::load() {
  116. 	double l = 0;
  117. 	int r = 0;
  118. 	for(int i = 0; i != c; ++i) {
  119. 		if(a[i].next != NULL) {
  120. 			++r;
  121. 		}
  122. 	}
  123. 	l = (r + s)/c;
  124. 	return l;
  125. }
  126.  
  127. std::ostream& HashMap::print(std::ostream& out) {
  128. 	if(is_empty()) {
  129. 		out << "<empty list>";
  130. 	}
  131. 	else {
  132. 		out << "[ ";
  133. 		for(int i = 0; i != (c-1); ++i) {
  134. 			if(a[i].x == 0) {
  135. 				out << "--";
  136. 			}
  137. 			if(a[i].x != 0) {
  138. 				out << a[i].x;
  139. 			}
  140. 			out << " : ";
  141. 		}
  142. 		out << " ]";
  143. 	}
  144. 	out << std::endl;
  145. 	return out;
  146. }
  147.  
  148. int main() {
  149. 	HashMap h = HashMap();
  150. 	std::cout << std::boolalpha << h.is_empty() << std::endl;
  151. 	h.insert(3,'x');
  152. 	h.print(std::cout);
  153. 	std::cout << std::boolalpha << h.is_empty() << std::endl;
  154. 	std::cout << h.size() << std::endl;
  155. 	return 0;
  156. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
true
[ -- : -- : -- : x : -- : -- : -- : -- : -- :  ]
false
1
https://ideone.com/dct54r
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!