stxxl::sort()
algorithm
00001 /*************************************************************************** 00002 * algo/test_sort.cpp 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2002 Roman Dementiev <dementiev@mpi-sb.mpg.de> 00007 * 00008 * Distributed under the Boost Software License, Version 1.0. 00009 * (See accompanying file LICENSE_1_0.txt or copy at 00010 * http://www.boost.org/LICENSE_1_0.txt) 00011 **************************************************************************/ 00012 00015 00016 #include <stxxl/mng> 00017 #include <stxxl/sort> 00018 #include <stxxl/vector> 00019 00020 00021 #define RECORD_SIZE 8 00022 00023 struct my_type 00024 { 00025 typedef unsigned key_type; 00026 00027 key_type _key; 00028 char _data[RECORD_SIZE - sizeof(key_type)]; 00029 key_type key() const 00030 { 00031 return _key; 00032 } 00033 00034 my_type() { } 00035 my_type(key_type __key) : _key(__key) { } 00036 00037 static my_type min_value() 00038 { 00039 return my_type((std::numeric_limits<key_type>::min)()); 00040 } 00041 static my_type max_value() 00042 { 00043 return my_type((std::numeric_limits<key_type>::max)()); 00044 } 00045 00046 ~my_type() { } 00047 }; 00048 00049 std::ostream & operator << (std::ostream & o, const my_type & obj) 00050 { 00051 o << obj._key; 00052 return o; 00053 } 00054 00055 bool operator < (const my_type & a, const my_type & b) 00056 { 00057 return a.key() < b.key(); 00058 } 00059 00060 bool operator == (const my_type & a, const my_type & b) 00061 { 00062 return a.key() == b.key(); 00063 } 00064 00065 bool operator != (const my_type & a, const my_type & b) 00066 { 00067 return a.key() != b.key(); 00068 } 00069 00070 struct cmp : public std::less<my_type> 00071 { 00072 my_type min_value() const 00073 { 00074 return my_type::min_value(); 00075 } 00076 my_type max_value() const 00077 { 00078 return my_type::max_value(); 00079 } 00080 }; 00081 00082 00083 int main() 00084 { 00085 unsigned memory_to_use = 128 * 1024 * 1024; 00086 typedef stxxl::vector<my_type> vector_type; 00087 const stxxl::int64 n_records = 00088 stxxl::int64(384) * stxxl::int64(1024 * 1024) / sizeof(my_type); 00089 vector_type v(n_records); 00090 00091 stxxl::random_number32 rnd; 00092 STXXL_MSG("Filling vector..., input size =" << v.size()); 00093 for (vector_type::size_type i = 0; i < v.size(); i++) 00094 v[i]._key = 1 + (rnd() % 0xfffffff); 00095 00096 00097 STXXL_MSG("Checking order..."); 00098 STXXL_MSG(((stxxl::is_sorted(v.begin(), v.end())) ? "OK" : "WRONG")); 00099 00100 STXXL_MSG("Sorting..."); 00101 stxxl::sort(v.begin(), v.end(), cmp(), memory_to_use); 00102 00103 STXXL_MSG("Checking order..."); 00104 STXXL_MSG(((stxxl::is_sorted(v.begin(), v.end())) ? "OK" : "WRONG")); 00105 00106 00107 STXXL_MSG("Done, output size=" << v.size()); 00108 00109 return 0; 00110 }