C++: check if vector<Class> is subset of vector<Class>

Question

I have the following piece of code. I have two strings (k1, k2), which I break into tokens by using the whitespace delimeter (t1, t2). Then I want to check if t1 is contained in t2. Problem is that even with isSubset(t1, t1) I get a 0 value returned. I want to avoid using a vector<string> instead of vector<StringRef>, if possible. What am I doing wrong? Output should be two 1's but I get two 0's instead.

#include<string>
#include<iostream>
#include <time.h>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

class StringRef
{
    private:
        char const*     begin_;
        int             size_;

    public:
        int size() const { return size_; }
        char const* begin() const { return begin_; }
        char const* end() const { return begin_ + size_; }

        std::string toString() {
             std::string value(begin_);
             return value;
        }

        StringRef( char const* const begin, int const size )
            : begin_( begin )
            , size_( size )
        {}

        bool operator<(const StringRef& s) const
        {
            return (strcmp(begin(), s.begin()) < 0);
        }
};


/************************************************
 * Checks if vector B is subset of vector A    *
 ************************************************/
bool isSubset(std::vector<StringRef> A, std::vector<StringRef> B)
{
    std::sort(A.begin(), A.end());
    std::sort(B.begin(), B.end());
    return std::includes(A.begin(), A.end(), B.begin(), B.end());
}


/************************************************
 * Split string using delimeter; returns vector *
 ************************************************/
vector<StringRef> split3( string const& str, char delimiter = ' ' )
{
    vector<StringRef>   result;

    enum State { inSpace, inToken };

    State state = inSpace;
    char const*     pTokenBegin = 0;    // Init to satisfy compiler.
    for( auto it = str.begin(); it != str.end(); ++it )
    {
        State const newState = (*it == delimiter? inSpace : inToken);
        if( newState != state )
        {
            switch( newState )
            {
            case inSpace:
                result.push_back( StringRef( pTokenBegin, &*it - pTokenBegin ) );
                break;
            case inToken:
                pTokenBegin = &*it;
            }
        }
        state = newState;
    }
    if( state == inToken )
    {
        result.push_back( StringRef( pTokenBegin, &str.back() - pTokenBegin ) );
    }
    return result;
}

int main()
{

    string k1 = "9 10";
    string k2 = "9 10 2 3";
    vector<StringRef> t1 = split3(k1,' ');
    vector<StringRef> t2 = split3(k2,' ');

    cout<<isSubset(t1,t1)<<endl;
    cout<<isSubset(t2,t1)<<endl;
    return 0;
}

EDIT: ------ CORRECTIONS -------

Changed toString to:

std::string toString() const {
    std::string value(begin_, size_);
    return value;
}

Changed operator< to: (thanks to @Mike Seymour)

bool operator<(const StringRef& s) const
{
    return (std::lexicographical_compare(begin(), end(), s.begin(), s.end()));
}

Finally, in split3, changed the if block before the return statement to:

if( state == inToken )
{
    result.push_back( StringRef( pTokenBegin, &str.back() + 1 - pTokenBegin ) );
}

Answer 1

There are issues in this code.

result.push_back( StringRef( pTokenBegin, &str.back() - pTokenBegin ) );

contains an off-by-one error, so the size of the last token is always too short.

return (strcmp(begin(), s.begin()) < 0);

and

std::string value(begin_);

rely on \0 terminated C strings, but you are not using \0 terminated C strings.

std::string toString() {

should be a const method.

After I resolved all of these issue, the code worked.

Answer 2

Fortunately c++11 makes all these "view of" shenanigans unnecessary.

std::reference_wrapper provides a copyable reference (pointer-like object that can't be null).

All you need to do is provide an overload of whichever operators you need in the std:: namespace.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>


using ConstStringRef = std::reference_wrapper<const std::string>;

namespace std {
    bool operator<(const reference_wrapper<const string>& l, const reference_wrapper<const string>& r)
    {
        return l.get() < r.get();
    }
}

using namespace std;

int main()
{

    std::string a { "hello a" };
    std::string b { "hello b" };
    const std::string c { "hello c" };

    std::vector<ConstStringRef> views { c, b, a };
    cout << "initial" << endl;
    std::copy(begin(views), end(views), std::ostream_iterator<std::string>(std::cout, ", "));
    std::cout << std::endl;

    // sort using lambda
    std::sort(begin(views), end(views), [](const ConstStringRef&r1, const ConstStringRef&r2 ) { return r1.get() < r2.get(); });
    cout << "sorted using lambda" << endl;
    std::copy(begin(views), end(views), std::ostream_iterator<std::string>(std::cout, ", "));
    std::cout << std::endl;

    reverse(begin(views), end(views));
    cout << "reversed" << endl;
    std::copy(begin(views), end(views), std::ostream_iterator<std::string>(std::cout, ", "));
    std::cout << std::endl;

    std::sort(begin(views), end(views));
    cout << "sorted using operator<" << endl;
    std::copy(begin(views), end(views), std::ostream_iterator<std::string>(std::cout, ", "));
    std::cout << std::endl;

    return 0;
}

output:

initial
hello c, hello b, hello a, 
sorted using lambda
hello a, hello b, hello c, 
reversed
hello c, hello b, hello a, 
sorted using operator<
hello a, hello b, hello c, 

Answer 3

Try printing out the contents of t1 and t2, you'll see your split3 function isn't working:

{9 10, 10}
{9 10 2 3, 10 2 3, 2 3, 3}

Also, your StringRef::toString() function is broken, and as Mike points out your operator< is broken (even after you fixed it to use < not <=).

What am I doing wrong?

Instead of writing a complete program then staring at it wondering why the final result is wrong, try testing each piece of the program and check it actually does what you think it does.

You have several mistakes in this program, to find them all you need to check each piece in isolation and fix each problem. Trying to fix all of them at once will just be confusing because you won't be able to see which of the many errors is the cause of the unexpected results.