#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
struct Person
{
std::string name;
double money;
};
bool operator==(const Person& lhs, const Person& rhs)
{
return lhs.name == rhs.name && lhs.money == rhs.money;
}
bool operator<(const Person& lhs, const Person& rhs)
{
return lhs.money < rhs.money; //All I care about is money
}
bool operator>(const Person& lhs, const Person& rhs)
{
return lhs.money > rhs.money; //All I care about is money
}
bool operator>=(const Person& lhs, const Person& rhs)
{
return !(lhs < rhs);
}
std::ostream& operator<<(std::ostream& os, const Person& p)
{
os << p.name << " with " << p.money << '$';
return os;
}
const std::vector<Person> CreatePersons(const int sz)
{
std::vector<Person> v(sz);
for (int i=0; i!=sz; ++i)
{
Person p;
p.name = 'a' + (std::rand() % 26);
p.money = static_cast<double>(std::rand() % 100);
v[i] = p;
}
return v;
}
template <class T>
const T GetMinThreeUsingPartial_sort(T t)
{
assert(t.size() >= 3);
std::partial_sort(t.begin(),t.begin() + 3,t.end());
t.resize(3);
return t;
}
template <class T>
const T GetMinThreeUsingNth_element(T t)
{
assert(t.size() >= 3);
std::partial_sort(t.begin(),t.begin() + 3,t.end());
t.resize(3);
return t;
}
template <class T>
const T GetMaxThreeUsingPartial_sort(T t)
{
assert(t.size() >= 3);
std::partial_sort(t.begin(),t.begin() + 3,t.end(),std::greater<typename T::value_type>());
t.resize(3);
return t;
}
template <class T>
const T GetMaxThreeUsingNth_element(T t)
{
assert(t.size() >= 3);
std::partial_sort(t.begin(),t.begin() + 3,t.end(),std::greater<typename T::value_type>());
t.resize(3);
return t;
}
const std::vector<int> Create(const int sz)
{
std::vector<int> v(sz);
for (int i=0; i!=sz; ++i)
{
v[i] = std::rand() % 100;
}
return v;
}
int main()
{
const int sz = 10;
//GetMinThree
{
const std::vector<int> v = Create(sz);
const std::vector<int> x = GetMinThreeUsingPartial_sort(v);
const std::vector<int> y = GetMinThreeUsingNth_element(v);
assert(x.front() <= v.back());
assert(y.front() <= v.back());
{
//std::nth_element does not return a sorted container
std::vector<int> y_sorted(y);
std::sort(y_sorted.begin(),y_sorted.end());
assert(y_sorted == x);
}
std::cout << "Before:\n";
std::copy(v.begin(),v.end(),std::ostream_iterator<int>(std::cout,"\n"));
std::cout << "After:\n";
std::copy(x.begin(),x.end(),std::ostream_iterator<int>(std::cout,"\n"));
}
//GetMaxThree
{
const std::vector<int> v = Create(sz);
const std::vector<int> x = GetMaxThreeUsingPartial_sort(v);
const std::vector<int> y = GetMaxThreeUsingNth_element(v);
assert(x.front() >= v.back());
assert(y.front() >= v.back());
{
//std::nth_element does not return a sorted container
std::vector<int> y_sorted(y);
std::sort(y_sorted.begin(),y_sorted.end(),std::greater<int>());
assert(y_sorted == x);
}
std::cout << "Before:\n";
std::copy(v.begin(),v.end(),std::ostream_iterator<int>(std::cout,"\n"));
std::cout << "After:\n";
std::copy(x.begin(),x.end(),std::ostream_iterator<int>(std::cout,"\n"));
}
//GetMaxThree on Person
{
const std::vector<Person> v = CreatePersons(sz);
const std::vector<Person> x = GetMaxThreeUsingPartial_sort(v);
const std::vector<Person> y = GetMaxThreeUsingNth_element(v);
assert(x.front() >= v.back());
assert(y.front() >= v.back());
{
//std::nth_element does not return a sorted container
std::vector<Person> y_sorted(y);
std::sort(y_sorted.begin(),y_sorted.end(),std::greater<Person>());
assert(y_sorted == x);
}
std::cout << "Before:\n";
std::copy(v.begin(),v.end(),std::ostream_iterator<Person>(std::cout,"\n"));
std::cout << "After:\n";
std::copy(x.begin(),x.end(),std::ostream_iterator<Person>(std::cout,"\n"));
}
}
|
Desktop application
Lubuntu 12.10 (quantal)
Qt Creator 2.5.2
STL: GNU ISO C++ Library, version 4.7.2
