help a newbie with vectors

Discussion in 'C++' started by Kamran, Mar 9, 2005.

  1. Kamran

    Kamran Guest

    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
     
    Kamran, Mar 9, 2005
    #1
    1. Advertising

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

    > [...]
     
    Victor Bazarov, Mar 9, 2005
    #2
    1. Advertising

  3. Kamran

    Ron Natalie Guest

    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).
     
    Ron Natalie, Mar 9, 2005
    #3
  4. Kamran

    Matt Bitten Guest

    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"));
    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.
     
    Matt Bitten, Mar 9, 2005
    #4
  5. Kamran

    Kamran Guest

    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, Mar 9, 2005
    #5
  6. Kamran

    Kamran Guest

    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"));
    > 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
     
    Kamran, Mar 9, 2005
    #6
  7. Kamran

    Mike Wahler Guest

    "Kamran" <> wrote in message
    news:d0ne0u$cv1$...
    >
    >
    > 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
     
    Mike Wahler, Mar 9, 2005
    #7
  8. Kamran

    Kamran Guest

    Mike Wahler wrote:
    > "Kamran" <> wrote in message
    > news:d0ne0u$cv1$...
    >
    >>
    >>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
     
    Kamran, Mar 10, 2005
    #8
  9. Kamran

    Howard Guest

    "Kamran" <> wrote in message
    news:d0orbe$1ar$...

    <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
    your response. Thanks...
    -Howard
     
    Howard, Mar 10, 2005
    #9
  10. Kamran

    Mike Wahler Guest

    Re: [corr] help a newbie with vectors

    "Kamran" <> wrote in message
    news:d0orbe$1ar$...
    > 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
     
    Mike Wahler, Mar 10, 2005
    #10
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    5
    Views:
    869
    info_
    Mar 28, 2005
  2. kelvSYC
    Replies:
    1
    Views:
    707
    Axter
    May 18, 2005
  3. Manuel
    Replies:
    6
    Views:
    311
    Manuel
    Dec 26, 2005
  4. Replies:
    3
    Views:
    725
    Shadowman
    Mar 26, 2008
  5. Guest
    Replies:
    0
    Views:
    481
    Guest
    Sep 14, 2005
Loading...

Share This Page