help a newbie with vectors

K

Kamran

I am a newbie in C++ and having a lot of problems with vectors.
I have a "vector <string> channels" and this may contain
several copies of the same string. I need to find the indices
of all the occurances of that particular string in "channels".
this is the code that is supposed to do the job:

---------------
vector<string>::iterator index;
index = channels.begin();
while (index != channels.end()) {
pos = find(index,channels.end(),string("SPB2_BHZ").c_str()) -
channels.begin();
cout << "pos: " << pos << endl;
if (pos != channels.size()) {
cout << "pos " << pos << " ncopy " << ncopy << endl;
indices[ncopy++] = pos;
}
++index;

}

--------------

If there is only one occurance of "SPB2_BHZ" and it is at position 9 I
get 20 different hits:

pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9

which is 19 too many. I also get 11 hits at position 21 which is
the size of the vector !!! If there are more occurances of the string
I get a mess.
I suspect substraction of "channels.begin()" in the find statement
is the culprit but don't know how to do it.
Does anyone know how to do this ?

Thanks in advance

Kamran
 
V

Victor Bazarov

Kamran said:
I am a newbie in C++ and having a lot of problems with vectors.

You're having problems with your algorithm, and not with vectors.
Write down the pseudo-code for your search, then convert it to C++.
Then post _both_ and let's see what's wrong.

At this point it is unclear whether you have a wrong algorithm, or
you have no idea how to translate it into C++, or you simply made
a mistake typing your C++ up.

And try to post a complete test program next time. The data in which
you're searching would definitely help.
 
R

Ron Natalie

Kamran said:
while (index != channels.end()) {
pos = find(index,channels.end(),string("SPB2_BHZ").c_str()) -
channels.begin();

The .c_str() here is silly.
cout << "pos: " << pos << endl;
You print this unconditionaly each time through the loop.
So it prints 20 times.

I also suspect that rather than
++ index;

you want to really do index += pos; (or similar logic using the
return from find).
 
M

Matt Bitten

Kamran said:
I am a newbie in C++ and having a lot of problems with vectors.

I usually prefer the approach of earlier posters: lead someone
to an answer. But I feel like just giving answers away today.
So here is a general critique of your code:

vector<string>::iterator index;
index = channels.begin();
while(index != channels.end()) {
// Loop body here
++index;
}

There is nothing wrong with the above loop, but it really is a "for"
loop in disguise. Why not write it as one? You can also put the
iterator inside the scope of the loop, to avoid name conflicts with
other variables. Lastly, since you are not using the iterator to
modify the container, make it a const_iterator:

for(vector<string>::const_iterator index = channels.begin();
index != channels.end();
++index) {
// Loop body here
}

Second, converting your string literal to a string object and then
back to a (char *) is a bit odd. Leave off the ".c_str()".

Now for the actual errors. You are using "find" incorrectly. It
takes a range and a value. It finds the first occurrence of the
value in the range, and returns an iterator to it. Or it returns
the end of the range if nothing was found.

You are doing multiple finds on nearly the same range, so of course
you find the same thing over and over again. And when your range
shrinks enough that the item is not found, find returns .end().
This means "not found", but you are interpreting it as a successful
find beyond the end of the list.

Instead, do your first find starting at the beginning. Then do
your next find starting at the position after the result of the
previous find. And so on. Stop when find returns channels.end().
Like this:

vector<string>::const_iterator finditer = channels.begin();
while(true) {
finditer = find(finditer, channels.end(), string("SPB2_BHZ"));
if(finditer == channels.end()) break; // Not found
size_t pos = finditer - channels.begin();
cout << "pos: " << pos << endl;
indices[ncopy++] = pos;
++finditer; // Next find starts just after result of this one
}

One more minor note: It can be inefficient to call the .end()
member function over and over. This varies by container, and for
a vector it is hardly an issue. However, it is not a bad idea
to get in the habit of doing things like this:

vector<string>::const_iterator finditer = channels.begin();
const vector<string>::const_iterator endmark = channels.end();
while(true) {
finditer = find(finditer, endmark, string("SPB2_BHZ"));
if(finditer == endmark) break; // Not found
size_t pos = finditer - channels.begin();
cout << "pos: " << pos << endl;
indices[ncopy++] = pos;
++finditer; // Next find starts just after result of this one
}

And of course you can convert that to a "for" loop, if you want.
 
K

Kamran

Ron said:
The .c_str() here is silly.

Thanks.
Forgot to remove that. Used to be a variable there. Sorry.

Yes, that was left from debugging. But I still have 8 too many.
You print this unconditionaly each time through the loop.
So it prints 20 times.

I also suspect that rather than
++ index;

Then how do I move forward ?
you want to really do index += pos; (or similar logic using the
return from find).

Same problem. I get too many hits.

Kamran
 
K

Kamran

Matt said:
Kamran said:
I am a newbie in C++ and having a lot of problems with vectors.


I usually prefer the approach of earlier posters: lead someone
to an answer. But I feel like just giving answers away today.
So here is a general critique of your code:

vector<string>::iterator index;
index = channels.begin();
while(index != channels.end()) {
// Loop body here
++index;
}

There is nothing wrong with the above loop, but it really is a "for"
loop in disguise. Why not write it as one? You can also put the
iterator inside the scope of the loop, to avoid name conflicts with
other variables. Lastly, since you are not using the iterator to
modify the container, make it a const_iterator:

for(vector<string>::const_iterator index = channels.begin();
index != channels.end();
++index) {
// Loop body here
}

Second, converting your string literal to a string object and then
back to a (char *) is a bit odd. Leave off the ".c_str()".

Now for the actual errors. You are using "find" incorrectly. It
takes a range and a value. It finds the first occurrence of the
value in the range, and returns an iterator to it. Or it returns
the end of the range if nothing was found.

You are doing multiple finds on nearly the same range, so of course
you find the same thing over and over again. And when your range
shrinks enough that the item is not found, find returns .end().
This means "not found", but you are interpreting it as a successful
find beyond the end of the list.

Instead, do your first find starting at the beginning. Then do
your next find starting at the position after the result of the
previous find. And so on. Stop when find returns channels.end().
Like this:

vector<string>::const_iterator finditer = channels.begin();
while(true) {
finditer = find(finditer, channels.end(), string("SPB2_BHZ"));
if(finditer == channels.end()) break; // Not found
size_t pos = finditer - channels.begin();
cout << "pos: " << pos << endl;
indices[ncopy++] = pos;
++finditer; // Next find starts just after result of this one
}

One more minor note: It can be inefficient to call the .end()
member function over and over. This varies by container, and for
a vector it is hardly an issue. However, it is not a bad idea
to get in the habit of doing things like this:

vector<string>::const_iterator finditer = channels.begin();
const vector<string>::const_iterator endmark = channels.end();
while(true) {
finditer = find(finditer, endmark, string("SPB2_BHZ"));
if(finditer == endmark) break; // Not found
size_t pos = finditer - channels.begin();
cout << "pos: " << pos << endl;
indices[ncopy++] = pos;
++finditer; // Next find starts just after result of this one
}

And of course you can convert that to a "for" loop, if you want.

Thanks a lot. I guess it was my lucky day :)
Hope you feel this way everyday :)

