find an object in a vector of object by data member value, delete the object

[LMHmedchem]

Hello,

This is an operation I have performed more often in a map, since I often store objects in a map container if I want to retrieve them by searching on a name.

In this case I have a vector of objects,

class row_data {

public:

   // initialize class data members
   row_data() : index(0), id(0), distance_to_centroid(0.0), row_name("") { }

   unsigned int index, id;
   double distance_to_centroid;
   string row_name;
   vector<string> input_string_data;
   vector<double> point_coordinates;

};

vector<row_data> rows_data

I need to find the object with a specific .row_name value (there will be only one in the vector) and delete that object from the vector. I can do something like a loop,

// find the position of an object in a vector of object by a passed string value
// delete the object from the vector using erase
void remove_object(const string &search_string, vector<row_data> &search_vector) {

   // location of object to erase
   unsigned int item_location

   // search vector for member variable name
   // break from for loop when item is found
   for(unsigned int i=0; i<search_vector.size(); i++) {
      if(search_vector[i].row_name == search_string) { unsigned int item_location = i; break; }
   }

   // erase the object at the identified location
   search_vector.erase(search_vector.begin() + item_location);

return;
}

Though I think this would work, I see some drawbacks. This is hard coded for the data member .row_name, so it's not very reusable. The for loop and break is a bit kludgy and it seems like find or find_if would be more robust. I am also not sure that I am erasing the correct object with search_vector.begin() + item_location.

Similar things I have done before used pointers and iterators with find_if, but I'm not sure how to do that searching a vector of objects instead of a vector of primitives.

Are there any suggestions? Thanks.

LMHmedchem

[laserlight]

Similar things I have done before used pointers and iterators with find_if, but I'm not sure how to do that searching a vector of objects instead of a vector of primitives.

It is the same idea either way, e.g.,

void remove_object(const string &search_string, vector<row_data> &search_vector) {
    auto found = std::find_if(
        search_vector.begin(),
        search_vector.end(),
        [&](const row_data& obj) { return obj.row_name == search_string; }
    );
    if (found != search_vector.end()) {
        search_vector.erase(found);
    }
}

[LMHmedchem]

It is the same idea either way, e.g.,

void remove_object(const string &search_string, vector<row_data> &search_vector) {
    auto found = std::find_if(
        search_vector.begin(),
        search_vector.end(),
        [&](const row_data& obj) { return obj.row_name == search_string; }
    );
    if (found != search_vector.end()) {
        search_vector.erase(found);
    }
}

Thanks for the post. I am not using c++11, so I don't think I can use auto to declare found. What type is found? Find_if returns an iterator, so if I explicitly declare found, would it look like,

void remove_object(const string &search_string, vector<row_data> &search_vector) {

   // iterator to matching object
   vector<row_data>::iterator found;

   // search vector with find_if
   found = std::find_if( search_vector.begin(),
                         search_vector.end(),
                         [&](const row_data& obj) { return obj.row_name == search_string; } );

   // remove object if found
   if (found != search_vector.end()) { search_vector.erase(found); }

return;
}

Since I am not using c++11, I can't use the lamda. I think I need to create a separate bool function to do the evaluation, [&](const row_data& obj) { return obj.row_name == search_string; }. Maybe something like,

bool check_name(const row_data &row_object, const string &search_string) {
   return row_object.row_name == search_string;
}

This doesn't look right because there is no way to substitute check_name() for the lamda you wrote since my function needs a specific object to operate on. Every example I have seen of this includes the custom equality operator in the class definition.

LMHmedchem

[laserlight]

You would create a function object, e.g.,

class CheckName
{
public:
    explicit CheckName(const std::string& name) : search_string(name) {}

    bool operator()(const row_data& obj) const
    {
        return obj.row_name == search_string;
    }
private:
    std::string search_string;
};

void remove_object(const string& search_string, vector<row_data>& search_vector) {
    vector<row_data>::iterator found = std::find_if(
        search_vector.begin(),
        search_vector.end(),
        CheckName(search_string)
    );
    if (found != search_vector.end()) {
        search_vector.erase(found);
    }
}

[AvDav]

And of course the type of raw_data can be substituted with a template class and / or function to perform the task. This could easily eliminate the usage of redundant code.

[AvDav]

