C++ - Check if One Array of Strings Contains All Elements of Another

Question

I've recently been porting a Python application to C++, but am now at a loss as to how I can port a specific function. Here's the corresponding Python code:

def foo(a, b): # Where `a' is a list of strings, as is `b'
    for x in a:
        if not x in b:
            return False

    return True

I wish to have a similar function:

bool
foo (char* a[], char* b[])
{
    // ...
}

What's the easiest way to do this? I've tried working with the STL algorithms, but can't seem to get them to work. For example, I currently have this (using the glib types):

gboolean
foo (gchar* a[], gchar* b[])
{
    gboolean result;

    std::sort (a, (a + (sizeof (a) / sizeof (*a))); // The second argument corresponds to the size of the array.
    std::sort (b, (b + (sizeof (b) / sizeof (*b)));

    result = std::includes (b, (b + (sizeof (b) / sizeof (*b))),
                            a, (a + (sizeof (a) / sizeof (*a))));

    return result;
}

I'm more than willing to use features of C++11.

Answer 1

A naive transcription of the python version would be:

bool foo(std::vector<std::string> const &a,std::vector<std::string> const &b) {
    for(auto &s : a)
        if(end(b) == std::find(begin(b),end(b),s))
            return false;
    return true; 
}

---

It turns out that sorting the input is very slow. (And wrong in the face of duplicate elements.) Even the naive function is generally much faster. Just goes to show again that premature optimization is the root of all evil.

Here's an unordered_set version that is usually somewhat faster than the naive version (or was for the values/usage patterns I tested):

bool foo(std::vector<std::string> const& a,std::unordered_set<std::string> const& b) {
    for(auto &s:a)
        if(b.count(s) < 1)
            return false;
    return true;
}

On the other hand, if the vectors are already sorted and b is relatively small ( less than around 200k for me ) then std::includes is very fast. So if you care about speed you just have to optimize for the data and usage pattern you're actually dealing with.

Answer 2

I'm just going to add a few comments to what others have stressed and give a better algorithm for what you want.

Do not use pointers here. Using pointers doesn't make it c++, it makes it bad coding. If you have a book that taught you c++ this way, throw it out. Just because a language has a feature, does not mean it is proper to use it anywhere you can. If you want to become a professional programmer, you need to learn to use the appropriate parts of your languages for any given action. When you need a data structure, use the one appropriate to your activity. Pointers aren't data structures, they are reference types used when you need an object with state lifetime - i.e. when an object is created on one asynchronous event and destroyed on another. If an object lives it's lifetime without any asynchronous wait, it can be modeled as a stack object and should be. Pointers should never be exposed to application code without being wrapped in an object, because standard operations (like new) throw exceptions, and pointers do not clean themselves up. In other words, pointers should always be used only inside classes and only when necessary to respond with dynamic created objects to external events to the class (which may be asynchronous).

Do not use arrays here. Arrays are simple homogeneous collection data types of stack lifetime of size known at compiletime. They are not meant for iteration. If you need an object that allows iteration, there are types that have built in facilities for this. To do it with an array, though, means you are keeping track of a size variable external to the array. It also means you are enforcing external to the array that the iteration will not extend past the last element using a newly formed condition each iteration (note this is different than just managing size - it is managing an invariant, the reason you make classes in the first place). You do not get to reuse standard algorithms, are fighting decay-to-pointer, and generally are making brittle code. Arrays are (again) useful only if they are encapsulated and used where the only requirement is random access into a simple type, without iteration.

Do not sort a vector here. This one is just odd, because it is not a good translation from your original problem, and I'm not sure where it came from. Don't optimise early, but don't pessimise early by choosing a bad algorithm either. The requirement here is to look for each string inside another collection of strings. A sorted vector is an invariant (so, again, think something that needs to be encapsulated) - you can use existing classes from libraries like boost or roll your own. However, a little bit better on average is to use a hash table. With amortised O(N) lookup (with N the size of a lookup string - remember it's amortised O(1) number of hash-compares, and for strings this O(N)), a natural first way to translate "look up a string" is to make an unordered_set<string> be your b in the algorithm. This changes the complexity of the algorithm from O(NM log P) (with N now the average size of strings in a, M the size of collection a and P the size of collection b), to O(NM). If the collection b grows large, this can be quite a savings.

In other words

gboolean foo(vector<string> const& a, unordered_set<string> const& b)

Note, you can now pass constant to the function. If you build your collections with their use in mind, then you often have potential extra savings down the line.

The point with this response is that you really should never get in the habit of writing code like that posted. It is a shame that there are a few really (really) bad books out there that teach coding with strings like this, and it is a real shame because there is no need to ever have code look that horrible. It fosters the idea that c++ is a tough language, when it has some really nice abstractions that do this easier and with better performance than many standard idioms in other languages. An example of a good book that teaches you how to use the power of the language up front, so you don't build bad habits, is "Accelerated C++" by Koenig and Moo.

But also, you should always think about the points made here, independent of the language you are using. You should never try to enforce invariants outside of encapsulation - that was the biggest source of savings of reuse found in Object Oriented Design. And you should always choose your data structures appropriate for their actual use. And whenever possible, use the power of the language you are using to your advantage, to keep you from having to reinvent the wheel. C++ already has string management and compare built in, it already has efficient lookup data structures. It has the power to make many tasks that you can describe simply coded simply, if you give the problem a little thought.

Answer 3

Your first problem is related to the way arrays are (not) handled in C++. Arrays live a kind of very fragile shadow existence where, if you as much as look at them in a funny way, they are converted into pointers. Your function doesn't take two pointers-to-arrays as you expect. It takes two pointers to pointers.

In other words, you lose all information about the size of the arrays. sizeof(a) doesn't give you the size of the array. It gives you the size of a pointer to a pointer.

So you have two options: the quick and dirty ad-hoc solution is to pass the array sizes explicitly:

gboolean foo (gchar** a, int a_size, gchar** b, int b_size)

Alternatively, and much nicer, you can use vectors instead of arrays:

gboolean foo (const std::vector<gchar*>& a, const std::vector<gchar*>& b)

Vectors are dynamically sized arrays, and as such, they know their size. a.size() will give you the number of elements in a vector. But they also have two convenient member functions, begin() and end(), designed to work with the standard library algorithms.

So, to sort a vector:

std::sort(a.begin(), a.end());

And likewise for std::includes.

Your second problem is that you don't operate on strings, but on char pointers. In other words, std::sort will sort by pointer address, rather than by string contents.

Again, you have two options:

If you insist on using char pointers instead of strings, you can specify a custom comparer for std::sort (using a lambda because you mentioned you were ok with them in a comment)

std::sort(a.begin(), a.end(), [](gchar* lhs, gchar* rhs) { return strcmp(lhs, rhs) < 0; });

Likewise, std::includes takes an optional fifth parameter used to compare elements. The same lambda could be used there.

Alternatively, you simply use std::string instead of your char pointers. Then the default comparer works:

gboolean
foo (const std::vector<std::string>& a, const std::vector<std::string>& b)
{
    gboolean result;

    std::sort (a.begin(), a.end());
    std::sort (b.begin(), b.end());

    result = std::includes (b.begin(), b.end(),
                            a.begin(), a.end());

    return result;
}

Simpler, cleaner and safer.

Answer 4

In your sample snippet your use of std::includes is pointless since it will use operator< to compare your elements. Unless you are storing the same pointers in both your arrays the operation will not yield the result you are looking for.

Comparing adresses is not the same thing as comparing the true content of your c-style-strings.

---

You'll also have to supply std::sort with the neccessary comparator, preferrably std::strcmp (wrapped in a functor).

It's currently suffering from the same problem as your use of std::includes, it's comparing addresses instead of the contents of your c-style-strings.

---

This whole "problem" could have been avoided by using std::strings and std::vectors.

---

Example snippet

#include <iostream>
#include <algorithm>
#include <cstring>

typedef char gchar;

gchar const * a1[5] = {
  "hello", "world", "stack", "overflow", "internet"
};

gchar const * a2[] = {
  "world", "internet", "hello"
};

...

int
main (int argc, char *argv[])
{
  auto Sorter = [](gchar const* lhs, gchar const* rhs) {
    return std::strcmp (lhs, rhs) < 0 ? true : false;
  };

  std::sort (a1, a1 + 5, Sorter);
  std::sort (a2, a2 + 3, Sorter);

  if (std::includes (a1, a1 + 5, a2, a2 + 3, Sorter)) {
    std::cerr << "all elements in a2  was   found in a1!\n";
  } else {
    std::cerr << "all elements in a2 wasn't found in a1!\n";
  }
}

output

all elements in a2  was   found in a1!

Answer 5

The sort in the C++ version isn't working because it's sorting the pointer values (comparing them with std::less as it does with everything else). You can get around this by supplying a proper comparison functor. But why aren't you actually using std::string in the C++ code? The Python strings are real strings, so it makes sense to port them as real strings.