13 #ifndef STXXL_IN_MEMORY_SORT_HEADER
14 #define STXXL_IN_MEMORY_SORT_HEADER
16 #include <stxxl/bits/namespace.h>
17 #include <stxxl/bits/common/simple_vector.h>
18 #include <stxxl/bits/algo/adaptor.h>
19 #include <stxxl/bits/mng/adaptor.h>
24 __STXXL_BEGIN_NAMESPACE
26 template <
typename ExtIterator_,
typename StrictWeakOrdering_>
27 void stl_in_memory_sort(ExtIterator_ first, ExtIterator_ last, StrictWeakOrdering_ cmp)
29 typedef typename ExtIterator_::vector_type::value_type value_type;
30 typedef typename ExtIterator_::block_type block_type;
32 STXXL_VERBOSE(
"stl_in_memory_sort, range: " << (last - first));
33 unsigned_type nblocks = last.bid() - first.bid() + (last.block_offset() ? 1 : 0);
34 simple_vector<block_type> blocks(nblocks);
35 simple_vector<request_ptr> reqs(nblocks);
38 for (i = 0; i < nblocks; ++i)
39 reqs[i] = blocks[i].read(*(first.bid() + i));
44 unsigned_type last_block_correction = last.block_offset() ? (block_type::size - last.block_offset()) : 0;
45 if (block_type::has_filler)
48 ArrayOfSequencesIterator<
49 block_type,
typename block_type::value_type, block_type::size
50 >(blocks.begin(), first.block_offset()),
51 ArrayOfSequencesIterator<
52 block_type,
typename block_type::value_type, block_type::size
53 >(blocks.begin(), nblocks * block_type::size - last_block_correction),
55 TwoToOneDimArrayRowAdaptor<
56 block_type,
typename block_type::value_type, block_type::size
57 >(blocks.begin(), first.block_offset()),
58 TwoToOneDimArrayRowAdaptor<
59 block_type,
typename block_type::value_type, block_type::size
60 >(blocks.begin(), nblocks * block_type::size - last_block_correction),
65 std::sort(blocks[0].elem + first.block_offset(),
66 blocks[nblocks].elem - last_block_correction, cmp);
69 for (i = 0; i < nblocks; ++i)
70 reqs[i] = blocks[i].write(*(first.bid() + i));
79 #endif // !STXXL_IN_MEMORY_SORT_HEADER