fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. #include <set>
  5. #include <unordered_set>
  6. #include <string>
  7. #include <algorithm>
  8. #include <numeric>
  9. #include <random>
  10. #include <chrono>
  11.  
  12. using namespace std;
  13. using namespace std::chrono;
  14.  
  15. // Returns shuffled sequence of unique numbers of specified size, with values from start to start + size - 1.
  16. vector<int> shuffled_sequence(int size, int start = 0) {
  17.     vector<int> result(size);
  18.     iota(result.begin(), result.end(), start);
  19.     random_shuffle(result.begin(), result.end());
  20.     return result;
  21. }
  22.  
  23. // Returns sequence of random numbers of specified size, with values from 0 to max.
  24. vector<int> random_sequence(int size, int max) {
  25.     random_device rd;
  26.     default_random_engine generator(rd());
  27.     uniform_int_distribution<int> distribution(0, max);
  28.     vector<int> result;
  29.     for (int i = 0; i < size; i++) {
  30.         result.push_back(distribution(generator));
  31.     }
  32.     return result;
  33. }
  34.  
  35. // ��������� ������������� ��� �������
  36. template<typename Container>
  37. void insert_element(Container& container, int elem, bool insert_at_beginning) {
  38.     if (insert_at_beginning) {
  39.         container.insert(container.begin(), elem);
  40.     } else {
  41.         container.push_back(elem);
  42.     }
  43. }
  44.  
  45. // ������������� ��� set
  46. template<>
  47. void insert_element<set<int>>(set<int>& container, int elem, bool insert_at_beginning) {
  48.     container.insert(elem);
  49. }
  50.  
  51. // ������������� ��� unordered_set
  52. template<>
  53. void insert_element<unordered_set<int>>(unordered_set<int>& container, int elem, bool insert_at_beginning) {
  54.     container.insert(elem);
  55. }
  56.  
  57. template<typename Container>
  58. void test_insertion(const vector<int>& elements, const string& container_name, bool insert_at_beginning = false) {
  59.     Container container;
  60.  
  61.     auto start = high_resolution_clock::now();
  62.  
  63.     for (const auto& elem : elements) {
  64.         insert_element(container, elem, insert_at_beginning);
  65.     }
  66.  
  67.     auto end = high_resolution_clock::now();
  68.     auto duration = duration_cast<microseconds>(end - start);
  69.  
  70.     string operation = insert_at_beginning ? "insert at beginning" : "insert at end";
  71.     if (container_name == "set" || container_name == "unordered_set") {
  72.         operation = "insert";
  73.     }
  74.  
  75.     cout << container_name << " " << operation << " time for " << elements.size()
  76.          << " elements: " << duration.count() << " microseconds" << endl;
  77. }
  78.  
  79. // ��������� ������������� ��� ������
  80. template<typename Container>
  81. int search_in_container(Container& container, const vector<int>& search_elements) {
  82.     int hits = 0;
  83.     for (const auto& elem : search_elements) {
  84.         auto it = find(container.begin(), container.end(), elem);
  85.         if (it != container.end()) {
  86.             hits++;
  87.         }
  88.     }
  89.     return hits;
  90. }
  91.  
  92. // ������������� ��� set
  93. template<>
  94. int search_in_container<set<int>>(set<int>& container, const vector<int>& search_elements) {
  95.     int hits = 0;
  96.     for (const auto& elem : search_elements) {
  97.         auto it = container.find(elem);
  98.         if (it != container.end()) {
  99.             hits++;
  100.         }
  101.     }
  102.     return hits;
  103. }
  104.  
  105. // ������������� ��� unordered_set
  106. template<>
  107. int search_in_container<unordered_set<int>>(unordered_set<int>& container, const vector<int>& search_elements) {
  108.     int hits = 0;
  109.     for (const auto& elem : search_elements) {
  110.         auto it = container.find(elem);
  111.         if (it != container.end()) {
  112.             hits++;
  113.         }
  114.     }
  115.     return hits;
  116. }
  117.  
  118. template<typename Container>
  119. void test_search(Container& container, const vector<int>& search_elements, const string& container_name) {
  120.     auto start = high_resolution_clock::now();
  121.  
  122.     int hits = search_in_container(container, search_elements);
  123.  
  124.     auto end = high_resolution_clock::now();
  125.     auto duration = duration_cast<microseconds>(end - start);
  126.  
  127.     cout << container_name << " search time for " << search_elements.size()
  128.          << " elements: " << duration.count() << " microseconds (hits: " << hits << ")" << endl;
  129. }
  130.  
  131. int main() {
  132.     const int M = 10000; // Number of search operations
  133.  
  134.     vector<int> sizes = {10, 100, 1000, 10000, 100000};
  135.  
  136.     for (int size : sizes) {
  137.         cout << "\n=== Testing with " << size << " elements ===" << endl;
  138.  
  139.         const auto elems_to_add = shuffled_sequence(size);
  140.         const auto elems_to_search = random_sequence(M, 2 * size);
  141.  
  142.         // Test vector - insert at end
  143.         test_insertion<vector<int>>(elems_to_add, "vector", false);
  144.  
  145.         // Test vector - insert at beginning
  146.         test_insertion<vector<int>>(elems_to_add, "vector", true);
  147.  
  148.         // Test list - insert at end
  149.         test_insertion<list<int>>(elems_to_add, "list", false);
  150.  
  151.         // Test list - insert at beginning
  152.         test_insertion<list<int>>(elems_to_add, "list", true);
  153.  
  154.         // Test set
  155.         test_insertion<set<int>>(elems_to_add, "set");
  156.  
  157.         // Test unordered_set
  158.         test_insertion<unordered_set<int>>(elems_to_add, "unordered_set");
  159.  
  160.         cout << "--- Search tests ---" << endl;
  161.  
  162.         // Prepare containers for search tests
  163.         vector<int> vec_end(elems_to_add.begin(), elems_to_add.end());
  164.  
  165.         vector<int> vec_begin;
  166.         for (auto it = elems_to_add.rbegin(); it != elems_to_add.rend(); ++it) {
  167.             vec_begin.push_back(*it);
  168.         }
  169.  
  170.         list<int> lst_end(elems_to_add.begin(), elems_to_add.end());
  171.         list<int> lst_begin(elems_to_add.begin(), elems_to_add.end());
  172.  
  173.         set<int> st(elems_to_add.begin(), elems_to_add.end());
  174.         unordered_set<int> ust(elems_to_add.begin(), elems_to_add.end());
  175.  
  176.         // Test search operations
  177.         test_search(vec_end, elems_to_search, "vector (end)");
  178.         test_search(vec_begin, elems_to_search, "vector (begin)");
  179.         test_search(lst_end, elems_to_search, "list (end)");
  180.         test_search(lst_begin, elems_to_search, "list (begin)");
  181.         test_search(st, elems_to_search, "set");
  182.         test_search(ust, elems_to_search, "unordered_set");
  183.     }
  184.  
  185.     return 0;
  186. }
  187.  
