find / find_first_of - vector of pairs..

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.

re: find / find_first_of - vector of pairs..

ma740988 wrote:[color=blue]
> 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)[/color]
shouldn't this be ==? (Yeah, I know, a typo.)[color=blue]
> p.erase(it);[/color]

all iterators get invalidated after an erase. Hence, this for loop
might produce an unexpected / undefined behavior.
[color=blue]
> }
>
> // 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.[/color]

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;
}

}

re: find / find_first_of - vector of pairs..

On 1 Jan 2006 21:26:20 -0800, "ma740988" <ma740988@gmail.com> wrote:
[color=blue]
>
>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:[/color]
<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

re: find / find_first_of - vector of pairs..

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

re: find / find_first_of - vector of pairs..

ma740988 wrote:
[color=blue]
> 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>[/color]

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

template<class T, class U>[color=blue]
> class Foo2 {
> T i;
> public:
> Foo2(int j) : i(j) { }[/color]
Foo2(T j) i(j) { }
[color=blue]
> bool operator()(std::pair<T, T> p)[/color]
bool operator()(std::pair<T, U> p)
[color=blue]
> {
> 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;
>[/color]
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.

re: find / find_first_of - vector of pairs..

||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::ostream& operator<< // for cout .. wont
work with the find algo - i dont think..
( std::ostream& 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.

re: find / find_first_of - vector of pairs..

ma740988 wrote:[color=blue][color=green]
>> my_struct& operator=(my_struct& ms) // four basic things. self[/color][/color]

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_str uct,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;
}
}
[color=blue]
> 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.[/color]

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.
[color=blue]
> 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?[/color]

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.