2
\$\begingroup\$

Is there a quicker/better way of doing this, mine works great for small vectors but if i get a vector with an arbitrarily large size this would probably take forever to run. Thanks.(P.S. its been a while since I've written any code so please excuse me for any sloppiness).

/*Fill a vector with integers,
sum each pair of adjacent elements, 
and remove the pair of elements and place sum in the vector*/

#include <iostream>
#include <vector>


int main() {
    std::vector<int> numbers;
    std::cout << "Please enter a list of integers:\n";

    int num1;
    while (std::cin >> num1)
        numbers.push_back(num1);

    // starting from back of the container with integer k representing last element
    // i representing the second to last
    for (int i = numbers.size() - 2, k = numbers.size() - 1; i > -1; i-=2, k-=2) {
        numbers[i] += numbers[k];
        numbers.erase(numbers.begin() + k);
    }
}
\$\endgroup\$
2
\$\begingroup\$

It seems to me that a tiny bit of calculation can simplify the code quite a bit:

auto dest = numbers.size() % 2; // 0 if even, 1 if odd

for (auto src = dest; src < numbers.size(); src += 2, ++dest)
    numbers[dest] = numbers[src] + numbers[src + 1];

numbers.resize(dest);

Although it has the same big-O complexity (linear in both cases) I'd expect this to typically be at least a little faster than the solution @larkey posted, for a couple of reasons. First, it avoids conditional execution by simply computing the starting source/destination positions. Second, when it resizes the array down to the correct size after the additions, it does so in one fell swoop, so to speak, instead of doing a pop_back individually on each item being removed.

If the vector contained objects with non-trivial destructors, the destructor for each object being removed would have to be invoked, so the resize would be linear on the number of items being removed. Given that these are ints, there's really no dtor to run, so the resize can be done with constant complexity (and I'd expect most current implementations of std::vector to include the specializations necessary to actually achieve constant complexity too).

More importantly (at least in my opinion), this seems to me to simplify the code so it's considerably easier to read and understand the intent and result.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Yes, that's far better -- didn't think of iterating over src and dest in one loop -- definitely makes it nicer to read & write. I thought of erase() (which might not be fast) but forgot about resize() which definitely is better. Totally worth any upvote! \$\endgroup\$ – ljrk Jun 29 '16 at 13:33
1
\$\begingroup\$

First, ignoring performance, some general remarks:

  • Why name your variable num1? I think num or num_input would be more clear. num1 often implies at least num2.
  • Possibly put your addition in a separate function.
  • Do you require in-place? Otherwise you could just open up another vector.
  • Also use std::vec<int>::size_type for i or use an iterator instead.

So now for the performance: As @200_success already mentioned, your code runs in quadratic time complexity. This code will run in \$\mathcal{O}(n)\$ and in-place (space-complexity is constant):

#include <iostream>
#include <vector>

/* print elements of vector from start s to end e */
void print_int_vector(std::vector<int> vec, std::vector<int>::size_type s,
                      std::vector<int>::size_type e)
{
    /* possibly swap start and end */
    if (s > e) {
        std::vector<int>::size_type t = s;
        s = e;
        e = t;
    }

    std::cout << "[";
    for (std::vector<int>::size_type i = s; i < e; i++) {
        std::cout << vec[i];
        if (i < e-1) {
            std::cout << ", ";
        }
    }
    std::cout << "]" << std::endl;
}

/* adds adjacent elements, beginning from last, ie:
 *
 *  - for even number of elements in vector:
 *     vec_i = i*2 + i*2+1
 *  - else:
 *     vec_0 = vec_0
 *     vec_i = i*2-1 + i*2-1
 *
 */
void pair_sums(std::vector<int> &numbers)
{
    /*
     * calculate new size of vector & whether we need to subtract 1
     * while indexing
     */
    std::vector<int>::size_type new_size;
    int offset;
    if (numbers.size() % 2 == 0) {
        offset = 0;
        new_size = (numbers.size() / 2);
        numbers[0] = numbers[0] + numbers[1];
    } else {
        new_size = (numbers.size() / 2) +1;
        offset = -1;
        //numbers[0] = numbers[0];
    }

    /* calculate new elements in list */
    for (std::vector<int>::size_type i = 1; i < new_size; i++) {
        numbers[i] = numbers[i*2+offset] + numbers[i*2+offset+1];
    }
    /* remove unneeded elements */
    for (std::vector<int>::size_type i = new_size; i < numbers.size(); i++) {
        numbers.pop_back();
    }
}

int main()
{
    std::vector<int> numbers;
    std::cout << "Please enter a list of integers:\n";

    int num_input;
    while (std::cin >> num_input) {
        numbers.push_back(num_input);
    }

    std::cout << "input:\t"; print_int_vector(numbers, 0, numbers.size());
    pair_sums(numbers);
    std::cout << "output:\t"; print_int_vector(numbers, 0, numbers.size());
}
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Your program doesn't actually produce any output. I assume you are interested in the contents of numbers as your output.

The performance problem is with calling numbers.erase(). Erasing an element creates a "hole", which needs to be filled by copying all subsequent elements to their preceding position. Thus numbers.erase() is an \$O(n)\$ operation, and your whole program is \$O(n^2)\$ because you call numbers.erase() \$\frac{n}{2}\$ times.

The tricky part of the problem is that you don't know whether the results should consist of

$$(a_0 + a_1), (a_2 + a_3), (a_4 + a_5), (a_6 + a_7) + \ldots + (a_{n-2} + a_{n-1})$$

or

$$(a_0), (a_1 + a_2), (a_3 + a_4), (a_5 + a_6), (a_7 + a_8) + \ldots + (a_{n-2} + a_{n-1})$$

until you find out whether \$n\$ is odd or even. Therefore, I suggest that you build both results speculatively, then keep the appropriate one when you find out whether \$n\$ is odd or even.

#include <iostream>
#include <vector>

std::vector<int> pair_sums(std::istream &in) {
    std::vector<int> even_pair_sums, odd_pair_sums;
    size_t i = 0;
    for (int n, even_buf = 0, odd_buf = 0; in >> n; ) {
        if (i++ % 2 == 0) {
            odd_pair_sums.push_back(odd_buf + n);
            odd_buf = 0;
            even_buf = n;
        } else {
            even_pair_sums.push_back(even_buf + n);
            even_buf = 0;
            odd_buf = n;
        }
    }
    return (i % 2) ? odd_buf : even_buf;
}

int main() {
    std::vector<int> numbers = pair_sums(std::cin);
}   
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ OP doesn't require it to be computed "live" on input but already has the complete vector provided when calculating the sums -- so why not just use size() to determine even/odd beforehand? \$\endgroup\$ – ljrk Jun 27 '16 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.