API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Sep 23rd, 2019
153
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 22.49 KB | None | 0 0
raw download clone embed print report
  1. // trivial_bookshelf.h
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <cassert>
  5. #include <type_traits>
  6. #include <new>
  7. #include <limits>
  8. #include <memory>
  9.  
  10. // target feature: iterator returned by "insert" is guaranteed to remain valid until "erase"d by user
  11. // though the object itself may change address
  12. // insert -- O(1) (O(N) on realloc, but pretty soft)
  13. // erase -- O(1)
  14. // access -- O(1)
  15. // never calls T constructors and destructors, "insert" is done by std::memcpy
  16. // unused memory is always(!) zeroed
  17. template<typename T, typename uint = std::size_t>
  18. class trivial_bookshelf
  19. {
  20. //static_assert(std::is_trivially_copyable<T>::value, "T must be trivially copyable");
  21.  
  22. T *data_ptr;
  23.  
  24. uint *available_idx;
  25. uint ai_size;
  26. uint ai_capacity;
  27.  
  28. static constexpr double realloc_factor = 1.5;
  29. void reallocate(uint const) noexcept;
  30. public:
  31. ~trivial_bookshelf();
  32. trivial_bookshelf() noexcept;
  33. trivial_bookshelf(trivial_bookshelf const &) noexcept;
  34. trivial_bookshelf(trivial_bookshelf &&) noexcept;
  35.  
  36. T &operator[](uint const i) noexcept;
  37. T const &operator[](uint const i) const noexcept;
  38.  
  39. T * data() noexcept;
  40. T const * data() const noexcept;
  41. uint insert(T const &item) noexcept;
  42. void erase(uint const idx) noexcept;
  43. uint size() const noexcept;
  44. uint capacity() const noexcept;
  45. void clear() noexcept;
  46. void reserve(uint const n) noexcept;
  47. };
  48.  
  49. template<typename T, typename uint>
  50. trivial_bookshelf<T, uint>::trivial_bookshelf() noexcept
  51. : data_ptr(nullptr)
  52. , available_idx(nullptr)
  53. , ai_size(0)
  54. , ai_capacity(0)
  55. {}
  56. template<typename T, typename uint>
  57. trivial_bookshelf<T, uint>::trivial_bookshelf(trivial_bookshelf const &b) noexcept
  58. : data_ptr( static_cast<T * >(std::malloc(b.ai_capacity * sizeof(T))))
  59. , available_idx(static_cast<uint *>(std::malloc(b.ai_capacity * sizeof(uint))))
  60. , ai_size(b.ai_size)
  61. , ai_capacity(b.ai_capacity)
  62. {
  63. std::memcpy(data_ptr, b.data_ptr, b.ai_capacity * sizeof(T));
  64. std::memcpy(available_idx, b.available_idx, b.ai_capacity * sizeof(uint));
  65. }
  66. template<typename T, typename uint>
  67. trivial_bookshelf<T, uint>::trivial_bookshelf(trivial_bookshelf &&b) noexcept
  68. : data_ptr(b.data_ptr)
  69. , available_idx(b.available_idx)
  70. , ai_size(b.ai_size)
  71. , ai_capacity(b.ai_capacity)
  72. {
  73. b.data_ptr = nullptr;
  74. b.available_idx = nullptr;
  75. b.ai_size = 0;
  76. b.ai_capacity = 0;
  77. }
  78. template<typename T, typename uint>
  79. void trivial_bookshelf<T, uint>::reallocate(uint const cap) noexcept
  80. {
  81. if(cap <= ai_capacity)
  82. return;
  83. data_ptr = static_cast<T * >(std::realloc(data_ptr, cap * sizeof(T)));
  84. available_idx = static_cast<uint *>(std::realloc(available_idx, cap * sizeof(uint)));
  85. assert(data_ptr != nullptr);
  86. assert(available_idx != nullptr);
  87. std::memset(data_ptr + ai_capacity, 0, (cap - ai_capacity) * sizeof(T));
  88. for(uint i = ai_capacity; i < cap; i++)
  89. available_idx[i] = i;
  90. ai_capacity = cap;
  91. }
  92. template<typename T, typename uint>
  93. trivial_bookshelf<T, uint>::~trivial_bookshelf()
  94. {
  95. std::free(data_ptr);
  96. std::free(available_idx);
  97. data_ptr = nullptr;
  98. available_idx = nullptr;
  99. ai_size = 0;
  100. ai_capacity = 0;
  101. }
  102. template<typename T, typename uint>
  103. T &trivial_bookshelf<T, uint>::operator[](uint const i) noexcept
  104. {
  105. assert(i < ai_capacity);
  106. return data_ptr[i];
  107. }
  108. template<typename T, typename uint>
  109. T const &trivial_bookshelf<T, uint>::operator[](uint const i) const noexcept
  110. {
  111. assert(i < ai_capacity);
  112. return data_ptr[i];
  113. }
  114. template<typename T, typename uint>
  115. uint trivial_bookshelf<T, uint>::insert(T const &item) noexcept
  116. {
  117. if(ai_size == ai_capacity)
  118. reallocate(ai_capacity == 0 ? 3 : ai_capacity * realloc_factor);
  119. std::memcpy(data_ptr + available_idx[ai_size], &item, sizeof(T));
  120. return available_idx[ai_size++];
  121. }
  122. template<typename T, typename uint>
  123. void trivial_bookshelf<T, uint>::erase(uint const idx) noexcept
  124. {
  125. assert(ai_size != 0);
  126. assert(idx < ai_capacity);
  127. std::memset(data_ptr + idx, 0, sizeof(T));
  128. available_idx[--ai_size] = idx;
  129. }
  130. template<typename T, typename uint>
  131. T *trivial_bookshelf<T, uint>::data() noexcept
  132. {
  133. return data_ptr;
  134. }
  135. template<typename T, typename uint>
  136. T const *trivial_bookshelf<T, uint>::data() const noexcept
  137. {
  138. return data_ptr;
  139. }
  140. template<typename T, typename uint>
  141. uint trivial_bookshelf<T, uint>::size() const noexcept
  142. {
  143. return ai_size;
  144. }
  145. template<typename T, typename uint>
  146. uint trivial_bookshelf<T, uint>::capacity() const noexcept
  147. {
  148. return ai_capacity;
  149. }
  150. template<typename T, typename uint>
  151. void trivial_bookshelf<T, uint>::clear() noexcept
  152. {
  153. ai_size = 0;
  154. std::memset(data_ptr, 0, ai_capacity * sizeof(T));
  155.  
  156. // this is optional, but helpful
  157. for(uint i = 0; i < ai_capacity; i++)
  158. available_idx[i] = i;
  159. }
  160. template<typename T, typename uint>
  161. void trivial_bookshelf<T, uint>::reserve(uint const n) noexcept
  162. {
  163. reallocate(n);
  164. }
  165.  
  166. //////////////////////////////////////////////////////////////////
  167. #include <cstdint> // std::uint32_t
  168. #include <functional> // std::hash
  169.  
  170. template
  171. <
  172. typename Key,
  173. typename Value,
  174. typename Hash = std::hash<Key>,
  175. typename KeyEqual = std::equal_to<Key>
  176. >
  177. class trivial_hash_map
  178. {
  179. static_assert(std::is_trivially_copyable<Key >::value, "Key type must be trivially copyable");
  180. static_assert(std::is_trivially_copyable<Value>::value, "Value type must be trivially copyable");
  181.  
  182. using idx_t = std::uint32_t;
  183. static constexpr double load_factor = 0.9;
  184.  
  185. // initialized with zeroes
  186. struct node
  187. {
  188. struct pair
  189. {
  190. Key first;
  191. Value second;
  192. } data;
  193. struct node_state
  194. {
  195. idx_t next;
  196. bool active;
  197. bool has_child;
  198. } state;
  199. };
  200.  
  201. node *nodes_ptr;
  202. idx_t nodes_size;
  203. idx_t nodes_cap;
  204. trivial_bookshelf<node, idx_t> collisions;
  205.  
  206. node *next_node(node * const ptr) noexcept {return &collisions[ptr->state.next];}
  207. node const *next_node(node const * const ptr) const noexcept {return &collisions[ptr->state.next];}
  208. idx_t hash_idx(Key const &key) const noexcept {return Hash{}(key) % nodes_cap;}
  209.  
  210. public:
  211.  
  212. ~trivial_hash_map();
  213. trivial_hash_map() noexcept;
  214. trivial_hash_map(idx_t const capacity) noexcept;
  215. trivial_hash_map(trivial_hash_map<Key, Value, Hash, KeyEqual> &&) noexcept;
  216. trivial_hash_map<Key, Value, Hash, KeyEqual> &operator=(trivial_hash_map<Key, Value, Hash, KeyEqual> &&) noexcept;
  217.  
  218. struct iterator
  219. {
  220. node *ptr;
  221.  
  222. node * const end_ptr;
  223. node * const begin_ptr;
  224. node * const total_end_ptr;
  225.  
  226. iterator & operator++() noexcept;
  227. typename node::pair &operator* () const noexcept;
  228. typename node::pair *operator->() const noexcept;
  229.  
  230. bool operator!=(iterator const &) const noexcept;
  231. bool operator==(iterator const &) const noexcept;
  232. };
  233. struct const_iterator
  234. {
  235. node const *ptr;
  236.  
  237. node const * const end_ptr;
  238. node const * const begin_ptr;
  239. node const * const total_end_ptr;
  240.  
  241. const_iterator & operator++() noexcept;
  242. typename node::pair const &operator* () const noexcept;
  243. typename node::pair const *operator->() const noexcept;
  244.  
  245. bool operator!=(const_iterator const &) const noexcept;
  246. bool operator==(const_iterator const &) const noexcept;
  247. };
  248.  
  249. iterator begin() noexcept;
  250. iterator end() noexcept;
  251. const_iterator cbegin() const noexcept;
  252. const_iterator cend() const noexcept;
  253.  
  254. idx_t size() const noexcept {return nodes_size;}
  255. void rehash(idx_t const new_capacity) noexcept;
  256.  
  257. iterator emplace(Key const &, Value const &) noexcept;
  258. void erase(iterator) noexcept;
  259. void erase(Key const &key) noexcept;
  260. iterator find(Key const &) noexcept;
  261. const_iterator find(Key const &) const noexcept;
  262.  
  263. private:
  264. iterator iter(node *ptr) noexcept;
  265. const_iterator const_iter(node const *ptr) const noexcept;
  266. };
  267.  
  268. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  269. trivial_hash_map<Key, Value, Hash, KeyEqual>::~trivial_hash_map()
  270. {
  271. std::free(nodes_ptr);
  272. }
  273. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  274. trivial_hash_map<Key, Value, Hash, KeyEqual>::trivial_hash_map() noexcept
  275. : nodes_ptr(nullptr)
  276. , nodes_size(0)
  277. , nodes_cap(0)
  278. {}
  279. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  280. trivial_hash_map<Key, Value, Hash, KeyEqual>::trivial_hash_map(idx_t const capacity) noexcept
  281. : nodes_ptr(static_cast<node *>(std::calloc(capacity, sizeof(node))))
  282. , nodes_size(0)
  283. , nodes_cap(capacity)
  284. {}
  285. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  286. trivial_hash_map<Key, Value, Hash, KeyEqual>::trivial_hash_map(trivial_hash_map<Key, Value, Hash, KeyEqual> &&m) noexcept
  287. : nodes_ptr(m.nodes_ptr)
  288. , nodes_size(m.nodes_size)
  289. , nodes_cap(m.nodes_cap)
  290. , collisions(std::move(m.collisions))
  291. {
  292. m.nodes_ptr = nullptr;
  293. m.nodes_size = 0;
  294. m.nodes_cap = 0;
  295. }
  296. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  297. trivial_hash_map<Key, Value, Hash, KeyEqual> &
  298. trivial_hash_map<Key, Value, Hash, KeyEqual>::operator=(trivial_hash_map<Key, Value, Hash, KeyEqual> &&m) noexcept
  299. {
  300. if(this == &m)
  301. return *this;
  302. this->~trivial_hash_map();
  303. new (this) trivial_hash_map(std::move(m));
  304. return *this;
  305. }
  306.  
  307. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  308. typename trivial_hash_map<Key, Value, Hash, KeyEqual>::iterator
  309. trivial_hash_map<Key, Value, Hash, KeyEqual>::iter
  310. (trivial_hash_map<Key, Value, Hash, KeyEqual>::node *ptr) noexcept
  311. {
  312. return iterator
  313. {
  314. ptr,
  315. nodes_ptr + nodes_cap,
  316. collisions.data(),
  317. collisions.data() + collisions.capacity()
  318. };
  319. }
  320. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  321. typename trivial_hash_map<Key, Value, Hash, KeyEqual>::const_iterator
  322. trivial_hash_map<Key, Value, Hash, KeyEqual>::const_iter
  323. (trivial_hash_map<Key, Value, Hash, KeyEqual>::node const *ptr) const noexcept
  324. {
  325. return const_iterator
  326. {
  327. ptr,
  328. nodes_ptr + nodes_cap,
  329. collisions.data(),
  330. collisions.data() + collisions.capacity()
  331. };
  332. }
  333. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  334. typename trivial_hash_map<Key, Value, Hash, KeyEqual>::iterator &
  335. trivial_hash_map<Key, Value, Hash, KeyEqual>::iterator::operator++() noexcept
  336. {
  337. while(1)
  338. {
  339. if(ptr + 1 != end_ptr)
  340. ptr++;
  341. else
  342. ptr = begin_ptr;
  343.  
  344. if(ptr == total_end_ptr || ptr->state.active)
  345. break;
  346. }
  347. return *this;
  348. }
  349. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  350. typename trivial_hash_map<Key, Value, Hash, KeyEqual>::node::pair &
  351. trivial_hash_map<Key, Value, Hash, KeyEqual>::iterator::operator*() const noexcept
  352. {
  353. return ptr->data;
  354. }
  355. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  356. typename trivial_hash_map<Key, Value, Hash, KeyEqual>::node::pair *
  357. trivial_hash_map<Key, Value, Hash, KeyEqual>::iterator::operator->() const noexcept
  358. {
  359. return &ptr->data;
  360. }
  361. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  362. bool trivial_hash_map<Key, Value, Hash, KeyEqual>::iterator::operator!=(iterator const &it) const noexcept
  363. {
  364. return ptr != it.ptr;
  365. }
  366. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  367. bool trivial_hash_map<Key, Value, Hash, KeyEqual>::iterator::operator==(iterator const &it) const noexcept
  368. {
  369. return ptr == it.ptr;
  370. }
  371. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  372. typename trivial_hash_map<Key, Value, Hash, KeyEqual>::iterator
  373. trivial_hash_map<Key, Value, Hash, KeyEqual>::begin() noexcept
  374. {
  375. iterator it = iter(nodes_ptr);
  376. while(1)
  377. {
  378. if(it.ptr == it.total_end_ptr || it.ptr->state.active)
  379. break;
  380. if(it.ptr != it.end_ptr)
  381. it.ptr++;
  382. if(it.ptr == it.end_ptr)
  383. it.ptr = it.begin_ptr;
  384. }
  385. return it;
  386. }
  387. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  388. typename trivial_hash_map<Key, Value, Hash, KeyEqual>::iterator
  389. trivial_hash_map<Key, Value, Hash, KeyEqual>::end() noexcept
  390. {
  391. return iter(collisions.data() + collisions.capacity());
  392. }
  393. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  394. typename trivial_hash_map<Key, Value, Hash, KeyEqual>::const_iterator &
  395. trivial_hash_map<Key, Value, Hash, KeyEqual>::const_iterator::operator++() noexcept
  396. {
  397. while(1)
  398. {
  399. if(ptr + 1 != end_ptr)
  400. ptr++;
  401. else
  402. ptr = begin_ptr;
  403.  
  404. if(ptr == total_end_ptr || ptr->state.active)
  405. break;
  406. }
  407. return *this;
  408. }
  409. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  410. typename trivial_hash_map<Key, Value, Hash, KeyEqual>::node::pair const &
  411. trivial_hash_map<Key, Value, Hash, KeyEqual>::const_iterator::operator*() const noexcept
  412. {
  413. return ptr->data;
  414. }
  415. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  416. typename trivial_hash_map<Key, Value, Hash, KeyEqual>::node::pair const *
  417. trivial_hash_map<Key, Value, Hash, KeyEqual>::const_iterator::operator->() const noexcept
  418. {
  419. return &ptr->data;
  420. }
  421. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  422. bool trivial_hash_map<Key, Value, Hash, KeyEqual>::const_iterator::operator!=(const_iterator const &it) const noexcept
  423. {
  424. return ptr != it.ptr;
  425. }
  426. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  427. bool trivial_hash_map<Key, Value, Hash, KeyEqual>::const_iterator::operator==(const_iterator const &it) const noexcept
  428. {
  429. return ptr == it.ptr;
  430. }
  431. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  432. typename trivial_hash_map<Key, Value, Hash, KeyEqual>::const_iterator
  433. trivial_hash_map<Key, Value, Hash, KeyEqual>::cbegin() const noexcept
  434. {
  435. iterator it = const_iter(nodes_ptr);
  436. while(1)
  437. {
  438. if(it.ptr == it.total_end_ptr || it.ptr->state.active)
  439. break;
  440. if(it.ptr != it.end_ptr)
  441. it.ptr++;
  442. if(it.ptr == it.end_ptr)
  443. it.ptr = it.begin_ptr;
  444. }
  445. return it;
  446. }
  447. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  448. typename trivial_hash_map<Key, Value, Hash, KeyEqual>::const_iterator
  449. trivial_hash_map<Key, Value, Hash, KeyEqual>::cend() const noexcept
  450. {
  451. return const_iter(collisions.data() + collisions.capacity());
  452. }
  453.  
  454. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  455. void trivial_hash_map<Key, Value, Hash, KeyEqual>::rehash(idx_t const new_cap) noexcept
  456. {
  457. trivial_hash_map<Key, Value, Hash, KeyEqual> new_map(new_cap);
  458. for(auto const &pair : *this)
  459. new_map.emplace(pair.first, pair.second);
  460. *this = std::move(new_map);
  461. }
  462. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  463. typename trivial_hash_map<Key, Value, Hash, KeyEqual>::iterator
  464. trivial_hash_map<Key, Value, Hash, KeyEqual>::emplace(Key const &key, Value const &value) noexcept
  465. {
  466. if(nodes_size >= nodes_cap * load_factor)
  467. rehash(nodes_cap * 2 + 7);
  468.  
  469. KeyEqual const equal;
  470. idx_t const i = hash_idx(key);
  471. node *node_ptr = nodes_ptr + i;
  472. if(!node_ptr->state.active)
  473. {
  474. node_ptr->data = typename node::pair{key, value};
  475. node_ptr->state = typename node::node_state{0, true, false};
  476. nodes_size++;
  477. return iter(node_ptr);
  478. }
  479. if(equal(node_ptr->data.first, key))
  480. return iter(node_ptr);
  481. if(!node_ptr->state.has_child)
  482. {
  483. nodes_size++;
  484. node_ptr->state = {collisions.insert(node{key, value, 0, true, false}), true, true};
  485. return iter(next_node(node_ptr));
  486. }
  487.  
  488. idx_t child_idx = node_ptr->state.next;
  489. while(1)
  490. {
  491. node &curr_node = collisions[child_idx];
  492. assert(hash_idx(curr_node.data.first) == i);
  493. if(equal(curr_node.data.first, key))
  494. return iter(&curr_node);
  495. if(!curr_node.state.has_child)
  496. {
  497. nodes_size++;
  498. // insert may invalidate pointers
  499. idx_t const new_idx = collisions.insert(node{key, value, 0, true, false});
  500. collisions[child_idx].state = {new_idx, true, true};
  501. return iter(&collisions[new_idx]);
  502. }
  503. else
  504. child_idx = curr_node.state.next;
  505. }
  506. }
  507. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  508. typename trivial_hash_map<Key, Value, Hash, KeyEqual>::iterator
  509. trivial_hash_map<Key, Value, Hash, KeyEqual>::find(Key const &key) noexcept
  510. {
  511. KeyEqual const equal;
  512. idx_t const i = hash_idx(key);
  513. node *node_ptr = nodes_ptr + i;
  514. if(!node_ptr->state.active)
  515. return end();
  516. while(1)
  517. {
  518. if(equal(node_ptr->data.first, key))
  519. return iter(node_ptr);
  520. if(node_ptr->state.has_child)
  521. node_ptr = next_node(node_ptr);
  522. else
  523. return end();
  524. }
  525. }
  526. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  527. typename trivial_hash_map<Key, Value, Hash, KeyEqual>::const_iterator
  528. trivial_hash_map<Key, Value, Hash, KeyEqual>::find(Key const &key) const noexcept
  529. {
  530. KeyEqual const equal;
  531. idx_t const i = hash_idx(key);
  532. node const *node_ptr = nodes_ptr + i;
  533. if(!node_ptr->state.active)
  534. return cend();
  535. while(1)
  536. {
  537. if(equal(node_ptr->data.first, key))
  538. return const_iter(node_ptr);
  539. if(node_ptr->state.has_child)
  540. node_ptr = next_node(node_ptr);
  541. else
  542. return cend();
  543. }
  544. }
  545. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  546. void trivial_hash_map<Key, Value, Hash, KeyEqual>::erase(Key const &key) noexcept
  547. {
  548. KeyEqual const equal;
  549. idx_t const i = hash_idx(key);
  550. node *prev_node = nullptr;
  551. node *node_ptr = nodes_ptr + i;
  552. if(!node_ptr->state.active)
  553. return;
  554. while(!equal(node_ptr->data.first, key))
  555. {
  556. if(!node_ptr->state.has_child)
  557. return;
  558. prev_node = node_ptr;
  559. node_ptr = next_node(node_ptr);
  560. }
  561. // from here node_ptr->data.first == key
  562. nodes_size--;
  563. if(!node_ptr->state.has_child)
  564. {
  565. if(prev_node != nullptr)
  566. {
  567. collisions.erase(prev_node->state.next);
  568. prev_node->state = typename node::node_state{0, true, false};
  569. }
  570. else
  571. std::memset(node_ptr, 0, sizeof(typename node::pair) + sizeof(typename node::node_state));
  572. }
  573. else
  574. {
  575. idx_t const child_idx = node_ptr->state.next;
  576. node const &child = collisions[child_idx];
  577. node_ptr->data = child.data;
  578. node_ptr->state = child.state;
  579. collisions.erase(child_idx);
  580. }
  581. }
  582. template<typename Key, typename Value, typename Hash, typename KeyEqual>
  583. void trivial_hash_map<Key, Value, Hash, KeyEqual>::erase(iterator it) noexcept
  584. {
  585. if(it.ptr->state.has_child)
  586. {
  587. idx_t const child_idx = it.ptr->state.next;
  588. node const &child = collisions[child_idx];
  589. it.ptr->data = child.data;
  590. it.ptr->state = child.state;
  591. collisions.erase(child_idx);
  592. nodes_size--;
  593. }
  594. else
  595. erase(it.ptr->data.first);
  596. }
  597.  
  598. #include <iostream>
  599. #include <chrono>
  600. #include <unordered_map>
  601.  
  602. void printExecutionTime(std::string const & name, std::function<void ()> const & f) {
  603. using namespace std::chrono;
  604.  
  605. auto start = system_clock::now();
  606. f();
  607. auto end = system_clock::now();
  608. auto ms = duration_cast<std::chrono::milliseconds>(end - start);
  609.  
  610. std::cout << name << " took " << ms.count() << " ms" << '\n';
  611. }
  612.  
  613. size_t const N = 8 * 1024 * 1024;
  614.  
  615. class Buffer {
  616. size_t capacity = 1024 * N;
  617. void * data = malloc(capacity);
  618. size_t offset = 0;
  619.  
  620. public:
  621. void * allocate(std::size_t size) {
  622. void * result = data + offset;
  623. offset += size;
  624. return result;
  625. }
  626.  
  627. ~Buffer() {
  628. free(data);
  629. }
  630.  
  631. };
  632.  
  633. template <class T>
  634. struct TvoyaMamkaAllocator {
  635. typedef T value_type;
  636. std::shared_ptr<Buffer> buffer{new Buffer};
  637.  
  638. TvoyaMamkaAllocator() = default;
  639.  
  640. template <class U> constexpr TvoyaMamkaAllocator(const TvoyaMamkaAllocator<U>&o) noexcept
  641. : buffer(o.buffer) {}
  642.  
  643. [[nodiscard]] T* allocate(std::size_t n) {
  644. return static_cast<T*>(buffer->allocate(sizeof(T) * n));
  645. }
  646.  
  647. void deallocate(T* p, std::size_t) noexcept { }
  648. };
  649. using CustomAllocator = TvoyaMamkaAllocator<std::pair<const int, int>>;
  650.  
  651. int main()
  652. {
  653. auto const testEmplace = [](auto& map){
  654. map.rehash(N);
  655. for(int i = 0; i < N; i++)
  656. map.emplace(i, 0);
  657. };
  658.  
  659. auto const testErase = [](auto& map){
  660. for(int i = 0; i < N; i++)
  661. map.erase(i);
  662. };
  663.  
  664. trivial_hash_map<int, int> bicycle;
  665. std::unordered_map<int, int> unordered_map;
  666. std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, CustomAllocator> custom_allocator_map;
  667. printExecutionTime("emplace bicycle", [&](){ testEmplace(bicycle); });
  668. printExecutionTime("emplace unordered_map", [&](){ testEmplace(unordered_map); });
  669. printExecutionTime("emplace custom_allocator_map", [&](){ testEmplace(custom_allocator_map); });
  670.  
  671. printExecutionTime("erase bicycle", [&](){ testErase(bicycle); });
  672. printExecutionTime("erase unordered_map", [&](){ testErase(unordered_map); });
  673. printExecutionTime("erase custom_allocator_map", [&](){ testErase(custom_allocator_map); });
  674. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!