### vector

hi. I would like to code a function which takes a vector of ten numbers as an argument. the function should return the sum of the three largerst numbers.I would like to use a sort, and then add.
 ``1234567891011121314151617181920`` ``````#include #include using namespace std; int func(vector numbers) { int SUM = 0; int MAX = 0; for(int i=0; i MAX) { MAX = numbers[i]; } } SUM += MAX; return SUM; }``````
Last edited on
 ``123456789101112`` ``````#include // std::sort #include // std::vector using namespace std; int SumTop3(vector numbers) { int SUM = 0; sort(numbers.begin(), numbers.end()); for ( int i = numbers.size() - 3 ; i < numbers.size() ; ++i) SUM += numbers[i]; return SUM; }``````
Last edited on
you make it look so easy!!!
 ``123456`` ``````int func(vector numbers) { int s = numbers.size(); sort( numbers.begin(), numbers.end() ); return numbers[s-1] + numbers[s-2] + numbers[s-3]; }``````
:)
sorting the whole vector is waste of time: if all you need are the three largest elements, use `nth_element`

 ``12345678910111213141516`` ``````#include #include #include #include #include int func(std::vector v) { if(v.size() < 3) throw std::runtime_error("Your vector is too small"); nth_element(v.begin(), v.begin()+3, v.end(), std::greater()); return v[0] + v[1] + v[2]; } int main() { std::cout << func({1,2,3,4,5,6,7,8,9,10,20,30}) << '\n'; }``````

demo: http://ideone.com/UxWpdt

Granted, copying before sort/nth_element is a waste of time too, the best way is really to maintain just the three integers and update them as you iterate through the vector.

There's even a library for that:

 ``123456789101112131415161718`` ``````#include #include #include #include #include #include int func(const std::vector& v) { using namespace boost::accumulators; accumulator_set>> acc(tag::tail::cache_size = 3); acc = for_each(v.begin(), v.end(), acc); return accumulate(tail(acc).begin(), tail(acc).end(), 0); } int main() { std::cout << func({1,2,3,4,5,6,7,8,9,10,20,30}) << '\n'; }``````

demo: http://ideone.com/ySxuxX
Last edited on
 you make it look so easy!!!

I can make it look harder.

 ``123456789101112131415161718192021222324252627282930313233343536`` ``````#include #include #include template Type sumOfGreatestN(Iterator begin, Iterator end) { Type r(0); unsigned int i = 0; while (i++ != n && begin != end) { std::iter_swap(begin, std::max_element(begin, end)); r += *begin; ++begin; } return r; } int main() { std::vector vi; vi.push_back(-30); vi.push_back(10); vi.push_back(-10); vi.push_back(0); vi.push_back(20); vi.push_back(100); vi.push_back(-40); vi.push_back(500); vi.push_back(-600); std::cout << sumOfGreatestN(vi.begin(), vi.end()) << std::endl; }``````

Topic archived. No new replies allowed.