to compare sub-items in vector

Question

Overview of problem : I am using std::vector to hold objects of Subject. Now this vector contains lots of objects( with lots I mean 10-20 objects at max) .

These objects have string member values like category and sub_category.

Both category and sub_category can have string which can be same of other objects's sub_category & category.

Issue: Now I want my std::vector to have only those objects whose's sub_category are unique. If category is not unique that's not a problem .

Secondly if we found 2 objects having same sub_category then we have to delete one of them from the vector. we will delete it based on some rules example

Rules for deleting are if
i) instance of Subject ->category = " Land " OR if category = "Jungle" then delete other duplicate object ,
ii) if above condition doesn't match then delete either of them.

I am wondering , how would I compare the sub-items from the vector . For example

I have class say Subject

class Subject
{
public :
// some constructors,
// functions to get ., set category and sub category
   std::String get_sub_category()   
   std::string get_category();

 private:
   std::string category;
  std::string sub_category;
}

I have vector which stores object of Subjects. example

vector<Subject> sub_vec;

Now what I want is to delete the object from vector that has same sub_category I am not looking for source code buT i need a starting point,? example

say

    sub_vec[0] = Animal  object that has sub_category Tiger
    sub_vec [1] = Animal object   with Lion as sub category 
    sub_vec[2] = Forest object with sub_category Tiger

so what I want is to based on some conditions(which I can do ) remove either Forest or Animal object containing Tiger. But for that how would I do comparison?

Thanks everyone for the help. I have written the function and have checked it but I am sure there is a room for hell lot of improvement. May you guys please pin out out my pitfalls.

 std::vector< Subject >copy_vector; // copy_vector conatins all the objects of SUbject with redundant sub_category


  for( std::vector< Subject >::iterator ii = copy_vector.begin() ; ii != copy_vector.end() ; ++ii )
  {
      sub_category = ii->get_sub_category();

      std::cout <<" sub_category-- in main for loop " << sub_category  << std::endl ;
      std::vector< Subject >::iterator it = ii+1;
      while( it != copy_vector.end() )
      {
            std::cout <<" the  size of copy _vector is = " << copy_vector.size() << std::endl ; // for debug purpose
          if( it->get_sub_category() == sub_category )
          {
              std::cout <<" we got a match here" << std::endl ;
              // since both are duplicate , we have to delete one of them. Rules for deleting  are if 
              i) instance of Subject ->category = " Land " OR if category = "Jungle"   then delete other duplicate object , 
              ii) if above condition doesn't match then delete either of them.

              if( ( it->get_category == "Land" ) || (  it->get_category == "Jungle" )  )
              {
                 std::cout <<" we are deleting it reference value  " << std::endl ;
                 it =  copy_vector.erase(ii);

                 // increment the counter 
                 ++ii;
              }
              else if( ( ii->get_category == "Land" ) || (  ii->get_category == "Jungle" )  )
              {
                 std::cout <<" we are deleting from copy_vector  " << std::endl ;
                 it =  copy_vector.erase(it);
              }

              else
              {
                     std::cout <<" we are deleting from copy_vector  when there is no match for rules " << std::endl ;
                      it =  copy_vector.erase(it);
              }
              std::cout <<" the size of copy _vector is = " << copy_vector.size() << std::endl ;

          }
          else
          {
              std::cout <<" No Match" << std::endl;
              // increase main iterator 
              if( it != copy_vector.end() )
             {
                     ++it;
             }
          }
      }

  }
  //print value
    for( std::vector< Subject >::iterator ii = copy_vector.begin() ; ii != copy_vector.end() ; ++ii )
    {

        std::cout <<" New list = " << ii->get_category <<" \t " << ii->get_sub_category() << std::endl;
    } 

Answer 1

Your solution has time complexity O(n*n) but the problem can be solved with complexity O(n*log(n)) or even O(n).

First, let's define such category comparison function (if a category is "Land" or "Jungle" then it's greater then other categories):

bool CategoryLess(string sCategory1, string sCategory2){
    return sCategory1 != "Land" && sCategory1 != "Jungle"
        && (sCategory2 == "Land" || sCategory2 == "Jungle");
}

Now iterate through the vector and store all found subcategories and corresponding Subjects in a std::unordered_map (or std::map in if you don't use C++11). If the subcategory is already in the map then replace corresponding Subject if the category of the already found Subject less then category of the new Subject:

unordered_map<string, Subject*> Subcategories;

for (int i=0; i<sub_vec.size(); ++i){
    unordered_map<string, Subject*>::iterator
        it = Subcategories.find(sub_vec[i].get_sub_category());  

    if (it != Subcategories.end()){
        if (CategoryLess((*it)->get_category(), sub_vec[i].get_category())
            it->second = &sub_vec[i];
    }
    else
        Subcategories[sub_vec[i].get_sub_category()] = &sub_vec[i];
}

Now you have the map of all subcategories and corresponding Subjects.
If we found two or more Subjects with the same subcategory then the map contains a pointer to the Subject with greater category.

Now iterate sub_vec once more and delete Subjects if

Subcategories[sub_vec[i].get_sub_category()] != &sub_vec[i];

Time complexity:
If we use std::unordered_map then expected time complexity is O(n) for the both cycles (O(n*n) in worst case).
If we use std::map then time complexity is O(n*log(n)) for the both cycles.

(I didn't take into account time complexities of string comparison and vector.erase as irrelevant)

Please note than when you delete a Subject from the vector, the addresses of other Subjects can be changed. So you need to take care when compare pointers to Subjects (for example copy needed Subjects to another vector instead of deleting other Subjects from the vector). But it doesn't change the general idea of my solution.

Answer 2

One way to do it is by using remove_if. To check if an object has a duplicate sub_category you can use a function or functor that stores the subcategories it finds in a set or an unordered_map and the remove all objects where its sub_category already exists in the set/unordered_map.

Note, unordered_map is only available in c++11.

Answer 3

You could try to use BOOST_FOREACH to iterate thru vector elements

I'm doing something similar like this :

BOOST_FOREACH( Subject f, sub_vec )
{
    ///TODO: do your filtering here 
    if(f.sub_category == "<bla bla>")
}

What I like about using BOOST_FOREACH is that it makes very readable code and when you are dealing with many vector elements and many filtering possibilities, then that is certainly a factor to consider

Answer 4

Either you should use a lambda expression or define a functional object.

An example with using a lambda expression

#include <vector>
#include <string>
#include <algorithm>

// ...

std:string tiger = "Tiger";

sub_vec.erase( std::remove_if( sub_vec.begin(), sub_vec.end(), 
                               [&]( const Subject &s ) { return ( s.sub_category == tiger ); } ),
               sub_vec.end() ); 

Take into account that the code above removes all obexts that have sub_category equal to "Tiger". If you need to remove only duplicates then at first you should find the first object of the sub category and then remove all other objects with the same subcategory. In this case the code could look as

#include <vector>
#include <string>
#include <algorithm>

// ...

std:string tiger = "Tiger";

auto equal_sb_category = [&]( const Subject &s ) { return ( s.sub_category == tiger ); };

auto it = std::find_if( sub_vec.begin(), sub_vec.end(), equal_sb_category );

if ( it != sub_vec.end() )
{
    sub_vec.erase( std::remove_if( std::next( it ), sub_vec.end(), equal_sb_category ),
                   sub_vec.end() ); 
}