API tools faq
paste
Advertisement
sve_vash

Untitled

sve_vash
Nov 28th, 2019
127
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.56 KB | None | 0 0
raw download clone embed print report
  1. #include <vector>
  2. #include <string>
  3. #include <list>
  4. #include <forward_list>
  5. #include <set>
  6. #include <unordered_set>
  7. #include <map>
  8. #include <unordered_map>
  9. #include <stack>
  10. #include <queue>
  11. #include <deque>
  12.  
  13. #include <iostream>
  14. #include <cmath>
  15. #include <algorithm>
  16. #include <numeric>
  17. #include <iostream>
  18. #include <fstream>
  19. #include <sstream>
  20. #include <iomanip>
  21. #include <tuple>
  22. #include <type_traits>
  23. #include <functional>
  24. #include <utility>
  25. #include <atomic>
  26. #include <thread>
  27. #include <future>
  28. #include <chrono>
  29. #include <iterator>
  30. #include <memory>
  31. #define CATCH_CONFIG_MAIN
  32. #include "catch.hpp"
  33. #include "hash_map.hpp"
  34.  
  35. namespace fefu {
  36.  
  37. TEST_CASE("constructors") {
  38. hash_map<std::string, int> a(7);
  39. REQUIRE(a.bucket_count() == 7);
  40. REQUIRE(a.size() == 0);
  41. REQUIRE(a.empty());
  42.  
  43. hash_map<std::string, int> b(8);
  44.  
  45. std::vector<std::pair<std::string, int>> vec(5);
  46. vec[0] = {"abc1", 1};
  47. vec[1] = {"abc2", 2};
  48. vec[2] = {"abc3", 3};
  49. vec[3] = {"abc4", 4};
  50. vec[4] = {"abc5", 5};
  51. b.insert(vec.begin(), vec.end());
  52.  
  53. hash_map<std::string, int> c(b);
  54.  
  55. REQUIRE(c == b);
  56. a = b;
  57. REQUIRE(a == b);
  58.  
  59. REQUIRE(a.bucket("abc1") == b.bucket("abc1"));
  60. REQUIRE(a.bucket("abc2") == b.bucket("abc2"));
  61. REQUIRE(a.bucket("abc3") == b.bucket("abc3"));
  62. REQUIRE(a.bucket("abc4") == b.bucket("abc4"));
  63. REQUIRE(a.bucket("abc5") == b.bucket("abc5"));
  64.  
  65. hash_map<std::string, int> d(std::move(b));
  66. REQUIRE(d.contains("abc1"));
  67. REQUIRE(d.contains("abc2"));
  68. REQUIRE(d.contains("abc3"));
  69. REQUIRE(d.contains("abc4"));
  70. REQUIRE(d.contains("abc5"));
  71. }
  72.  
  73. TEST_CASE("try emplace") {
  74. hash_map<std::string, int> a(7);
  75. REQUIRE(a.bucket_count() == 7);
  76. REQUIRE(a.size() == 0);
  77. REQUIRE(a.empty());
  78. a.try_emplace("ttt", 555);
  79. REQUIRE(a.bucket_count() == 7);
  80. REQUIRE(a.size() == 1);
  81. REQUIRE(a.at("ttt") == 555);
  82. REQUIRE(a.contains("ttt"));
  83. }
  84.  
  85. TEST_CASE("operator ==") {
  86. hash_map<std::string, int> a(5);
  87. hash_map<std::string, int> b(5); //equal
  88. hash_map<std::string, int> c(5); //same size, different elements
  89. hash_map<std::string, int> d(6); //same elements, different size
  90. hash_map<std::string, int> e(5); //same size, different keys
  91.  
  92. a.try_emplace("abc1", 5);
  93. a.try_emplace("abc2", 5);
  94.  
  95. a.insert(std::pair<std::string, int>("abc3", 5));
  96. a.insert(std::pair<std::string, int>("abc4", 5));
  97.  
  98. b.try_emplace("abc1", 5);
  99. b.try_emplace("abc2", 5);
  100.  
  101. b.insert(std::pair<std::string, int>("abc3", 5));
  102. b.insert(std::pair<std::string, int>("abc4", 5));
  103.  
  104. c.try_emplace("abc1", 6);
  105. c.try_emplace("abc2", 5);
  106.  
  107. c.insert(std::pair<std::string, int>("abc3", 5));
  108. c.insert(std::pair<std::string, int>("abc4", 5));
  109.  
  110. b.try_emplace("abc1", 5);
  111. b.try_emplace("abc2", 5);
  112.  
  113. b.insert(std::pair<std::string, int>("abc3", 5));
  114. b.insert(std::pair<std::string, int>("abc4", 5));
  115.  
  116. e.try_emplace("abc1", 5);
  117. e.try_emplace("abc2", 5);
  118.  
  119. e.insert(std::pair<std::string, int>("abc3", 5));
  120. e.insert(std::pair<std::string, int>("abc5", 5));
  121.  
  122. REQUIRE(a == b);
  123. REQUIRE(!(a == c));
  124. REQUIRE(!(a == d));
  125. REQUIRE(!(a == e));
  126. }
  127.  
  128. TEST_CASE("rehash") {
  129. hash_map<int, int> a(5);
  130. a.try_emplace(1, 1);
  131. a.try_emplace(2, 2);
  132. a.try_emplace(3, 3);
  133. a.rehash(10);
  134. REQUIRE(a.contains(1));
  135. REQUIRE(a.contains(2));
  136. REQUIRE(a.contains(3));
  137. REQUIRE(a.size() == 3);
  138. REQUIRE(a.bucket_count() == 10);
  139. }
  140.  
  141. TEST_CASE("simple erase") {
  142. hash_map<int, int> a(5);
  143. a.try_emplace(1, 1);
  144. a.try_emplace(2, 2);
  145. a.try_emplace(3, 3);
  146. a.erase(a.begin());
  147. a.insert_or_assign(3, 3);
  148. int j = 15, i = 17;
  149. a.insert_or_assign(j, i);
  150. REQUIRE(a.contains(3));
  151. a.erase(3);
  152. REQUIRE(!a.contains(3));
  153. REQUIRE(a.size() == 2);
  154. }
  155.  
  156. TEST_CASE("2") {
  157. hash_map<int, int> a(5);
  158. REQUIRE(a.size() == 0);
  159. a.try_emplace(1, 1);
  160. REQUIRE(a.size() == 1);
  161. a.try_emplace(2, 2);
  162. REQUIRE(a.size() == 2);
  163. a.try_emplace(3, 3);
  164. REQUIRE(a.size() == 3);
  165. a.erase(a.begin());
  166. REQUIRE(a.size() == 2);
  167. a.insert_or_assign(3, 3);
  168. REQUIRE(a.size() == 2);
  169. REQUIRE(a.contains(3));
  170. a.erase(3);
  171. REQUIRE(!a.contains(3));
  172. REQUIRE(a.size() == 1);
  173. }
  174.  
  175. TEST_CASE("erase") {
  176. hash_map<std::string, int> a(5);
  177. a.try_emplace("abc1", 5);
  178. a.try_emplace("abc2", 5);
  179.  
  180. a.erase(a.begin());
  181. std::string sss = "abc3";
  182. int kkk = 5;
  183. a.try_emplace(sss, kkk);
  184. std::string s = "abc3";
  185. a.erase("abc3");
  186.  
  187. REQUIRE(a.bucket_count() == 5);
  188. REQUIRE(a.size() == 1);
  189. REQUIRE(a.bucket("abc3") == a.bucket_count());
  190. }
  191.  
  192. TEST_CASE("insert iterators") {
  193. std::vector<std::pair<std::string, int>> vec(5);
  194. vec[0] = {"abc1", 1};
  195. vec[1] = {"abc2", 2};
  196. vec[2] = {"abc3", 3};
  197. vec[3] = {"abc4", 4};
  198. vec[4] = {"abc5", 5};
  199. hash_map<std::string, int> a(1);
  200.  
  201. a.insert(vec.begin(), vec.end());
  202.  
  203. hash_map<std::string, int> b(vec.begin(), vec.end());
  204.  
  205. REQUIRE(b.size() == 5);
  206.  
  207. REQUIRE(a.size() == 5);
  208.  
  209. REQUIRE(a.at("abc1") == 1);
  210. REQUIRE(a.at("abc2") == 2);
  211. REQUIRE(a.at("abc3") == 3);
  212. REQUIRE(a.at("abc4") == 4);
  213. REQUIRE(a.at("abc5") == 5);
  214.  
  215. REQUIRE(b.at("abc1") == 1);
  216. REQUIRE(b.at("abc2") == 2);
  217. REQUIRE(b.at("abc3") == 3);
  218. REQUIRE(b.at("abc4") == 4);
  219. REQUIRE(b.at("abc5") == 5);
  220. }
  221.  
  222. TEST_CASE("merge") {
  223. std::vector<std::pair<std::string, int>> vec(5);
  224. vec[0] = {"abc1", 1};
  225. vec[1] = {"abc2", 2};
  226. vec[2] = {"abc3", 3};
  227. vec[3] = {"abc4", 4};
  228. vec[4] = {"abc5", 5};
  229. hash_map<std::string, int> a(vec.begin(), vec.end());
  230.  
  231. std::vector<std::pair<std::string, int>> vec2(5);
  232. vec2[0] = {"ab1", 1};
  233. vec2[1] = {"ab2", 2};
  234. vec2[2] = {"ab3", 3};
  235. vec2[3] = {"ab4", 4};
  236. vec2[4] = {"abc5", 6};
  237. hash_map<std::string, int> b(vec2.begin(), vec2.end());
  238.  
  239. a.merge(b);
  240.  
  241. REQUIRE(a.size() == 9);
  242. REQUIRE(a.contains("abc1"));
  243. REQUIRE(a.contains("abc2"));
  244. REQUIRE(a.contains("abc3"));
  245. REQUIRE(a.contains("abc4"));
  246. REQUIRE(a.contains("abc5"));
  247. REQUIRE(a.contains("ab1"));
  248. REQUIRE(a.contains("ab2"));
  249. REQUIRE(a.contains("ab3"));
  250. REQUIRE(a.contains("ab4"));
  251.  
  252. std::vector<std::pair<std::string, int>> vec1(5);
  253. vec1[0] = {"abc1", 1};
  254. vec1[1] = {"abc2", 2};
  255. vec1[2] = {"abc3", 3};
  256. vec1[3] = {"abc4", 4};
  257. vec1[4] = {"abc5", 5};
  258. hash_map<std::string, int> c(vec1.begin(), vec1.end());
  259.  
  260. REQUIRE(c.size() == 5);
  261.  
  262. std::vector<std::pair<std::string, int>> vec3(5);
  263. vec3[0] = {"ab1", 1};
  264. vec3[1] = {"ab2", 2};
  265. vec3[2] = {"ab3", 3};
  266. vec3[3] = {"ab4", 4};
  267. vec3[4] = {"abc5", 6};
  268. hash_map<std::string, int> d(vec3.begin(), vec3.end());
  269.  
  270. c.merge(std::move(d));
  271.  
  272. REQUIRE(c.size() == 9);
  273. REQUIRE(c.contains("abc1"));
  274. REQUIRE(c.contains("abc2"));
  275. REQUIRE(c.contains("abc3"));
  276. REQUIRE(c.contains("abc4"));
  277. REQUIRE(c.contains("abc5"));
  278. REQUIRE(c.contains("ab1"));
  279. REQUIRE(c.contains("ab2"));
  280. REQUIRE(c.contains("ab3"));
  281. REQUIRE(c.contains("ab4"));
  282.  
  283. const std::string rrrr = "ab";
  284. auto t = c.cend();
  285. t = c.find(rrrr);
  286. REQUIRE(t == c.cend());
  287. }
  288.  
  289. TEST_CASE("allocators") {
  290. std::vector<std::pair<std::string, int>> vec2(5);
  291. vec2[0] = {"ab1", 1};
  292. vec2[1] = {"ab2", 2};
  293. vec2[2] = {"ab3", 3};
  294. vec2[3] = {"ab4", 4};
  295. vec2[4] = {"ab5", 5};
  296. hash_map<std::string, int> b(vec2.begin(), vec2.end());
  297.  
  298. allocator<std::pair<std::string, int>> all(5);
  299.  
  300. hash_map<std::string, int> c(b, all);
  301.  
  302. REQUIRE(b.getAllocator().x == 10);
  303.  
  304. REQUIRE(c.getAllocator().x == 5);
  305.  
  306. REQUIRE(!(b == c));
  307.  
  308. hash_map<std::string, int> d(all);
  309.  
  310. REQUIRE(d.size() == 0);
  311. REQUIRE(d.getAllocator().x == 5);
  312.  
  313. hash_map<std::string, int> e(std::move(b), all);
  314. REQUIRE(e.getAllocator().x == 5);
  315. REQUIRE(!(b == e));
  316.  
  317. hash_map<std::string, int> f({{"a", 5}});
  318. hash_map<std::string, int> k(5);
  319. k = std::move(f);
  320.  
  321. REQUIRE(k.size() == 1);
  322. REQUIRE(k.contains("a"));
  323.  
  324. auto rrr = k.max_size();
  325. }
  326.  
  327. TEST_CASE("erase iterators") {
  328. std::vector<std::pair<std::string, int>> vec(5);
  329. vec[0] = {"abc1", 1};
  330. vec[1] = {"abc2", 2};
  331. vec[2] = {"abc3", 3};
  332. vec[3] = {"abc4", 4};
  333. vec[4] = {"abc5", 5};
  334. hash_map<std::string, int> a(vec.begin(), vec.end());
  335.  
  336. REQUIRE(a.size() == 5);
  337.  
  338. a.erase(a.begin(), a.end());
  339.  
  340. REQUIRE(a.size() == 0);
  341. }
  342.  
  343. TEST_CASE("reserve") {
  344. std::vector<std::pair<std::string, int>> vec(5);
  345. vec[0] = {"abc1", 1};
  346. vec[1] = {"abc2", 2};
  347. vec[2] = {"abc3", 3};
  348. vec[3] = {"abc4", 4};
  349. vec[4] = {"abc5", 5};
  350. hash_map<std::string, int> a(vec.begin(), vec.end());
  351.  
  352. REQUIRE(a.max_load_factor() == 1.0);
  353. a.max_load_factor(0.75);
  354. REQUIRE(a.max_load_factor() == 0.75);
  355.  
  356. a.reserve(10);
  357.  
  358. REQUIRE(a.size() == 5);
  359. REQUIRE(a.bucket_count() == 14);
  360. }
  361.  
  362. TEST_CASE("operator []") {
  363. std::vector<std::pair<std::string, int>> vec(5);
  364. vec[0] = {"abc1", 1};
  365. vec[1] = {"abc2", 2};
  366. vec[2] = {"abc3", 3};
  367. vec[3] = {"abc4", 4};
  368. vec[4] = {"abc5", 5};
  369. hash_map<std::string, int> a(vec.begin(), vec.end());
  370.  
  371. a["abc1"] = 3;
  372. const int ddd = a.at("abc1");
  373. REQUIRE(ddd == 3);
  374. REQUIRE(a.size() == 5);
  375. std::string kkk = "abc6";
  376. a[kkk] = 7;
  377. REQUIRE(a.size() == 6);
  378. REQUIRE(a.at("abc6") == 7);
  379. REQUIRE(a.count("abc6") == 1);
  380. a.erase(a.find("abc6"));
  381. REQUIRE(!a.contains("abc6"));
  382. }
  383.  
  384. TEST_CASE("swap") {
  385. std::vector<std::pair<std::string, int>> vec(5);
  386. vec[0] = {"abc1", 1};
  387. vec[1] = {"abc2", 2};
  388. vec[2] = {"abc3", 3};
  389. vec[3] = {"abc4", 4};
  390. vec[4] = {"abc5", 5};
  391. hash_map<std::string, int> a(vec.begin(), vec.end());
  392.  
  393. std::vector<std::pair<std::string, int>> vec2(4);
  394. vec2[0] = {"ab1", 1};
  395. vec2[1] = {"ab2", 2};
  396. vec2[2] = {"ab3", 3};
  397. vec2[3] = {"ab4", 4};
  398. hash_map<std::string, int> b(vec2.begin(), vec2.end());
  399.  
  400. a.swap(b);
  401.  
  402. REQUIRE(a.size() == 4);
  403. REQUIRE(a.contains("ab1"));
  404. REQUIRE(a.contains("ab2"));
  405. REQUIRE(a.contains("ab3"));
  406. REQUIRE(a.contains("ab4"));
  407.  
  408. REQUIRE(b.size() == 5);
  409. REQUIRE(b.contains("abc1"));
  410. REQUIRE(b.contains("abc2"));
  411. REQUIRE(b.contains("abc3"));
  412. REQUIRE(b.contains("abc4"));
  413. REQUIRE(b.contains("abc5"));
  414. }
  415.  
  416. TEST_CASE("clear") {
  417. std::vector<std::pair<std::string, int>> vec2(4);
  418. vec2[0] = {"ab1", 1};
  419. vec2[1] = {"ab2", 2};
  420. vec2[2] = {"ab3", 3};
  421. vec2[3] = {"ab4", 4};
  422. hash_map<std::string, int> b({{"ab1", 1}, {"ab2", 2}, {"ab3", 3}, {"ab4", 4}});
  423.  
  424. REQUIRE(b.size() == 4);
  425. b.clear();
  426. REQUIRE(b.empty());
  427. b.emplace("abc", 1);
  428. b.clear();
  429. REQUIRE(b.empty());
  430. }
  431.  
  432. TEST_CASE("operator =") {
  433. std::vector<std::pair<std::string, int>> vec2(4);
  434. vec2[0] = {"ab1", 1};
  435. vec2[1] = {"ab2", 2};
  436. vec2[2] = {"ab3", 3};
  437. vec2[3] = {"ab4", 4};
  438. hash_map<std::string, int> b({{"ab1", 1}, {"ab2", 2}, {"ab3", 3}, {"ab4", 4}});
  439.  
  440. hash_map<std::string, int> a(5);
  441. a = {{"ab1", 1}, {"ab2", 2}, {"ab3", 3}, {"ab4", 4}};
  442.  
  443. REQUIRE(a.size() == b.size());
  444.  
  445. REQUIRE(a.contains("ab1"));
  446. REQUIRE(a.contains("ab2"));
  447. REQUIRE(a.contains("ab3"));
  448. REQUIRE(a.contains("ab4"));
  449.  
  450. REQUIRE(b.contains("ab1"));
  451. REQUIRE(b.contains("ab2"));
  452. REQUIRE(b.contains("ab3"));
  453. REQUIRE(b.contains("ab4"));
  454. }
  455.  
  456. struct custom_hash
  457. {
  458. std::vector<long long unsigned int> rnd;
  459.  
  460. custom_hash()
  461. {
  462. for (int i = 0; i < 1000000; ++i)
  463. rnd.push_back(rand());
  464. }
  465.  
  466. long long unsigned int operator()(int i) const
  467. {
  468. return rnd[i];
  469. }
  470. };
  471.  
  472. template<typename TimePoint>
  473. class time_meter
  474. {
  475. public:
  476. using time_point = TimePoint;
  477.  
  478. private:
  479. std::function<time_point()> m_fnow;
  480. std::function<double(time_point, time_point)> m_fsec;
  481. time_point m_begin;
  482. time_point m_stop;
  483. bool m_stopped;
  484.  
  485. public:
  486. template<typename FNow, typename FSec>
  487. time_meter(FNow&& now, FSec&& sec) : m_fnow(std::forward<FNow>(now)), m_fsec(std::forward<FSec>(sec)), m_begin(m_fnow()), m_stopped(false) { }
  488.  
  489. double seconds() const
  490. {
  491. if (m_stopped)
  492. return m_fsec(m_begin, m_stop);
  493. return m_fsec(m_begin, m_fnow());
  494. }
  495.  
  496. void restart()
  497. {
  498. m_stopped = false;
  499. m_begin = m_fnow();
  500. }
  501.  
  502. void stop()
  503. {
  504. if (m_stopped)
  505. return;
  506. m_stop = m_fnow();
  507. m_stopped = true;
  508. }
  509.  
  510. void start()
  511. {
  512. if (!m_stopped)
  513. return;
  514. m_stopped = false;
  515. m_begin += m_fnow() - m_stop;
  516. }
  517. };
  518.  
  519. auto create_tm()
  520. {
  521. using tm_type = time_meter<std::chrono::high_resolution_clock::time_point>;
  522.  
  523. static const auto get_sec = [](tm_type::time_point p1, tm_type::time_point p2)
  524. {
  525. return static_cast<double>((p2 - p1).count()) / std::chrono::high_resolution_clock::period::den;
  526. };
  527.  
  528. return tm_type(std::chrono::high_resolution_clock::now, get_sec);
  529. }
  530.  
  531. TEST_CASE("_stress")
  532. {
  533. auto tm = create_tm();
  534. hash_map<int, int, custom_hash> m(1000000);
  535. m.max_load_factor(0.1f);
  536. for (int i = 0; i < 1000000; ++i)
  537. {
  538. m.insert({i, i * 3});
  539. }
  540. for (int i = 100; i < 999999; ++i)
  541. {
  542. m.erase(i);
  543. }
  544. for (int i = 0; i < 1000000; ++i)
  545. {
  546. m.insert({i, i * 3});
  547. }
  548. for (int i = 0; i < 1000000; ++i)
  549. {
  550. m.insert({i, i * 3});
  551. }
  552. for (int i = 100; i < 999999; ++i)
  553. {
  554. m.erase(i);
  555. }
  556. for (int i = 100; i < 999999; ++i)
  557. {
  558. m.erase(i);
  559. }
  560. for (int i = 0; i < 100; ++i)
  561. REQUIRE(m[i] == i * 3);
  562. REQUIRE(m[999999] == 2999997);
  563. REQUIRE(m.size() == 101);
  564. for (int i = 0; i < 1000; ++i)
  565. m.insert({rand() % 1000000, rand()});
  566. std::cout << "**********\n" << "STRESS TIME = " << tm.seconds() << "\n**********" << std::endl;
  567. }
  568.  
  569. } //namespace fefu
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!