On the other hand, the solution placed above would pretty well suited for this particular case.

[2kaud]

This is hard coded for the data member .row_name, so it's not very reusable

It's not easily possible to specify the name of the data member to be used - this has to be hard coded unless a pointer to a member operator is used. See https://msdn.microsoft.com/en-us/library/k8336763.aspx. Note that these add complexity to the code and are rarely used. However the type of this member can be defined using templated code as mentioned by AvDav in post #5

[wolle]

Are there any suggestions?

I have modified laserlight's solution using function pointers and the so called erase-remove idiom. (The latter was suggested also by laserlight in another thread.) It should be robust and efficient since it is an established idiom. Note that it removes all matching objects, not just the first found.

https://en.wikipedia.org/wiki/Erase%...93remove_idiom

I have factored out the critical types out of CheckName and remove_object turning them into templates. I have also introduced getter functions in row_data because I wanted functions rather than naked data (and in addition this increases encapsulation slightly).

The solution is quite flexible and general I think (and can be made even more so). The drawback possibly is the strange syntax of function pointers that takes a while getting used to.

class row_data {
public:
	row_data(double distance_to_centroid, const std::string& row_name) : dtc(distance_to_centroid), rn(row_name) {}

	double distance_to_centroid() const {return dtc;}
	std::string row_name() const {return rn;}

private:
	double dtc;
	std::string rn;
};


template <typename C, typename T>
class CheckName {
public:
	CheckName(T (C::*fptr)() const, const T& name) : function_ptr(fptr), search_val(name) {}

	bool operator()(const C& obj) const	{
		return (obj.*function_ptr)() == search_val;
	}

private:
	T (C::*function_ptr)() const;
	T search_val;
};

template <typename C, typename T>
void remove_object(T (C::*function_ptr) () const, const T& search_val, std::vector<C>& search_vector) {
	search_vector.erase(std::remove_if( // the erase-remove idiom
		search_vector.begin(), 
		search_vector.end(), 
		CheckName<C, T>(function_ptr, search_val)), 
		search_vector.end()
	);
}

void print(std::vector<row_data>& sv) {
	for (std::size_t i = 0; i < sv.size(); ++i) {
		std::cout << "{" << sv[i].distance_to_centroid() << "," << sv[i].row_name() << "} ";
	}
	std::cout << std::endl;
}

void test() {
	std::vector<row_data> sv;

	sv.push_back(row_data(1.0, "one"));
	sv.push_back(row_data(2.0, "two"));
	sv.push_back(row_data(3.0, "three"));
	sv.push_back(row_data(4.0, "four"));
	sv.push_back(row_data(5.0, "five"));
	sv.push_back(row_data(3.0, "second three"));
	print(sv);
		// first remove all "two"-objects based on equality with row_data::row_name()
	remove_object<row_data, std::string>(&row_data::row_name, "two", sv); 
	print(sv);
		// then remove all 3.0-objects based on equality with row_data::distance_to_centroid()
	remove_object<row_data, double>(&row_data::distance_to_centroid, 3.0, sv);
	print(sv);
}

[2kaud]

The for loop and break is a bit kludgy and it seems like find or find_if would be more robust. I am also not sure that I am erasing the correct object with search_vector.begin() + item_location.

Going back to the original code as posted in post #1, a simple c++98 re-working would be

void remove_object(const string &search_string, vector<row_data> &search_vector)
{
    for (vector<row_data>::iterator row_iter = search_vector.begin(); row_iter != search_vector.end(); ++row_iter)
        if (row_iter->row_name == search_string) {
            search_vector.erase(row_iter);
            break;
        }

    return;
}

This is the simple c++98 code for erasing the first occurrence of search_string in the vector. I don't know how large search_vector is, but as search_vector is stated to only occur once (if it occurs), why continue to search the vector once the item has been found? IMO there is a balance between having simple code that is easy to understand/maintain and more complex generalised code.

[wolle]

Going back to the original code as posted in post #1, a simple c++98 re-working would be

void remove_object(const string &search_string, vector<row_data> &search_vector)
{
    for (vector<row_data>::iterator row_iter = search_vector.begin(); row_iter != search_vector.end(); ++row_iter)
        if (row_iter->row_name == search_string) {
            search_vector.erase(row_iter);
            break;
        }

    return;
}

