Prev: implicit conversion: ctor or cast?
Next: where does it say non-modifying operations can't throw?
From: Guido on 22 Apr 2010 08:21
Hi,

I'm learning c++, I come from java/c# developing and I'm doing some c+
+ exercises. One of them is the implementation of a search algorithm,
merge sorting. Much problems come from the use of vector.
The code that I wrote give error when inserting data in the b vector
with the iterator {b.insert(it, a->at(j));} , and I don't understand
where the error come from. Someone can give me an hand? Furthermore,
are there some error or some "not to do" in the code?

Thanks for help. Regards.


#include <string>
#include <list>
#include <vector>
#include <iostream>
#include <cmath>
#include <istream>
#include <iterator>

void merge(std::vector<std::string>& list, int left, int center, int
right);
void mergesort(std::vector<std::string>& list, int left, int right);
void printVector(std::vector<std::string>& v);

void ex01() {

std::vector<std::string> v;

std::string input;
while (input != "quit") {
std::getline(std::cin, input);
v.push_back(input);
}

mergesort(v, 0, v.size());
printVector(v);

}

void printVector(std::vector<std::string>& v) {
std::vector<std::string>::iterator it;
for (it = v.begin(); it < v.end(); ++it) {
std::cout << *it << std::endl;
}

std::cout << "print end" << std::endl;

}

void merge(std::vector<std::string>& list, int left, int center, int
right) {
std::vector<std::string>* a = &list;

std::vector<std::string> b;
std::vector<std::string>::iterator it;

b.resize(a->size());
it = b.begin();

int i = left;
int j = center + 1;

while ((i <= center) && (j <= right)) {
if (a->at(i) <= a->at(j)) {
b.insert(it, a->at(i));
i = i + 1;
} else {
b.insert(it, a->at(j));
j = j + 1;
it++;
}
}

while (i <= center) {
b.insert(it, a->at(i));
i = i + 1;
it++;
}

while (j <= right) {
b.insert(it, a->at(j));
j = j + 1;
it++;
}

int k;
for (k = left; k <= right; ++k) {
a->at(k) = b.at(k - left);
}

}

void mergesort(std::vector<std::string>& list, int left, int right) {
std::vector<std::string>* a = &list;
printVector(*a);

if (left < right) {
int center = int(std::floor((left + right) / 2));
mergesort(*a, left, center);
mergesort(*a, center + 1, right);
merge(*a, left, center, right);
}

- Nascondi testo citato
- Mostra testo citato -
}

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Lailoken on 23 Apr 2010 08:28
On Apr 22, 4:21 pm, Guido <f8ki...(a)gmail.com> wrote:
> I'm learning c++, I come from java/c# developing and I'm doing some c+
> + exercises. One of them is the implementation of a search algorithm,
> merge sorting. Much problems come from the use of vector.
> The code that I wrote give error when inserting data in the b vector
> with the iterator {b.insert(it, a->at(j));} , and I don't understand
> where the error come from. Someone can give me an hand? Furthermore,
> are there some error or some "not to do" in the code?

Well, firstly, you already have list, not need to get it's address and
assign it to 'a'.

You can drop a altogether and just use the non-pointer type 'list'.
Instead of a->at(j) I would just use list[j] (seems simpler to me at
least)

Then to get to your problem, from what I can see you are inserting
into a vector 'b' for which you keep an iterator 'it'. And insertion
of items 'may' invalidate (and in your case probably does) the
iterator.

What you probably want to consider is using the return from the
insert() method:

See : http://www.cplusplus.com/reference/stl/vector/insert/

Thus I would do something like:

it = b.insert(it, list[i]);

to get a new valid iterator.

On the topic, I see you are mixing iterators and integer indexes. With
vectors I never really cared much either way but it may help with your
understanding if you chose integers for this specific problem. Later
work your way up to and understand all the different iterators and
where they are not just great to use, but almost also essential.

Also...

At one point you do an insert into 'b' without incrementing 'it'... is
this intentional?

If not, and your intention is to always add to the back of the vector,
I would drop 'it' totally and always use:

b.push_back(list[i]);

Hope this helps,
Me.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Lailoken on 23 Apr 2010 08:28
On Apr 22, 4:21 pm, Guido <f8ki...(a)gmail.com> wrote:
> Hi,
>
> I'm learning c++, I come from java/c# developing and I'm doing some c+
> + exercises. One of them is the implementation of a search algorithm,
> merge sorting. Much problems come from the use of vector.
> The code that I wrote give error when inserting data in the b vector
> with the iterator {b.insert(it, a->at(j));} , and I don't understand
> where the error come from. Someone can give me an hand? Furthermore,
> are there some error or some "not to do" in the code?
>
> Thanks for help. Regards.

Another avenue is to rather use StackOverflow web site as a resource
instead of usenet.

Try: http://stackoverflow.com/

Marius.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Daniel T. on 24 Apr 2010 02:57
Lailoken <lailoken(a)gmail.com> wrote:

> On Apr 22, 4:21 pm, Guido <f8ki...(a)gmail.com> wrote:
> > I'm learning c++, I come from java/c# developing and I'm doing some c+
> > + exercises. One of them is the implementation of a search algorithm,
> > merge sorting. Much problems come from the use of vector.
> > The code that I wrote give error when inserting data in the b vector
> > with the iterator {b.insert(it, a->at(j));} , and I don't understand
> > where the error come from. Someone can give me an hand? Furthermore,
> > are there some error or some "not to do" in the code?
>
> Well, firstly, you already have list, not need to get it's address and
> assign it to 'a'.
>
> You can drop a altogether and just use the non-pointer type 'list'.
> Instead of a->at(j) I would just use list[j] (seems simpler to me at
> least)
>
> Then to get to your problem, from what I can see you are inserting
> into a vector 'b' for which you keep an iterator 'it'. And insertion
> of items 'may' invalidate (and in your case probably does) the
> iterator.

I think his problem is more fundamental than that, and replacing the
call to 'at()' with an op[] would serve to hide the problem rather than
solve it.

To demonstrate what I mean, try using his merge with a vector of two
elements.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Daniel T. on 24 Apr 2010 02:57
Guido <f8kibis(a)gmail.com> wrote:

First let's get your merge fixed. It would be far easier if you didn't
do an in-place merge. For example an interface like this:

vector<string> merge(const vector<string>& left, const vector<string>&
right);

Yes, the above isn't as efficient, but it is a better learning exorcise.
Please consider it.

If you insist on doing an in-place merge, then start with a simple case:

int main() {
vector<string> v;
v.push_back("1");
v.push_back("2");
merge(v, 0, 1, 2);
printVector(v);
}

Write the simplest solution you can think of. Then go to the next case:

int main() {
vector<string> v;
v.push_back("1");
v.push_back("2");
merge(v, 0, 1, 2);
printVector(v);

v.clear();
v.push_back("2");
v.push_back("1");
merge(v, 0, 1, 2);
printVector(v);

}

Post your results and we can go from there.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 |  Next  |  Last
Pages: 1 2
Prev: implicit conversion: ctor or cast?
Next: where does it say non-modifying operations can't throw?