It's back...

[Enot02]

What is it? It's EAccessViolation.
Code:

//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop
#include <vector>
#include <iostream>
//---------------------------------------------------------------------------

#pragma argsused
using namespace std;
int main(int argc, char* argv[])
{
        vector<int> a,b;
        int c=0,d=0,e=0;
        int* f;
        cin>>c;
        for(int g=0;g<c;g++)
        {
                cin>>d;
                a.push_back(d);
        }
        e=a[0];
        while(a.capacity()>1)
        {
                for(int g=0;g<a.capacity();g++)
                {
                        min(e,a[g]);
                        if(e<a[g])*f=g;
                }
                b.push_back(e);
                a.erase(a.begin(),f);
        }
        b.push_back(a[0]);
        for(int g=0;g<b.capacity();g++)
        {
                cout<<b[g];
        }
        return 0;
}
//--------------------------------------------------------------------------- 

The program should create a vector of the smallest numbers after the last one.
But it throws AccessViolation on 28th line.

[AbstractionAnon]

What is it? It's EAccessViolation.

That's an attempt to access memory that doesn't belong to you. Most often caused by an out of bounds reference.

Line 23,25,34: vector::capacity() and vector::size() are not the same thing. capacity() returns how many elements are currently allocated. size() returns how many actually exist. An attempt to reference an element >= size() (even if allocated) will result in undefined behavior, in your case this was an access violation.

[Chervil]

The code won't compile for me, at line 31

    a.erase(a.begin(),f);

[Error] no matching function for call to 'std::vector<int>::erase(std::vector<int>::iterator, int*&)'

http://www.cplusplus.com/reference/vector/vector/erase/

Also, you should definitely not be using vector.capacity() in that manner. All we know about the capacity is that it is at least as large as the size(), other than that it is pretty much meaningless in this context.
Perhaps you meant to use size() instead?

http://www.cplusplus.com/reference/vector/vector/capacity/
http://www.cplusplus.com/reference/vector/vector/size/

One more thing,

    *f = g;

the value g is assigned to the integer pointed to by f.
But what exactly does f point to? It is uninitialised, and will result in undefined behaviour, such as an access violation.


Also, the use of single-letter variable names make the code pretty much unreadable. Try using names which describe the purpose of each variable.

(well, for loop counters, single letters are acceptable, for pretty much anything else, they serve the purpose of increasing obscurity).

[Enot02]

It should be the pointer to the a[g] element to save it and use for erase()

[cire]

It should be the pointer to the a[g] element to save it and use for erase()

In that case, the line would be f = &a[g];, but a pointer to an element is not what erase expects as noted by Chervil above.

[Enot02]

But how can you convert a number into an iterator?

[cire]

An index is simply an offset from the iterator returned by a.begin(). Use a.begin()+g to obtain an iterator which refers to the gth element of a.

[Enot02]

Well now it does wrong things. If I paste in

22
3 1 5 4 8 105 2 6 10 9 7 13 15 14 533 16
11 12 19 18 17 220

that program outputs 3 and 220.

[Chervil]

What would be the correct output, and why?

[Enot02]

The correct output is

1 2 6 7 11 12 17

[Chervil]

So this is the input and the output. Could you explain how the output is selected:

3 1 5 4 8 105 2 6 10 9 7 13 15 14 533 16 11 12 19 18 17 220
  1           2 6      7                 11 12       17

I know programmers are supposed to be good at identifying patterns, but I haven't figured this out yet.

[Chervil]

Ok, I think I have it:

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> vec_a;
    std::vector<int> vec_b;

    int count = 0;
    int input = 0;

    std::cout << "How many numbers? ";
    std::cin >> count;

    for (int g = 0; g<count; g++)
    {
        std::cin >> input;
        vec_a.push_back(input);
    }

    while (vec_a.size() > 1)
    {
        size_t offset = 0;

        int minimum = vec_a[0];

        for (size_t g=0; g<vec_a.size(); g++)
        {
            if (minimum  > vec_a[g])
            {
                minimum = vec_a[g];
                offset = g;
            }
        }

        vec_b.push_back(minimum);

        vec_a.erase(vec_a.begin(), vec_a.begin() + offset + 1);
    }

    for (size_t g=0; g<vec_b.size(); g++)
    {
        std::cout << vec_b[g] << ' ';
    }

    std::cout << "\n Done \n";
}

[Enot02]

So, what is the difference?

[Chervil]

The incorrect code was replaced with corrected code - when the requirements were understood.
1. find the smallest value in the vector.
2. insert that value into the second vector.
3. erase from start up to and including the smallest value.

repeat.

[Enot02]

Correct! I actually with your help made it myself!!!

[lastchance]

Thank-you @Chervil for managing to fathom out what was intended and rewriting the code so that it is possible to understand the algorithm.

Can I ask if it is strictly necessary to erase any of vec_a? Once you have found a minimum to push into vec_b, couldn't you just start the search for the next minimum at the next element of vec_a? Would the following code work?

#include <vector>
#include <iostream>
#include <algorithm>

int main()
{
    std::vector<int> vec_a;
    std::vector<int> vec_b;

    int count = 0;
    int input = 0;

    std::cout << "How many numbers? ";
    std::cin >> count;

    for (int g = 0; g<count; g++)
    {
        std::cin >> input;
        vec_a.push_back(input);
    }

    std::vector<int>::iterator biter = vec_a.begin();
    while (vec_a.end() - biter > 1)
    {
        biter = std::min_element(biter,vec_a.end());
        vec_b.push_back(*biter);
        biter++;
    }

    for (size_t g=0; g<vec_b.size(); g++)
    {
        std::cout << vec_b[g] << ' ';
    }

    std::cout << "\n Done \n";
}

My second question is for @Enot02. What is the purpose of this little algorithm?

With the line (from the corrected version by @chervil)
while (vec_a.size() > 1)
you always have the situation where a monotonically increasing sequence like

1 2 3 4 5 6

produces output which inevitably loses the last element:

1 2 3 4 5

Is this intended? It looks very unnatural. If you made the simple change to
while (vec_a.size() >= 1)
(that is, change "greater than" to "greater than or equal to") then the output would be

1 2 3 4 5 6

(and similarly for the while statement in my own code).

So my question boils down to: is there some purpose to this intriguing algorithm?

[Chervil]

@lastchance Thanks for this - I like your code rather better than what I came up with. Doing an erase operation on a vector is something which leaves me a little uneasy - in this case it is perfectly fine, but it can be inefficient when the size is large. Getting the result without the need to erase is a better approach.

For me, almost regardless of the problem, it isn't until I see the data that it starts to make sense. So it was here. With the example input and output it fell into place in terms of what the algorithm would be.