(C++) GetMinThree

 

GetMinThree is a container code snippet to get the three least values in a container.

 

• Download the Qt Creator project 'GetMinThree' (zip)

 

 

 

 

 

Technical facts

 

Application type(s)

• Desktop application

Operating system(s) or programming environment(s)

• Lubuntu 12.10 (quantal)

IDE(s):

• Qt Creator 2.5.2

Project type:

• Console application

C++ standard:

• C++98

Compiler(s):

• G++ 4.7.2

Libraries used:

• STL: GNU ISO C++ Library, version 4.7.2

 

 

 

 

 

Qt project file: CppGetMinThree.pro

 

---

TEMPLATE = app CONFIG += console CONFIG -= qt SOURCES += main.cpp

 

 

 

 

 

main.cpp

 

---

#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"));   } }

 

Screen output:

 

---

Before: 83 86 77 15 93 35 86 92 49 21 After: 15 21 35 Before: 62 27 90 59 63 26 40 26 72 36 After: 90 72 63 Before: h with 68$ d with 29$ q with 30$ c with 23$ x with 35$ j with 2$ o with 58$ f with 67$ x with 56$ j with 42$ After: h with 68$ f with 67$ o with 58$