Success #stdin #stdout 4.19s 19644KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
=== Testing with 10 elements ===
vector insert at end time for 10 elements: 0 microseconds
vector insert at beginning time for 10 elements: 0 microseconds
list insert at end time for 10 elements: 0 microseconds
list insert at beginning time for 10 elements: 0 microseconds
set insert time for 10 elements: 1 microseconds
unordered_set insert time for 10 elements: 2 microseconds
--- Search tests ---
vector (end) search time for 10000 elements: 65 microseconds (hits: 4739)
vector (begin) search time for 10000 elements: 65 microseconds (hits: 4739)
list (end) search time for 10000 elements: 91 microseconds (hits: 4739)
list (begin) search time for 10000 elements: 89 microseconds (hits: 4739)
set search time for 10000 elements: 87 microseconds (hits: 4739)
unordered_set search time for 10000 elements: 185 microseconds (hits: 4739)

=== Testing with 100 elements ===
vector insert at end time for 100 elements: 0 microseconds
vector insert at beginning time for 100 elements: 1 microseconds
list insert at end time for 100 elements: 3 microseconds
list insert at beginning time for 100 elements: 1 microseconds
set insert time for 100 elements: 8 microseconds
unordered_set insert time for 100 elements: 8 microseconds
--- Search tests ---
vector (end) search time for 10000 elements: 300 microseconds (hits: 4927)
vector (begin) search time for 10000 elements: 295 microseconds (hits: 4927)
list (end) search time for 10000 elements: 886 microseconds (hits: 4927)
list (begin) search time for 10000 elements: 889 microseconds (hits: 4927)
set search time for 10000 elements: 169 microseconds (hits: 4927)
unordered_set search time for 10000 elements: 185 microseconds (hits: 4927)

=== Testing with 1000 elements ===
vector insert at end time for 1000 elements: 2 microseconds
vector insert at beginning time for 1000 elements: 49 microseconds
list insert at end time for 1000 elements: 23 microseconds
list insert at beginning time for 1000 elements: 11 microseconds
set insert time for 1000 elements: 90 microseconds
unordered_set insert time for 1000 elements: 87 microseconds
--- Search tests ---
vector (end) search time for 10000 elements: 2572 microseconds (hits: 5124)
vector (begin) search time for 10000 elements: 2623 microseconds (hits: 5124)
list (end) search time for 10000 elements: 9308 microseconds (hits: 5124)
list (begin) search time for 10000 elements: 9821 microseconds (hits: 5124)
set search time for 10000 elements: 400 microseconds (hits: 5124)
unordered_set search time for 10000 elements: 228 microseconds (hits: 5124)

=== Testing with 10000 elements ===
vector insert at end time for 10000 elements: 72 microseconds
vector insert at beginning time for 10000 elements: 7747 microseconds
list insert at end time for 10000 elements: 520 microseconds
list insert at beginning time for 10000 elements: 184 microseconds
set insert time for 10000 elements: 1981 microseconds
unordered_set insert time for 10000 elements: 1308 microseconds
--- Search tests ---
vector (end) search time for 10000 elements: 34846 microseconds (hits: 4987)
vector (begin) search time for 10000 elements: 34060 microseconds (hits: 4987)
list (end) search time for 10000 elements: 112250 microseconds (hits: 4987)
list (begin) search time for 10000 elements: 118706 microseconds (hits: 4987)
set search time for 10000 elements: 1045 microseconds (hits: 4987)
unordered_set search time for 10000 elements: 596 microseconds (hits: 4987)

=== Testing with 100000 elements ===
vector insert at end time for 100000 elements: 271 microseconds
vector insert at beginning time for 100000 elements: 846314 microseconds
list insert at end time for 100000 elements: 2832 microseconds
list insert at beginning time for 100000 elements: 1949 microseconds
set insert time for 100000 elements: 34094 microseconds
unordered_set insert time for 100000 elements: 10567 microseconds
--- Search tests ---
vector (end) search time for 10000 elements: 307423 microseconds (hits: 5004)
vector (begin) search time for 10000 elements: 286875 microseconds (hits: 5004)
list (end) search time for 10000 elements: 1174832 microseconds (hits: 5004)
list (begin) search time for 10000 elements: 1111067 microseconds (hits: 5004)
set search time for 10000 elements: 2549 microseconds (hits: 5004)
unordered_set search time for 10000 elements: 1343 microseconds (hits: 5004)
https://ideone.com/R4ChHf
language:
C++ (gcc 8.3)
created:
1 day 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!