Thanks again

Kamran
 
M

Mike Wahler

Kamran said:
I am a newbie in C++ and having a lot of problems with vectors.
I have a "vector <string> channels" and this may contain
several copies of the same string. I need to find the indices
of all the occurances of that particular string in "channels".
this is the code that is supposed to do the job:

---------------
vector<string>::iterator index;
index = channels.begin();
while (index != channels.end()) {
pos = find(index,channels.end(),string("SPB2_BHZ").c_str()) -
channels.begin();
cout << "pos: " << pos << endl;
if (pos != channels.size()) {
cout << "pos " << pos << " ncopy " << ncopy << endl;
indices[ncopy++] = pos;
}
++index;

}

--------------

If there is only one occurance of "SPB2_BHZ" and it is at position 9 I
get 20 different hits:

pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9

which is 19 too many. I also get 11 hits at position 21 which is
the size of the vector !!! If there are more occurances of the string
I get a mess.
I suspect substraction of "channels.begin()" in the find statement
is the culprit but don't know how to do it.
Does anyone know how to do this ?

#include <algorithm>
#include <iostream>
#include <ostream>
#include <string>
#include <vector>

const std::vector<std::vector<std::string>::size_type>&
report_dups(const std::vector<std::string>& input,
std::vector<std::vector<std::string>::size_type>& output,
const std::string& value)
{
std::vector<std::string>::const_iterator it(input.begin());
std::vector<std::string>::const_iterator bg(input.begin());
std::vector<std::string>::const_iterator en(input.end());

output.clear();

while(it != en)
if((it = std::find(it, en, value)) != en)
output.push_back(it++ - bg);

return output;
}

std::eek:stream& show_data(const std::vector<std::string>& d,
const std::string& prefix = "",
std::eek:stream& os = std::cout)
{
os << prefix;

if(d.size())
std::copy(d.begin(), d.end(),
std::eek:stream_iterator<std::string>(os, "\n"));
else
os << "(No data)\n";

os.put('\n');
return os;
}


std::eek:stream&
show_report(const std::vector<std::vector<std::string>::size_type>& r,
const std::string& value,
std::eek:stream& os = std::cout)
{
if(!r.empty())
os << "Value '" << value << "' found at following indices:\n";

std::copy(r.begin(), r.end(),
std::eek:stream_iterator
<std::vector<std::string>::size_type>(os, "\n"));

os << "\nFound " << r.size() << " occurrences of value '"
<< value << "'\n";

return os;
}

