| // -*- mode: c++ -*- |
| // $Id$ |
| // http://www.bagley.org/~doug/shootout/ |
| |
| #include <algorithm> |
| #include <cstdlib> |
| #include <iostream> |
| #include <list> |
| #include <numeric> |
| |
| template <class _ForwardIterator, class _Tp> |
| void |
| iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value) |
| { |
| while (__first != __last) |
| *__first++ = __value++; |
| } |
| |
| using namespace std; |
| |
| void list_print_n (list<int> L, int n) { |
| int c, lastc = n - 1; |
| list<int>::iterator i; |
| for (c = 0, i = L.begin(); i != L.end() && c < n; ++i, ++c) { |
| cout << (*i); |
| if (c < lastc) cout << " "; |
| } |
| cout << endl; |
| } |
| |
| int main(int argc, char* argv[]) { |
| #ifdef SMALL_PROBLEM_SIZE |
| #define LENGTH 100000 |
| #else |
| #define LENGTH 1000000 |
| #endif |
| int N = (argc == 2 ? (atoi(argv[1]) < 1 ? 1 : atoi(argv[1])): LENGTH); |
| list<int>::iterator i; |
| |
| // create empty list B |
| list<int> B; |
| |
| // create list (A) of integers from 1 through N |
| list<int> A(N); |
| ::iota(A.begin(), A.end(), 1); |
| |
| // move each individual item from A to B, in a loop, reversing order |
| while (! A.empty()) { |
| B.push_front(A.front()); |
| A.pop_front(); |
| } |
| |
| // print first 2 elements of B |
| list_print_n(B, 2); |
| |
| // reverse B (can be done in place) |
| B.reverse(); |
| // reverse(B.begin(), B.end()); |
| |
| // is 0 a member of B? |
| cout << ((find(B.begin(), B.end(), 0) == B.end()) ? "false" : "true") << endl; |
| |
| // is N a member of B? |
| cout << ((find(B.begin(), B.end(), N) == B.end()) ? "false" : "true") << endl; |
| |
| // filter values from B to A that are less than N/2, preserving order |
| int mid = N/2; |
| for (i = B.begin(); i != B.end(); ++i) { |
| if ((*i) < mid) A.push_back(*i); |
| } |
| |
| // print first ten items of A |
| list_print_n(A, 10); |
| |
| // print sum of items in A that are less than 1000 |
| int sum = 0; |
| for (i = A.begin(); i != A.end(); ++i) { |
| if ((*i) < 1000) sum += (*i); |
| } |
| cout << sum << endl; |
| |
| // append B to end of A |
| A.splice(A.end(), B); |
| |
| // print length and last element of A |
| cout << A.size() << " " << A.back() << endl; |
| } |