CODEWITHSUNDEEP
c++data-structures
Xara
Xara

Reputation: 9118

C++ : suitable Data Structure for this given scenario

I want to know which data structure will be good in my case.Please guide me. Following are the requirements. As shown in the fig below, on the basis of three values A, B and C ( where A will be an integer value and B , C will be characters). The left side table will all have unique entries. I want to store two values accepting rule number and true/false.Thus, for each unique value of A,B and C I want to store two values (accepting rule number and true/false) corresponding to them.One important thing is that accepting rule number can be one or more (size is not fixed). Secondly, table length can go upto 65025 or above.

enter image description here

P.S: I asked this type of question previously but this time the scenario is little different.

Upvotes: 0

Views: 464

Answers (5)

Matthieu M.
Matthieu M.

Reputation: 300299

Let us checks our basics, would you.

You basically want an association between a triplet (number, character, character) and a pair composed of two elements: a set of accepting rule numbers and a boolean (note: in your example the boolean is correlated with the fact that there is an accepting rule number or not).

So, we take this answer on how to best select a standard library container and follow its questions dumbly:

  1. Associative ? Yes
    1. Ordered ? No => unordered_
    2. Separate Key ? Yes => map
    3. Multiple values ? No (single structure) => no multi

And that's it, you want an unordered_map from your key (the triplet) to your value (the pair).

For an unordered map, we need 5 template parameters:

  • Key (the key)
  • T (the value)
  • Hash: a predicate that computes the hash of the key, it defaults to std::hash<Key> if correctly implemented
  • Equal: a comparator that checks the idempotence of two keys with the same hash, since hashing is not injective, it defaults to std::equal<Key> (that is, to using operator==)
  • Allocator: a memory allocator from where the container draws its memory, it defaults to std::allocator

So, providing that our Key can be hashed and compared for equality, we only really need to provide a Key and the associated value. Few keys are hashable though, so we'll provide the hasher ourselves.

struct TableKey {
    int A;
    char B;
    char C;
};

struct TableKeyHasher {
    size_t operator()(TableKey const& tk) const {
        return hash<int>(tk.A) ^ hash<char>(tk.B) ^ hash<char>(tk.C);
    }
};

bool operator==(TableKey const& left, TableKey const& right) {
    return std::tie(left.A, left.B, left.C) == std::tie(right.A, right.B, right.C);
}

bool operator!=(TableKey const& left, TableKey const& right) {
    return not (left == right);
}

struct TableValue {
    std::unordered_set<int> acceptingRules;
    bool someBooleanWithoutName;
};

And finally:

using MySuperTable = std::unordered_map<TableKey, TableValue, TableKeyHasher>;

Upvotes: 2

wayi
wayi

Reputation: 523

You question is vague, since you didn't tell us what operations you wish to support.

If your only purpose is retrieving an entry from the right table, given by an entry from the left table, then hash table is a good option, where you need to define two structs for both right table entry and left table entry.

Alternatively, you can also consider TRIE, which builds the left table as a prefix tree. This may help you save some space.

Moreover, if the right table is very sparse, e.g., too many 0-0 entries, you should consider store them as the pointers which point just one instance.

BTW, do you need to support any query based on the right table or any sorting function?

Upvotes: 1

user3140280
user3140280

Reputation: 313

 struct Left{

int A;
char B, C;
int AcceptingIndex; //index of accepting number in the main array

};

}

struct Data{

int *PToAcceptNumber[size];
bool TF[size];

Left LeftValues[leftsize];


};

You have an array of arrays PToAcceptNumber. You could choose linked lists if you want, that would be an array of linked-lists. The left side values are in a struct Left. Each Left knows its accept values it identifies it by its index in the main array. Then each accept number list has a corresponding boolean value in the TF array.

Upvotes: 1

Peter
Peter

Reputation: 1789

Yes. The values A,B,C of the left table form a key for your table on the right. So whatever datastructure you are using, it will depend on that combined key. This also means iterating over the keys every time you want to look up the table no matter what values are used, so a hash - function could be usefull which's return value is used as a key for the struct Data

Upvotes: 1

user1508332
user1508332

Reputation:

As much as I understood, this is how I would solve the problem:

B and C kept in a char matrix while A can simply be the counter you use for the lines of your matrix. Make a structure where in an int array of decent size ([10] for example), you should keep the rule numbers, and an unsigned variable that will keep the true or false 1 or 0. Define an array that will have the type of that structure and as manny elements as there are lines in that matrix. So in the end for every line in the char matrix you will have a structure that will contain the rules and the 1 or zeros.

Upvotes: 1

Related Questions