int main()
{
std::vector<std::string> data;
std::vector<std::vector<std::string>::size_type> report;

data.push_back("B");
data.push_back("X");
data.push_back("Y");
data.push_back("Z");
data.push_back("A");
data.push_back("B");
data.push_back("C");
data.push_back("A");
data.push_back("B");
data.push_back("C");
data.push_back("A");
data.push_back("B");
data.push_back("C");
data.push_back("B");

show_data(data, "Data:\n");
std::string to_find("B");

show_report(report_dups(data, report, to_find), to_find);
return 0;
}


Output:

Data:
B
X
Y
Z
A
B
C
A
B
C
A
B
C
B

Value 'B' found at following indices:
0
5
8
11
13

Found 5 occurrences of value 'B'


-Mike
 
K

Kamran

Mike said:
I am a newbie in C++ and having a lot of problems with vectors.
I have a "vector <string> channels" and this may contain
several copies of the same string. I need to find the indices
of all the occurances of that particular string in "channels".
this is the code that is supposed to do the job:

---------------
vector<string>::iterator index;
index = channels.begin();
while (index != channels.end()) {
pos = find(index,channels.end(),string("SPB2_BHZ").c_str()) -
channels.begin();
cout << "pos: " << pos << endl;
if (pos != channels.size()) {
cout << "pos " << pos << " ncopy " << ncopy << endl;
indices[ncopy++] = pos;
}
++index;

}

--------------

If there is only one occurance of "SPB2_BHZ" and it is at position 9 I
get 20 different hits:

pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9
pos 9

which is 19 too many. I also get 11 hits at position 21 which is
the size of the vector !!! If there are more occurances of the string
I get a mess.
I suspect substraction of "channels.begin()" in the find statement
is the culprit but don't know how to do it.
Does anyone know how to do this ?


#include <algorithm>
#include <iostream>
#include <ostream>
#include <string>
#include <vector>

const std::vector<std::vector<std::string>::size_type>&
report_dups(const std::vector<std::string>& input,
std::vector<std::vector<std::string>::size_type>& output,
const std::string& value)
{
std::vector<std::string>::const_iterator it(input.begin());
std::vector<std::string>::const_iterator bg(input.begin());
std::vector<std::string>::const_iterator en(input.end());

output.clear();

while(it != en)
if((it = std::find(it, en, value)) != en)
output.push_back(it++ - bg);

return output;
}

std::eek:stream& show_data(const std::vector<std::string>& d,
const std::string& prefix = "",
std::eek:stream& os = std::cout)
{
os << prefix;

if(d.size())
std::copy(d.begin(), d.end(),
std::eek:stream_iterator<std::string>(os, "\n"));
else
os << "(No data)\n";

os.put('\n');
return os;
}


std::eek:stream&
show_report(const std::vector<std::vector<std::string>::size_type>& r,
const std::string& value,
std::eek:stream& os = std::cout)
{
if(!r.empty())
os << "Value '" << value << "' found at following indices:\n";

std::copy(r.begin(), r.end(),
std::eek:stream_iterator
<std::vector<std::string>::size_type>(os, "\n"));

os << "\nFound " << r.size() << " occurrences of value '"
<< value << "'\n";

return os;
}

int main()
{
std::vector<std::string> data;
std::vector<std::vector<std::string>::size_type> report;

data.push_back("B");
data.push_back("X");
data.push_back("Y");
data.push_back("Z");
data.push_back("A");
data.push_back("B");
data.push_back("C");
data.push_back("A");
data.push_back("B");
data.push_back("C");
data.push_back("A");
data.push_back("B");
data.push_back("C");
data.push_back("B");

show_data(data, "Data:\n");
std::string to_find("B");

show_report(report_dups(data, report, to_find), to_find);
return 0;
}


Output:

Data:
B
X
Y
Z
A
B
C
A
B
C
A
B
C
B

Value 'B' found at following indices:
0
5
8
11
13

Found 5 occurrences of value 'B'


-Mike


Thanking you frantically :)

Kamran
 
H

Howard

Thanking you frantically :)

Kamran

I was scrolling frantically to get to the end of that! :) It would be
helpful to others if you'd trim out portions of previous posts you're
responding to (as I've done above), if that info is no longer important to
your response. Thanks...
-Howard
 
M

Mike Wahler

Kamran said:
Mike Wahler wrote:
[snip]
#include <algorithm>
#include <iostream>
#include <ostream>
#include <string>
#include <vector>
[snip]
std::copy(d.begin(), d.end(),
std::eek:stream_iterator<std::string>(os, "\n"));
[snip]



Thanking you frantically :)

You're welcome. :)

But I just realized that my code is missing one item (my
compiler let me get away with it, but it's technically needed
to be correct): The 'ostream_iterator' type needs:

#include <iterator>

-Mike
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,900
Latest member
Nell636132

Latest Threads

Top