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:air<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]

typedef std:air<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:air<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;
}

}

 

[Zara]

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:air<int,int>
{
public:
int_pair(int a,int b):std:air<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

 

[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:air<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:air < my_struct, int > my_pair;

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

Thanks!!
-- MP

 

[Neelesh Bodas]

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

class Foo2 {
T i;
public:
Foo2(int j) : i(j) { }

Foo2(T j) i(j) { }

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

 

[Neelesh Bodas]

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