1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
/***************************************************************************
* examples/containers/deque2.cpp
*
* Part of the STXXL. See http://stxxl.sourceforge.net
*
* Copyright (C) 2013 Daniel Feist <daniel.feist@student.kit.edu>
*
* 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/deque>
#include <iostream>
int main()
{
typedef stxxl::deque<unsigned int> deque;
deque my_deque;
unsigned int random, p, x;
unsigned int smaller_left = 0;
unsigned int smaller_right = 0;
stxxl::random_number32 rand32;
stxxl::uint64 number_of_elements = 8 * 1024 * 1024;
// fill deque with random integer values
for (stxxl::uint64 i = 0; i < number_of_elements; i++)
{
random = rand32(); // produce random integer from intervall [0,2^32)
my_deque.push_front(random);
}
stxxl::deque_iterator<deque> deque_iterator = my_deque.begin();
// Access random element x at position p(x) in the deque
p = rand32() % number_of_elements;
x = my_deque[p];
// Count number of smaller elements from the front to p(x) - 1
for (stxxl::uint64 j = 0; j < p; j++)
{
if (*deque_iterator < x)
{
smaller_left += 1;
}
++deque_iterator;
}
++deque_iterator;
// Count number of smaller elements from p(x) + 1 to the end
for (stxxl::uint64 k = p + 1; k < number_of_elements - 1; k++)
{
if (*deque_iterator < x)
{
smaller_right += 1;
}
++deque_iterator;
}
STXXL_MSG("smaller left: " << smaller_left << ", smaller right: " << smaller_right);
return 0;
}
|
