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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <vector>
#include <iostream>
using namespace std;

int func(vector<int> numbers)
{
    int SUM = 0;
    int MAX = 0;
   
   for(int i=0; i<numbers.size(); i++)
   {
        int found;
        if(numbers[i] > MAX)
       {
            MAX = numbers[i];
       }
   }
   SUM += MAX;
   return SUM;
}
Last edited on
1
2
3
4
5
6
7
8
9
10
11
12
#include <algorithm> // std::sort
#include <vector>    // std::vector
using namespace std;

int SumTop3(vector<int> 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!!!
1
2
3
4
5
6
int func(vector<int> 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <vector>
#include <stdexcept>
#include <algorithm>
#include <functional>

int func(std::vector<int> 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<int>());
    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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <boost/accumulators/accumulators.hpp>
#include <boost/accumulators/statistics/tail.hpp>

int func(const std::vector<int>& v)
{
    using namespace boost::accumulators;
    accumulator_set<int, features<tag::tail<right>>> acc(tag::tail<right>::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.

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
#include <algorithm>
#include <iostream>
#include <vector>

template <typename Type, unsigned int n, typename Iterator>
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<int> 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<int, 3>(vi.begin(), vi.end()) << std::endl;
}

Topic archived. No new replies allowed.