Compare element in a vector with elements in an array

I have two data structures with data in them.

  • One is a vector std::vector<int> presentStudents And other is a
  • char array char cAllowedStudents[256];

Now I have to compare these two such that checking every element in vector against the array such that all elements in the vector should be present in the array or else I will return false if there is an element in the vector that's not part of the array.

I want to know the most efficient and simple solution for doing this. I can convert my int vector into a char array and then compare one by one but that would be lengthy operation. Is there some better way of achieving this?

Answers


  1. Sort cAllowedstudents using std::sort.
  2. Iterate over the presentStudents and look for each student in the sorted cAllowedStudents using std::binary_search.
  3. If you don't find an item of the vector, return false.
  4. If all the elements of the vector are found, return true.

Here's a function:

bool check()
{
   // Assuming hou have access to cAllowedStudents
   // and presentStudents from the function.

   char* cend = cAllowedStudents+256;
   std::sort(cAllowedStudents, cend);

   std::vector<int>::iterator iter = presentStudents.begin();
   std::vector<int>::iterator end = presentStudents.end();
   for ( ; iter != end; ++iter )
   {
      if ( !(std::binary_search(cAllowedStudents, cend, *iter)) )
      {
         return false;
      }
   }
   return true;
}

Another way, using std::difference.

bool check()
{
   // Assuming hou have access to cAllowedStudents
   // and presentStudents from the function.

   char* cend = cAllowedStudents+256;
   std::sort(cAllowedStudents, cend);

   std::vector<int> diff;
   std::set_difference(presentStudents.begin(), presentStudents.end(),
                       cAllowedStudents, cend,
                       std::back_inserter(diff));
   return (diff.size() == 0);
}

I would suggest you use a hash map (std::unordered_map). Store all the elements of the char array in the hash map.

Then simply sequentially check each element in your vector whether it is present in the map or not in O(1).

Total time complexity O(N), extra space complexity O(N).

Note that you will have to enable C++11 in your compiler.


Please refer to function set_difference() in c++ algorithm header file. You can use this function directly, and check if result diff set is empty or not. If not empty return false.

A better solution would be adapting the implementation of set_difference(), like in here: http://en.cppreference.com/w/cpp/algorithm/set_difference, to return false immediately after you get first different element.

Example adaption:

while (first1 != last1)
{
    if (first2 == last2) 
        return false;

    if (*first1 < *first2)
    {
        return false;
    }
    else
    {
        if (*first2 == *first1)
        {
            ++first1;
        }
        ++first2;
    }
}
return true;

Sort both lists with std::sort and use std::find iteratively on the array.

EDIT: The trick is to use the previously found position as a start for the next search.

std::sort(begin(pS),end(pS))
std::sort(begin(aS),end(aS))

auto its=begin(aS);
auto ite=end(aS);

for (auto s:pS) {
    its=std::find(its,ite,s);
    if (its == ite) {
        std::cout << "Student not allowed" << std::cout;
        break;
    }
}

Edit: As legends mentiones, it usually might be more efficient to use binary search (as in R Sahu's answer). However, for small arrays and if the vector contains a significant fraction of students from the array (I'd say at least one tenths), the additional overhead of binary search might (or might not) outweight its asymptotic complexity benefits.


Need Your Help

Facebook Friends Request - Missing Friends

android facebook facebook-graph-api facebook-friends

I am requesting to get user friends from an Android App that I am developing. As from Facebook Api V2.0 I know that I should get only user friends that have already logged in through my App. However,

Javascript: How to add event via button to Outlook Calendar

javascript sharepoint outlook

I currently have a working vbscript implementation written: