This is an example of how to use some basic algorithms from stream package. This example shows how to create sorted_runs
data structure using stream::use_push
specialization of stream::runs_creator
class
/*************************************************************************** * stream/test_push_sort.cpp * * Part of the STXXL. See http://stxxl.sourceforge.net * * Copyright (C) 2004 Roman Dementiev <[email protected]> * * Distributed under the Boost Software License, Version 1.0. * (See accompanying file LICENSE_1_0.txt or copy at * http://www.boost.org/LICENSE_1_0.txt) **************************************************************************/ #include <stxxl/stream> typedef unsigned value_type; struct Cmp : public std::binary_function<value_type, value_type, bool> { typedef unsigned value_type; bool operator () (const value_type & a, const value_type & b) const { return a < b; } value_type min_value() { return (std::numeric_limits<value_type>::min)(); } value_type max_value() { return (std::numeric_limits<value_type>::max)(); } }; int main() { // special parameter type typedef stxxl::stream::use_push<value_type> InputType; typedef stxxl::stream::runs_creator<InputType, Cmp, 4096, stxxl::RC> CreateRunsAlg; typedef CreateRunsAlg::sorted_runs_type SortedRunsType; unsigned size = (30 * 1024 * 128 / (sizeof(value_type) * 2)); unsigned i = 0; Cmp c; CreateRunsAlg SortedRuns(c, 1024 * 128); value_type oldcrc(0); stxxl::random_number32 rnd; //stxxl::random_number<> rnd_max; unsigned cnt = size; while (cnt > 0) { const value_type tmp = rnd(); oldcrc += tmp; SortedRuns.push(tmp); // push into the sorter --cnt; } SortedRunsType Runs = SortedRuns.result(); // get sorted_runs data structure assert(stxxl::stream::check_sorted_runs(Runs, Cmp())); // merge the runs stxxl::stream::runs_merger<SortedRunsType, Cmp> merger(Runs, Cmp(), 1024 * 128 / 10 * stxxl::sort_memory_usage_factor()); stxxl::vector<value_type> array; STXXL_MSG(size << " " << Runs.elements); STXXL_MSG("CRC: " << oldcrc); value_type crc(0); for (i = 0; i < size; ++i) { crc += *merger; array.push_back(*merger); ++merger; } STXXL_MSG("CRC: " << crc); assert(stxxl::is_sorted(array.begin(), array.end(), Cmp())); assert(merger.empty()); return 0; }