How to find item using multiple search values in c++?

Question

Conceptually my data represents a table like this one

+-------+------+------+------+------+  
|  ID   | Val1 | Val2 | Val3 | Val4 |  
+-------+------+------+------+------+  
| Name1 | a    | b    | c    | d    |  
| Name2 | a    | b    | c    | e    |  
| Name3 | h    | b    | c    | d    |  
| Name4 | i    | j    | k    | l    |  
+-------+------+------+------+------+  

Currently I am free to choose how that data will be stored. Essentially I have IDs with some values, which are assigned to the IDs. A set of values is unique to the ID (no set will be repeated for another ID). Individual values can be repeated across IDs.

Now, what I need to do in C++ is to find the name by using a set of Values. So essentially something like this:

std::string findID(char val1, char val2, char val3, char val4)
{
    //Do something to find the corresponding Name

    return result;
}

I am currently a bit bumbed on how to go about this. I thought about using a map with tuples, but providing a hash function for the tuples seems like overcomplicating the problem. So basically like described here: Using tuple in unordered_map

Is there a simpler solution that I just seem to overlook?

Answer 1

If all values are characters, I think you'd better transform each line of your table into strings and provide a hash table for the couple ID/stringID. When you get 5 values as char to test you then just have to concat them and run your search.

Answer 2

Yes, the easiest way is to store a mapping from a tuple of values to a name. If your values are chars, however, it's the easiest to simply use string for that, and pack everything into std::unordered_map<std::string, std::string>, the key being all values packed into the string, and the value your name.

If your values aren't chars, it's still not that complex. Instead of using a tuple, you might just use a structure:

struct Key {
    std::array<Value, n> vals;
};

And then provide std::hash instance that'd fold the array with boost::hash_combine:

class KeyHash  {
    std::size_t operator()(Key const& k)
    {
        std::size_t h = 42;
        for (Value const& v : k.vals) {
            boost::hash_combine(h, v);
        }
        return h;
    }
};

The question you've linked and the presented solution aren't bad either, though, and are generic enough to be put into some reusable library.

Answer 3

It appears that you have a 1 to many relationship in your data table, knowing that we can create a simple class that represents an arbitrary row. From there we can create another simple class that takes a row from its constructor and it also has an addRow method to add additional rows. There are no limits on the rows. The table is confined to the size of the first row passed in. So if row1 has 3 elements and is passed into table1's constructor, every other row that is added to this instantiated table must be of the same types and size. These sets of classes are template for both the ID & Types. Here are the basic declarations - definitions of these classes' structures.

template<class ID, class Type>
class TableRow {
private:
    ID id_;
    std::vector<Type> values_;

public:
    template<class... Params>
    TableRow( const ID& id, Params&&... valuePack ) :
        id_( id ),
        values_ { std::forward<Params>( valuePack )... }
    {}

    ID getID() const {
        return id_;
    }

    std::vector<Type> getValues() const {
        return values_;
    }

    std::size_t getSize() const {
        return values_.size();
    }

};

template<class ID, class Type>
class Table {
private:
    std::size_t rowSize_;
    std::vector<TableRow<ID, Type>> table_;

public:
    explicit Table( TableRow<ID, Type> row ) {
        table_.push_back( row );
        rowSize_ = row.getSize();
    }

    void addRow( TableRow<ID, Type> row ) {
        // Check to see if row's size == our table's first index size
        if ( row.getSize() == rowSize_ ) {
            // This row's size is a match and this row of data is compatabile with our current table
            table_.push_back( row );
        } else {
            std::ostringstream strStream;
            strStream << __FUNCTION__ << " row passed in does not match size of this table's row size." << std::endl;
            throw std::exception( strStream.str().c_str() );
        }
    }

    // methods to retrieve a row, an id, or a specific element to an id, 
    // comparison operators, ostream friend operators etc. here...
};

And here is an example of instantiating them...

