fork(8) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <new>
  4. #include <assert.h>
  5. typedef unsigned int uint;
  6.  
  7.  
  8. //ассоциативный массив(используется двоичный поиск) 
  9. template<typename KEY, typename T>
  10. class marray {
  11.  
  12. 	struct info {
  13. 		KEY key;
  14. 		T   data;
  15. 	};
  16.  
  17. private:
  18. 	info* arr;
  19. 	uint  cnt;
  20. 	uint  mem;
  21. public:
  22. 	marray(void):arr(NULL),
  23. 	             cnt(0),
  24. 	             mem(16){}
  25. 	~marray(){
  26. 		this->clear();
  27. 	}
  28.  
  29. 	marray(const marray&);
  30. 	marray& operator = (const marray&);
  31. public:
  32.  
  33. 	//добавление ключ=значение
  34. 	T* add(const KEY& key, const T& data){
  35. 		uint i = _bin_find(key);
  36. 		if(! _heap_alloc_())
  37. 			return NULL;
  38.  
  39. 		//дубликат
  40. 		if(key == arr[i].key)
  41. 			return NULL;
  42.  
  43. 		if(i < cnt){
  44. 			info* pb = arr + cnt;
  45. 			info* pa = arr + i;
  46. 			for(;pb > pa; --pb)
  47. 				*pb = *(pb - 1); 
  48. 		}
  49. 		arr[i].key  = key;
  50. 		arr[i].data = data;
  51.  
  52. 		++cnt;
  53. 		return &arr[i].data;
  54. 	}
  55.  
  56. 	//удаление данных по-ключу
  57. 	void remove(const KEY& key){
  58. 		uint i = _bfind_info(key);
  59. 		if(i != (uint)-1){
  60. 			--cnt;
  61. 			info* pa = arr + i;
  62. 			info* pb = arr + cnt;
  63. 			for(;pa < pb; ++pa)
  64. 				*pa = *(pa + 1);
  65.  
  66. 			if(! cnt)
  67. 				this->clear();
  68. 		}
  69. 	}
  70.  
  71. 	//поиск данных по-ключу O(log(n))
  72. 	T* find(const KEY& key){
  73. 		uint i = _bfind_info(key);
  74. 		return (i != (uint)-1) ? &arr[i].data : NULL;
  75. 	}
  76. 	const T* find(const KEY& key) const {
  77. 		const uint i = _bfind_info(key);
  78. 		return (i != (uint)-1) ? &arr[i].data : NULL;
  79. 	}
  80.  
  81. 	bool empty(void) const {
  82. 		return (arr == NULL);
  83. 	}
  84.  
  85. 	//кол-во элементов
  86. 	uint size(void) const {
  87. 		return cnt;
  88. 	}
  89.  
  90. 	//удаление всего массива
  91. 	void clear(void){
  92. 		if(arr != NULL)
  93. 			delete[] arr;
  94. 		arr = NULL;
  95. 		cnt = 0;
  96. 		mem = 16;
  97. 	}
  98.  
  99. 	//получение ключа по-индексу только для чтения
  100. 	const KEY& keyAt(uint i) const {
  101. 		return arr[i].key;
  102. 	}
  103.  
  104. 	//доступ к значению по-индексу
  105. 	T& valueAt(uint i) const {
  106. 		return arr[i].data;
  107. 	}
  108.  
  109. 	//получение доступа как к обычному массиву
  110. 	const T& operator [] (const KEY& key) const {
  111. 		const uint i = _bfind_info(key);
  112.  
  113. 		assert(i != (uint)-1);
  114. 		return arr[i].data;
  115. 	}
  116.  
  117. 	T& operator [] (const KEY& key){
  118. 		uint i = _bin_find(key);
  119. 		if((i < cnt) && (key == arr[i].key))
  120. 			return arr[i].data;
  121.  
  122. 		if(_heap_alloc_()){
  123. 			if(i < cnt){
  124. 				info* pb = arr + cnt;
  125. 				info* pa = arr + i;
  126. 				for(;pb > pa; --pb)
  127. 					*pb = *(pb - 1); 
  128. 			}
  129. 			arr[i].key  = key;
  130. 			arr[i].data = T();
  131. 			++cnt;
  132. 		} else
  133. 			assert(false);
  134.  
  135. 		return arr[i].data;
  136. 	}
  137.  
  138. private:
  139.  
  140. 	//выделение динамической памяти для массива
  141. 	bool _heap_alloc_(void){
  142. 		if(arr == NULL){
  143. 			arr = new (std::nothrow) info[mem];
  144. 			if(arr == NULL)
  145. 				return false;
  146. 		} else if((cnt + 1) >= mem){
  147. 			uint  tmem = cnt + mem / 2;
  148. 			info* tmp  = new (std::nothrow) info[tmem];
  149. 			if(tmp == NULL)
  150. 				return false;
  151.  
  152. 			const info* p = arr;
  153. 			const info* e = arr + cnt;
  154. 			info* d = tmp;
  155. 			while(p != e)
  156. 				*d++ = *p++;
  157.  
  158. 			delete[] arr;
  159. 			arr = tmp;
  160. 			mem = tmem;
  161. 		}
  162. 		return true;
  163. 	}
  164.  
  165. 	//двоичный поиск вхождение ключа для вставки
  166. 	uint _bin_find(const KEY& key){
  167. 		if(! cnt || (key < arr[0].key))
  168. 			return 0;
  169. 		else if(arr[cnt - 1].key < key)
  170. 			return cnt;
  171.  
  172. 		uint m = 0, f = 0, l = cnt;
  173.  
  174. 		while(f < l){
  175. 			m = (f + l) >> 1;
  176. 			if(key < arr[m].key)
  177. 				l = m;
  178. 			else {
  179. 				if(key == arr[m].key)
  180. 					return m;
  181. 				f = m + 1;
  182. 			}
  183. 		}
  184. 		return f;
  185. 	}
  186.  
  187. 	//двоичный поиск вхождения ключа
  188. 	uint _bfind_info(const KEY& key) const {
  189. 		if(! cnt || (key < arr[0].key))
  190. 			return (uint)-1;
  191. 		else if(arr[cnt - 1].key < key)
  192. 			return (uint)-1;
  193.  
  194. 		uint m = 0, f = 0, l = cnt;
  195.  
  196. 		while(f < l){
  197. 			m = (f + l) >> 1;
  198. 			if(key < arr[m].key)
  199. 				l = m;
  200. 			else {
  201. 				if(key == arr[m].key)
  202. 					return m;
  203. 				f = m + 1;
  204. 			}
  205. 		}
  206. 		return (uint)-1;
  207. 	}
  208. };
  209.  
  210.  
  211.  
  212. int main(void){
  213. 	marray<std::string, int> arr;
  214.  
  215. 	arr["собака"]   = 100;
  216. 	arr["волк"]     = 200;
  217. 	arr["сова"]     = 300;
  218. 	arr["дельфин"]  = 890;
  219.  
  220. 	//найти
  221. 	int* p = arr.find("сова");
  222. 	if(p != NULL)
  223. 		*p = 1000; // изменить
  224.  
  225. 	//удалим волка
  226. 	arr.remove("волк");
  227. 	if(arr.find("волк") == NULL)
  228. 		std::cout << "волк удалён" << std::endl;
  229.  
  230. 	//добавим мышь
  231. 	arr.add("мышь", 90000);
  232.  
  233. 	//вывести все элементы ключ=значение
  234. 	for(uint i = 0; i < arr.size(); ++i){
  235. 		std::cout << arr.keyAt(i)   << " = "
  236. 			      << arr.valueAt(i) << std::endl;
  237. 	}
  238. 	std::cout << std::endl;
  239. 	arr.clear();
  240.  
  241. 	//...
  242.  
  243. 	//задача: подсчитать кол-во одинаковых символов
  244. 	marray<char, size_t> carr;
  245.  
  246. 	char  s[] = "AAABBBAACCCCCFCCCCC";
  247. 	char* pc  = &s[0];
  248. 	while(*pc)
  249. 		carr[*pc++]++;
  250.  
  251. 	//вывести результат
  252. 	for(uint c = 0; c < carr.size(); ++c){
  253. 		std::cout << carr.keyAt(c)   << " = "
  254. 			      << carr.valueAt(c) << std::endl;
  255. 	}
  256. 	std::cout << std::endl;
  257. 	carr.clear();
  258.  
  259. 	//...
  260.  
  261. 	marray<std::string, std::string> sarr;
  262. 	sarr["Вася"] = "Геодезист";
  263. 	sarr["Петя"] = "Бетонщик";
  264. 	sarr["Юрий"] = "Кровельщик";
  265.  
  266. 	sarr.add("Гриша", "Стропальщик");
  267.  
  268. 	std::cout << sarr["Вася"]  << std::endl
  269. 		      << sarr["Петя"]  << std::endl
  270. 			  << sarr["Юрий"]  << std::endl
  271. 			  << sarr["Гриша"] << std::endl;
  272. 	sarr.clear();
  273. 	return 0;
  274. }
  275.  
  276.  
Success #stdin #stdout 0s 3284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
волк удалён
дельфин = 890
мышь = 90000
собака = 100
сова = 1000

A = 5
B = 3
C = 10
F = 1

Геодезист
Бетонщик
Кровельщик
Стропальщик
https://ideone.com/a9ouMI
language:
C++ (gcc 8.3)
created:
8 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!