online compiler and debugger for c/c++

/* * This example program show's C++'s provided heap data structure, and how * to use it to sort a vector of integers. We do some timing experiments * to see how long it takes to sort a vector of 1 million integers, and * compare that to the time it takes to sort the same vector using the * std::sort and std::stable_sort algorithms. */ #include <iostream> #include <vector> #include <algorithm> #include <functional> #include <random> #include <chrono> #include <iomanip> #include <cassert> void printVector(const std::vector<int>& vec) { // Prints the first four and last four elements of a vector, separated // by commas, with an elipsis in the middle. We assume the vector has // more than eight elements. constexpr size_t SHOWLEN = 4; assert(vec.size() > 2 * SHOWLEN); for (size_t i = 0; i < SHOWLEN; ++i) { std::cout << vec[i] << ", "; } std::cout << "... "; size_t size = vec.size(); for (size_t i = size - SHOWLEN; i < size; ++i) { std::cout << ", " << vec[i]; } std::cout << std::endl; } int main() { // Create a vector of 5 million random integers. constexpr size_t N = 5000000; std::vector<int> data; data.reserve(N); std::random_device rd; std::seed_seq seed{rd(),rd(),rd(),rd()}; std::mt19937 rng(seed); for (size_t i = 0; i < N; ++i) { data.push_back(i); } // Shuffle the vector. std::shuffle(data.begin(), data.end(), rng); std::cout << N << " random integers generated:\n "; printVector(data); // Make a duplicate of the vector, so we can sort it using std::sort std::vector<int> sortMe = data; // Sort the vector using std::sort. auto start = std::chrono::high_resolution_clock::now(); std::sort(sortMe.begin(), sortMe.end()); auto end = std::chrono::high_resolution_clock::now(); std::chrono::duration<double> elapsed = end - start; std::cout << "std::sort took " << std::fixed << std::setprecision(3) << elapsed.count() << " seconds, result:\n "; printVector(sortMe); // Do it all again for std::stable_sort. sortMe = data; start = std::chrono::high_resolution_clock::now(); std::stable_sort(sortMe.begin(), sortMe.end()); end = std::chrono::high_resolution_clock::now(); elapsed = end - start; std::cout << "std::stable_sort took " << std::fixed << std::setprecision(3) << elapsed.count() << " seconds, result:\n "; printVector(sortMe); // C++ does not provide a std::heap<T> data structure, instead it provides // some algorithms that operate on a vector of elements (or something // vector-like). These are std::make_heap, std::push_heap, std::pop_heap, // and std::sort_heap. // std::make_heap // Heapifies a vector of elements, so that the largest element is // at the front of the vector (a max-heap). // std::push_heap // Adds a new element to the heap, and reorders the heap so that // the largest element is at the front of the vector. // std::pop_heap // Removes the largest element from the heap, and reorders the heap // so that the largest element is at the front of the vector. The // largest element is not removed from the vector, but is moved to // just past the end of the heap area in the vector. // std::sort_heap // Sorts a heapified vector of elements, so that the elements are // in ascending order. It just repeatedly calls std::pop_heap. // (For clarity, we don't use std::sort_heap in this example and // instead call std::pop_heap repeatedly.) // Sort the vector using std::make_heap, std::push_heap, and // std::pop_heap. sortMe = data; start = std::chrono::high_resolution_clock::now(); auto heapStart = sortMe.begin(); auto heapEnd = sortMe.end(); std::make_heap(heapStart, heapEnd); for (size_t i = 1; i < N; ++i) { std::pop_heap(heapStart, heapEnd); // The max element is now at the end of the heap area, and the heap // area is one element smaller. --heapEnd; } end = std::chrono::high_resolution_clock::now(); elapsed = end - start; std::cout << "std::make_heap, std::push_heap, and std::pop_heap took " << std::fixed << std::setprecision(3) << elapsed.count() << " seconds, result:\n "; printVector(sortMe); return 0; }