int main() {

    try {
        std::string id = std::string( "John" );
        std::string val1 = std::string( "a" ), val2 = std::string( "b" );
        std::string val3 = std::string( "c" ), val4 = std::string( "d" );
        TableRow<std::string, std::string> tr1 { id, val1, val2, val3, val4 };

        Table<std::string, std::string> table( tr1 );

        TableRow<std::string, std::string> tr2( "Mike", "e", "f", "g", "h" );
        table.addRow( tr2 );

        TableRow<std::string, std::string> tr3( "Susan", "a", "b", "c" );
        //table.addRow( tr3 ); // exception thrown

        TableRow<unsigned, float> trf1( 0, 2.3f, 4.5f );
        TableRow<unsigned, float> trf2( 1, 4.5f, 7.8f );
        Table<unsigned, float> table2( trf1 );
        table2.addRow( trf2 );
        TableRow<unsigned, float> trf3( 2, 3.5f, 8.7f, 9.2f, 4.8f );

        //table2.addRow( trf3 ); // exception thrown

        //table.addRow( trf3 ); // will not compile - mismatched TYPES  

    } catch ( std::exception e ) {
        std::cout << e.what() << std::endl;

        std::cout << "\nPress any key and enter to quit." << std::endl;
        char q;
        std::cin >> q;

        return -1;
    }

    std::cout << "\nPress any key and enter to quit." << std::endl;
    char q;
    std::cin >> q;
    return 0;
}

---

If you uncomment either line that says an exception will be thrown you can see how the table catches the mismatch in sizes of different rows as they must be equal in length.

As for the functions to compare, find, display this table; I'll leave that as a continuing exercise.

However I can give you some guidance. Now as for finding an ID based on an entire row or set of data; this should be fairly simple. You would have to compare one vector with another and then return that ID.

However there is a problem with this... Here's an example of the problem...

IDs | val1, val1, val3, val4
 1  |  a     b      c     d
 2  |  e     f      g     h
 3  |  a     b      c     d

Here if we are searching this table that has a set with (a,b,c,d). There are 2 possible solutions. So you would not be able to directly return a single answer or a single ID as this is an X|Y problem, however because we have nice vectors instead of returning a single answer in this situation you can return a set of answers a container of valid rows or row - ids, but to do this you would have to search through the entire table and for each one that is a match you would have to push that into a temporary container until all matches are found, then return that container back, if there is only a single match you would still be returning a container but it would only contain a single element as it will only be a set of 1.

However you did mention this:

Currently I am free to choose how that data will be stored. Essentially I have IDs with some values, which are assigned to the IDs. A set of values is unique to the ID (no set will be repeated for another ID). Individual values can be repeated across IDs.

So if the data that already exists does not exhibit this problem, then it should not be of a concern.

So your search would then be something like this from the Table's class

template<class ID, class Type>
ID Table<ID, Type>::find( const std::vector<Type>& data ) {
    for ( auto& row : table_ ) {
        if ( data == row.getValues() ) {
            return row.getId();
        } else {
            std::ostringstream strStream;
            strStream << __FUNCTION__ << " could not find matching set." << std::endl;
            throw std::exception( strStream.str().c_str() );
        }
    }
}

---

As for the classes above, you can even expand on them to increase the table's size if needed.

You would have to add an addItem or addElement method to the TableRow class template, and then in the Table class template you would have to add an addColumn method, there would be two tricks with the addColumn method. The first is that it would be variadic like TableRow's constructor but the size of the elements would have to be equal to the amount of rows in the table. The other trick would be having to append each element in the parameter pack to each individual row within the table, but this function would also have to update the row's size which shouldn't be all that hard to do.

Another thing to consider would be is if each element in the list of data that belongs to an ID are not of the same type, these class's would have to be modified a little bit, instead of using std::vector<T> you could use std::tuple<...> and from there compare two tuples.

Answer 4

As an alternative, you can go with std::vector<std::tuple<std::string, char, char, char, char>>:

struct somestruct
{    
    std::vector<std::tuple<std::string, char, char, char, char>> _data;

    std::string findID(char val1, char val2, char val3, char val4)
    {
        auto it = std::find(begin(_data), end(_data) [](const auto& item) {
            return item.get<1>() == val1 && /*...*/;
        });
        return it->get<0>();
    }
};