find / find_first_of - vector of pairs..

Discussion in 'C++' started by ma740988, Jan 2, 2006.

  1. ma740988

    ma740988 Guest

    Oh what fun it is to get acclimated with the various containers and
    algorithms.. I'm trying to determine if I could use find/find_first_of
    algorithms to achieve the same object of a for loop when searching for
    the first element in a vector of pairs. So now:

    typedef std::pair<int, int > int_pair;
    typedef std::vector<int_pair> vec_int_pair;
    int main()
    {
    vec_int_pair p;
    p.push_back(std::make_pair( 5, 6));
    p.push_back(std::make_pair( 5, 7));

    for (vec_int_pair::iterator it = p.begin();
    it != p.end();
    ++it)
    {
    if (it->first = 5)
    p.erase(it);
    }

    // now lets try the same thing with find and/or find_first_of

    //it = find ( p.begin(), p.end(), 5); -- 1
    //it = find_first_of ( p.begin(), p.end(), 5); -- 2

    // validate that we only have 5, 7
    cout << p.size() << endl;
    for (vec_int_pair::iterator it = p.begin();
    it != p.end();
    ++it)
    {
    cout << it->first << endl;
    cout << it->second << endl;
    }
    }

    The lines marked --1 and --2 are of interest. My guess is I would
    need a function object, but I'm not sure if that even makes sense?
    Sample source greatly appreaciated.

    Thanks.
    ma740988, Jan 2, 2006
    #1
    1. Advertising

  2. ma740988 wrote:
    > typedef std::pair<int, int > int_pair;
    > typedef std::vector<int_pair> vec_int_pair;
    > int main()
    > {
    > vec_int_pair p;
    > p.push_back(std::make_pair( 5, 6));
    > p.push_back(std::make_pair( 5, 7));
    >
    > for (vec_int_pair::iterator it = p.begin();
    > it != p.end();
    > ++it)
    > {
    > if (it->first = 5)

    shouldn't this be ==? (Yeah, I know, a typo.)
    > p.erase(it);


    all iterators get invalidated after an erase. Hence, this for loop
    might produce an unexpected / undefined behavior.

    > }
    >
    > // now lets try the same thing with find and/or find_first_of
    >
    > //it = find ( p.begin(), p.end(), 5); -- 1
    > //it = find_first_of ( p.begin(), p.end(), 5); -- 2
    >
    > // validate that we only have 5, 7
    > cout << p.size() << endl;
    > for (vec_int_pair::iterator it = p.begin();
    > it != p.end();
    > ++it)
    > {
    > cout << it->first << endl;
    > cout << it->second << endl;
    > }
    > }
    >
    > The lines marked --1 and --2 are of interest. My guess is I would
    > need a function object, but I'm not sure if that even makes sense?
    > Sample source greatly appreaciated.


    You need a function object

    class Foo {
    int i;
    public:
    Foo(int j) : i(j) { }
    bool operator()(std::pair<int, int> p)
    {
    return i==p.first;
    }

    };

    And then use find_if

    p.erase(find_if ( p.begin(), p.end(), Foo(5)) );

    As an aside, if the sequence of the pairs in the vector doesnot matter,
    you can use std::multimap.

    int main()
    {
    std::multimap<int, int> p;
    p.insert(std::make_pair( 5, 6));
    p.insert(std::make_pair( 5, 7));
    p.insert(std::make_pair( 4, 7));
    p.erase(p.find(5));
    cout << p.size() << endl;

    for (std::multimap<int,int>::iterator it = p.begin();
    it != p.end();
    ++it)
    {
    cout << it->first << endl;
    cout << it->second << endl;
    }

    }
    Neelesh Bodas, Jan 2, 2006
    #2
    1. Advertising

  3. ma740988

    Zara Guest

    On 1 Jan 2006 21:26:20 -0800, "ma740988" <> wrote:

    >
    >Oh what fun it is to get acclimated with the various containers and
    >algorithms.. I'm trying to determine if I could use find/find_first_of
    >algorithms to achieve the same object of a for loop when searching for
    >the first element in a vector of pairs. So now:

    <snip>

    You may create your own pair, to fit this search:

    #include <iostream>
    #include <vector>

    struct int_pair:std::pair<int,int>
    {
    public:
    int_pair(int a,int b):std::pair<int,int>(a,b) {}

    public:
    bool operator==(int n) {return first==n;} // Search criterion
    };

    typedef std::vector<int_pair> vec_int_pair;

    int main()
    {
    vec_int_pair p;
    p.push_back(int_pair( 5, 6));
    p.push_back(int_pair( 5, 7));

    vec_int_pair::iterator it = std::find ( p.begin(), p.end(), 5);
    if (it!=p.end())
    {
    std::cout << "Found!" << std::endl;
    std::cout << it->first << std::endl;
    std::cout << it->second << std::endl;
    }

    }


    Best regards,

    -- Zara
    Zara, Jan 2, 2006
    #3
  4. ma740988

    ma740988 Guest

    ||shouldn't this be ==? (Yeah, I know, a typo.)
    Sure is :). I caught that after transmitting the message.

    Thank you both.
    If I wanted support for - say a 'combination' of primitive types .. i.e
    int, int - double, int - char, float - etc.
    A templated solution is the answer. Correct? i.e ..

    template <typename T>
    class Foo2 {
    T i;
    public:
    Foo2(int j) : i(j) { }
    bool operator()(std::pair<T, T> p)
    {
    return i==p.first;
    }
    };

    Haven't touched the compiler thus far today, but I suspect the compiler
    will 'flag' the user if the user desired to do something bogus. For
    instance.
    typedef unsigned char* ADDRESS_TYPE;
    struct my_struct { ADDRESS_TYPE adt; unsigned int sz; };
    std::pair < my_struct, int > my_pair;

    An STL container holding 'my_pair' - I'm thinking shouldn't work.

    Thanks!!
    -- MP


    --------------------------------------------------------------------------------------------------------
    For real convolution the Fourier transform of the convolution is the
    product of the transforms of the two functions being convolved.
    The question, then, is what happens for complex convolution.
    ma740988, Jan 2, 2006
    #4
  5. ma740988 wrote:

    > If I wanted support for - say a 'combination' of primitive types .. i.e
    > int, int - double, int - char, float - etc.
    > A templated solution is the answer. Correct? i.e ..
    >
    > template <typename T>


    to have combinations like int-char or int-float etc you need two
    template parameters

    template<class T, class U>
    > class Foo2 {
    > T i;
    > public:
    > Foo2(int j) : i(j) { }

    Foo2(T j) i(j) { }

    > bool operator()(std::pair<T, T> p)

    bool operator()(std::pair<T, U> p)

    > {
    > return i==p.first;
    > }
    > };
    >
    > Haven't touched the compiler thus far today, but I suspect the compiler
    > will 'flag' the user if the user desired to do something bogus. For
    > instance.
    > typedef unsigned char* ADDRESS_TYPE;
    > struct my_struct { ADDRESS_TYPE adt; unsigned int sz; };
    > std::pair < my_struct, int > my_pair;
    >

    This will give errors if operator<< is not overloaded for my_struct or
    if operator== is not defined on my_struct. Otherwise it should work
    fine.
    Neelesh Bodas, Jan 2, 2006
    #5
  6. ma740988

    ma740988 Guest

    ||This will give errors if operator<< is not overloaded for
    || my_struct or if operator== is not defined on my_struct.

    Trying to put together a complete example here so i could get my head
    around this. I overload operator << for the stream
    but I dont believe that's what I want here.

    typedef unsigned char* ADDRESS_TYPE;
    struct my_struct {
    ADDRESS_TYPE adt; unsigned int sz;
    my_struct(unsigned int size) : sz(size) {}
    my_struct& operator=(my_struct& ms) // four basic things. self
    assign check/delete if pointers/allocate / return.
    {
    if (this == &ms)
    return *this;
    delete [] adt;
    adt = new unsigned char[sz]; //allocate memory
    return *this;
    }
    friend std::eek:stream& operator<< // for cout .. wont
    work with the find algo - i dont think..
    ( std::eek:stream& Out, const my_struct& rhs )
    {
    return Out << rhs.adt;
    }
    };

    // later
    int main() {} // soon to come.

    Help thanks...

    One other thing. The text (Eckel - Chapter 7, Generic Container - pg
    464) I'm reading suggest that inserting and erasing elements in the
    middle of a vector using an iterator is a bad idea. From the looks of
    the sample program and my understanding of the words, 'bad idea'
    amounts to re-allocation. The program - in a nutshell:
    1. reserved space for 11 elements.
    2. inserted 10 elements.
    3. Found the middle via an iterator - Inserted an additional element
    4. erased the element in the middle (using the iteator in 3 which has
    since been invalidated).

    Besides, the error in 4. i.e using an iterator that has been
    invalidated (obviously a bad idea). The words below the program
    highlights the implications surrounding reservation for 10 elements as
    opposed to 11. Obviously if 10 elements were reserved initially.
    Insertion of a new element results in - re-location .. Oops!!

    In any event, my question is this: In order for the vector to maintain
    it's linear array. Each call to erase results in a call to 'operator='.
    Period!! Correct?


    ---------------------------------------------------------------------------------------------
    For real convolution the Fourier transform of the convolution is the
    product of the transforms of the two functions being convolved.
    The question, then, is what happens for complex convolution.
    ma740988, Jan 3, 2006
    #6
  7. ma740988 wrote:
    >> my_struct& operator=(my_struct& ms) // four basic things. self


    You have overloaded assignment operator. Note that you need to provide
    operator==() (the eqaulity testing operator) so that find_if works.
    Once you provide that, your code will work properly. I tried it and it
    worked. The sample 'main' function that I used is -

    typedef std::pair < my_struct, int > my_pair;
    typedef std::vector<my_pair> vec_my_pair;
    int main()
    {
    my_struct z(10);
    vec_my_pair p;
    p.push_back(std::make_pair(z, 6));
    p.push_back(std::make_pair(z, 7));
    p.push_back(std::make_pair(z, 9));
    p.push_back(std::make_pair(z, 10));

    p.erase(std::find_if(p.begin(),p.end(),Foo2<my_struct,int>(z)));

    for (vec_my_pair::iterator it = p.begin(); it != p.end(); ++it)
    {
    cout << it->first << endl; // uses operator<< overloaded for
    my_struct
    cout << it->second << endl;
    }
    }

    > One other thing. The text (Eckel - Chapter 7, Generic Container - pg
    > 464) I'm reading suggest that inserting and erasing elements in the
    > middle of a vector using an iterator is a bad idea. From the looks of
    > the sample program and my understanding of the words, 'bad idea'
    > amounts to re-allocation.


    Not necessarily. Insertion of an element in the middle of a vector
    results into displacement (relocation) of the elements present after
    the insertion point. Re-allocation occurs if the capacity needs to be
    increased, not otherwise.

    > In any event, my question is this: In order for the vector to maintain
    > it's linear array. Each call to erase results in a call to 'operator='.
    > Period!! Correct?


    The standard doesnot give any rules for the implementation - it simply
    mentions the pre and post conditions and complexity of the algorithm.
    Further, the standard containers require the elements to be assignable,
    and hence a call to erase should have no problems in calling
    operator=() on the elements.

    Hope this helps.
    Neelesh Bodas, Jan 3, 2006
    #7
    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. Christopher

    std::string.find_first_of()

    Christopher, Apr 26, 2004, in forum: C++
    Replies:
    4
    Views:
    5,688
    Dave Moore
    Apr 26, 2004
  2. Replies:
    1
    Views:
    370
    Alf P. Steinbach
    Feb 17, 2006
  3. Replies:
    8
    Views:
    1,915
    Csaba
    Feb 18, 2006
  4. scottys0
    Replies:
    2
    Views:
    390
    scottys0
    Mar 4, 2006
  5. Replies:
    3
    Views:
    383
    =?iso-8859-1?q?Erik_Wikstr=F6m?=
    Jan 8, 2007
Loading...

Share This Page