find / find_first_of - vector of pairs..

[ma740988]

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.

[Neelesh Bodas]

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<i nt, int> p;
p.insert(std::m ake_pair( 5, 6));
p.insert(std::m ake_pair( 5, 7));
p.insert(std::m ake_pair( 4, 7));
p.erase(p.find( 5));
cout << p.size() << endl;

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

}

[Zara]

On 1 Jan 2006 21:26:20 -0800, "ma740988" <ma******@gmail .com> 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::p air<int,int>
{
public:
int_pair(int a,int b):std::pair<in t,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::i terator 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

[ma740988]

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

[Neelesh Bodas]

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.

[ma740988]

||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(unsig ned int size) : sz(size) {}
my_struct& operator=(my_st ruct& 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.

[Neelesh Bodas]

ma740988 wrote:

my_struct& operator=(my_st ruct& 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::fi nd_if(p.begin() ,p.end(),Foo2<m y_struct,int>(z )));

for (vec_my_pair::i terator 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.