3

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?

Improve this question
2
  • Are the collections sorted? What is the length of the char array, we know the size of 256. Commented Jun 10, 2014 at 6:29
  • Although I provided the answer which I personally believe is most efficient in your case, there is one general thing I'd like to mention: While efficiency is always good when it comes for free, it should be at the very bottom of your priority list if this is really only about 256 students. As long as this function is not called inside a huge loop, I believe code clarity and maintainability should be much more important in this case. Commented Jun 10, 2014 at 7:44

5 Answers 5

Reset to default
1

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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;
Improve this answer

Comments

0
  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);
}
Improve this answer

12 Comments

why not use something like std::set_difference?
@billz std::set_difference would work too. It will do the same computation but will also create another container.
@R Sahu: Correct me if I'm wrong, but binary_serach doesn't return an iterator, but a boolean. So the comparison with cend should not be necessary.
@billz: I like the set::difference version as it is very compact. What I don't like about set_difference however, is that (as far as the standard is concerned) it doesn't use the (in-)equality operator but uses the less operator two times. Do you know if this is optimized away in actual implementations?
@maven what i meant was that if yoz have copied the solution you had to make the array available inside the function check(). Did Ou do this by making the aray a global varable or by passing it as a parameter to check?
|
0

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.

Improve this answer

3 Comments

That would be inefficient, isn't it? Why use std::find when the they are sorted?
The array might be a superset of the numbers in the vector. Also you can start the search woth the position of the last found element. This way you achieve linear complexety after the lists are sorted.
@legends2k but i admit, for such a short list, a simple bruteforce search for all elements might be even more efficient
-1

Using C++11. In your case, size is 256. Note that I personally have not tested this, or even put it into a compiler. It should, however, give you a good idea of what to do yourself. I HIGHLY recommend testing the edge cases with this! 

#include <algorithm>

bool check(const std::vector<int>& studs, 
char* allowed, 
unsigned int size){

    for(auto x : studs){
        if(std::find(allowed, allowed+size-1, x) == allowed+size-1 && x!= *(allowed+size))
            return false;
    }
    return true;
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.