搜索一个数据结构，它可以像地图一样工作，也可以检索其他信息

Question

我有以下字符，如果它们在同一个括号中，我想给它们连续分配数字。例如

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

我想从给定的char中检索我可以用c++中的std::map实现的数字。然而，一旦我分配这些数字与map。我丢失了[a,b]在一个括号里而[c]是分开的信息。这个信息我要保留。

是否有一些数据结构，我可以使用这样的数据结构:[a,b]可以分配连续的数字，并且我可以得到[a,b]在一个括号中，而[c]是唯一在它的括号中的信息。

我的方法是使用map…但它不符合我稍后找出[a,b]是否在同一括号内的需要。能否有人建议一种数据结构，使其满足我连续分配数字的需要，并保留它们属于同一括号的信息。

Answer 1

我不完全清楚你在问什么，但这个答案是基于我目前的解释。难道不能使用一个值类型来存储有关该字符所在组的额外信息吗?例如:

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)
...

Answer 2

正如其他人指出的那样，没有一种数据结构能完全满足您的需求(据我所知)。但是，您可以自己轻松地设计一个。一些建议:

• 将每个字符映射到包含括号号和字符号的元组或结构体:

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

• 使用两个容器:一个包含字符组/括号列表，另一个是普通映射:

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

• 使用地图矢量:

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

您可以轻松地在这些表示之间进行转换。但是对于典型的操作，它们有不同的复杂性。如果能够检查某个字符是否在某个组中并访问其映射到的数字对您来说很重要，那么使用第一个解决方案。如果您需要经常列出一个组的所有字符，或者一个字符可以包含在多个组中，那么我更喜欢第二种方法。最后一种方法可能很有用，如果一个字符可以是多个组的元素，并且您希望根据组将其映射到不同的数字。