Velocity Reviews > C++ > help a newbie with vectors

# help a newbie with vectors

Kamran
Guest
Posts: n/a

 03-09-2005

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 ?

Kamran

Victor Bazarov
Guest
Posts: n/a

 03-09-2005
Kamran wrote:
> 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.

> [...]

Ron Natalie
Guest
Posts: n/a

 03-09-2005
Kamran wrote:

> 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).

Matt Bitten
Guest
Posts: n/a

 03-09-2005
Kamran wrote:
> 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
This means "not found", but you are interpreting it as a successful
find beyond the end of the list.

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"));
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"));
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.

Kamran
Guest
Posts: n/a

 03-09-2005
Ron Natalie wrote:
> Kamran wrote:
>
>> while (index != channels.end()) {
>> pos = find(index,channels.end(),string("SPB2_BHZ").c_str ()) -
>> channels.begin();

>
>
> The .c_str() here is silly.

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

>
>> cout << "pos: " << pos << endl;

>

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

Kamran
Guest
Posts: n/a

 03-09-2005
Matt Bitten wrote:
> Kamran wrote:
>
>>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"));
> 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"));
> 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

Mike Wahler
Guest
Posts: n/a

 03-09-2005
"Kamran" <(E-Mail Removed)> wrote in message
news:d0ne0u\$cv1\$(E-Mail Removed)...
>
>
> 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:stream& show_data(const std::vector<std::string>& d,
const std::string& prefix = "",
std:stream& os = std::cout)
{
os << prefix;

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

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

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

std::copy(r.begin(), r.end(),
std: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

Kamran
Guest
Posts: n/a

 03-10-2005
Mike Wahler wrote:
> "Kamran" <(E-Mail Removed)> wrote in message
> news:d0ne0u\$cv1\$(E-Mail Removed)...
>
>>
>>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:stream& show_data(const std::vector<std::string>& d,
> const std::string& prefix = "",
> std:stream& os = std::cout)
> {
> os << prefix;
>
> if(d.size())
> std::copy(d.begin(), d.end(),
> std:stream_iterator<std::string>(os, "\n"));
> else
> os << "(No data)\n";
>
> os.put('\n');
> return os;
> }
>
>
> std:stream&
> show_report(const std::vector<std::vector<std::string>::size_type>& r,
> const std::string& value,
> std:stream& os = std::cout)
> {
> if(!r.empty())
> os << "Value '" << value << "' found at following indices:\n";
>
> std::copy(r.begin(), r.end(),
> std: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

Howard
Guest
Posts: n/a

 03-10-2005

"Kamran" <(E-Mail Removed)> wrote in message
news:d0orbe\$1ar\$(E-Mail Removed)...

<snip!>

>
>
> 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
-Howard

Mike Wahler
Guest
Posts: n/a

 03-10-2005
"Kamran" <(E-Mail Removed)> wrote in message
news:d0orbe\$1ar\$(E-Mail Removed)...
> Mike Wahler wrote:

[snip]

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

[snip]

>> std::copy(d.begin(), d.end(),
>> std: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