CODEWITHSUNDEEP
c++c
user1778824
user1778824

Reputation: 369

Searching for a data structure which can act like a map as well as retrieve other information

I have the following chars to whom I want to assign numbers consecutively if they are in the same bracket. E.g.

   [a,b],[c],[d,e],[f,g],[h]
   a=0, b=1,c=2,d=3,e=4,f=5,g=6,h=7

From the given char I want to retrieve the number which I can do with std::map in c++. However, once i assign these numbers with map. I loose the information that [a,b] are in one bracket and [c] is separate. This information I want to retain.

Is there some data structure which I can use such that: [a,b] can be assigned consecutive numbers and also I can get the information that [a,b] are in one bracket and [c] is the only ones in its bracket.

My approach was to use map...but it does not fit my need of later finding out whether [a,b] are in the same bracket. Can someone please suggest a data structure such that it satisfies my need of assigning numbers consecutively as well as retaining the information that they belong to the same bracket.

Upvotes: 0

Views: 86

Answers (2)

Markus Mayr
Markus Mayr

Reputation: 4118

As others pointed out, there is no data structure that fits your needs perfectly (as far as I know). You can, however, easily design one yourself. Some suggestions:

  • Map each character to a tuple or struct that contains the bracket number and the character number: 

    struct CharData { int group; int characterNumber; };
std::map<char, CharData> data;

  • Use two containers: One contains a list of character groups / brackets, the other one is a plain map:

    std::vector<std::vector<char> > groups;  // Store groups in this container.
std::map<char, int> mapping; // Store mapping to integers in this container.

  • Use a vector of maps:

    std::vector<std::map<char, int> > data;

You can easily convert between these representations. They have different complexity for typical operations though. If it is important to you that you can check if a character is in a certain group and to access the number it is mapped to, then go four the first solution. If you need to list all characters of a group quite often or a character can be contained in multiple groups, then I would prefer the second approach. The last approach can be useful, if a character can be an element of multiple groups and you want to map it to different numbers depending on the group.

Upvotes: 1

Benjamin Lindley
Benjamin Lindley

Reputation: 103693

It's not entirely clear to me what you are asking, but this answer is based on my current interpretation. Can't you just use a value type that stores the extra information about what group the char is in? For example:

struct value_type
{
    int num;
    int group;
};
....
std::map<char, value_type> m;
m['a'].num   = 0;
m['a'].group = 0;
m['b'].num   = 1;
m['b'].group = 0;   // same group as 'a'
m['c'].num   = 2;
m['c'].group = 1;   // new group
// etc...

// testing if 'a' and 'b' are in the same group
if (m['a'].group == m['b'].group)
...

Upvotes: 3

Related Questions