This is the simple c++98 code for erasing the first occurrence of search_string in the vector. I don't know how large search_vector is, but as search_vector is stated to only occur once (if it occurs), why continue to search the vector once the item has been found? IMO there is a balance between having simple code that is easy to understand/maintain and more complex generalised code.

Well, the OP mentioned lack of reusability as a drawback hence my suggestion (in #8) to use function pointers.

Surprisingly the erase-remove idiom I suggested is almost as efficient as your "simple" algorithm. Even though your algoritm stops looking for matches when the first match is found, both algoritms need to erase the found object and that's an expensive operation on a vector. All objects after the found object must be shifted to close the gap left by the removed object. To avoid this one must either use a list container or accept that the object order of the vector changes. In the latter case one simply uses the last object to overwrite the found object. That's just one shift rather than shifting all remaining objects.

I agree that the erase-remove idiom is less transparent than your "simple" solution. But it is an established idiom indeed and only marginally slower. I think it's a feasible alternative to consider if you prefer functional iteration over explicit iteration.

[2kaud]

True, but I was also making the general point re trade-off between simple code that is easy to understand/test/maintain and more complex generalised code (eg using function pointers etc). Where this balance is, is for the developers to determine. The performance may be similar, but the other factors also come into play.

to erase the found object and that's an expensive operation on a vector

Yes. That's why, as wolle pointed out, using a vector is not always the correct container to use if direct element addressing is not required - although it is usually the most popular!

object order of the vector changes. In the latter case one simply uses the last object to overwrite the found object. That's just one shift rather than shifting all remaining objects

Unless the vector order is required to be maintained in a particular order, then overwriting the found object with a copy of the last element and then erasing the last element actually involves no shifting at all - as the size of the vector is simply reduced by 1. This is the efficiency of the erase-remove idiom as no data shifting is involved. Consider

void remove_object(const string &search_string, vector<row_data> &search_vector)
{
	for (vector<row_data>::iterator row_iter = search_vector.begin(); row_iter != search_vector.end(); ++row_iter)
		if (row_iter->row_name == search_string) {
			swap(row_iter->index, search_vector.back().index);
			swap(row_iter->id, search_vector.back().id);
			swap(row_iter->distance_to_centroid, search_vector.back().distance_to_centroid);
			swap(row_iter->row_name, search_vector.back().row_name);
			row_iter->input_string_data.swap(search_vector.back().input_string_data);
			row_iter->point_coordinates.swap(search_vector.back().point_coordinates);

			search_vector.erase(search_vector.end() - 1);
			break;
		}

	return;
}

This also avoids the overhead of copying the two vectors within row_data.

[wolle]

Consider

void remove_object(const string &search_string, vector<row_data> &search_vector)
{
	for (vector<row_data>::iterator row_iter = search_vector.begin(); row_iter != search_vector.end(); ++row_iter)
		if (row_iter->row_name == search_string) {
			swap(row_iter->index, search_vector.back().index);
			swap(row_iter->id, search_vector.back().id);
			swap(row_iter->distance_to_centroid, search_vector.back().distance_to_centroid);
			swap(row_iter->row_name, search_vector.back().row_name);
			row_iter->input_string_data.swap(search_vector.back().input_string_data);
			row_iter->point_coordinates.swap(search_vector.back().point_coordinates);

			search_vector.erase(search_vector.end() - 1);
			break;
		}

	return;
}

This also avoids the overhead of copying the two vectors within row_data.

That overhead can be prevented by holding the row_data objects by pointer. Also then you don't have to modify remove_object each time data fields are added to or removed from row_data.

Furthermore, what if you want to remove row_data objects based on some other field than row_name? Introducing one remove_object function for each field? Or what if you want to remove other kind of objects from a vector. Introducing even more remove_object functions?

I'm getting more and more convinced that function pointers (my post #8) is a pretty good idea. And if the objects are costly to copy, holding them by pointer probably is a good thing. This is for C++ 98 of course. With C++ 11 we have lambda expressions, move semantics and smart pointers so it's a different ballgame all together.

[2kaud]

With C++ 11 we have lambda expressions, move semantics and smart pointers so it's a different ballgame all together.

Yes. In a previous thread I'd already queried re upgrading to at least a c++11 compiler but this option currently isn't viable.