Need advice with datastructure

[Mza]

Hi everybody,

I'm pretty new to C++ so I don't know if I'm on the right track with the following subject.

I'm making a little application to modify and view some logging information. Every log message has a group, subgroup and level (all integers) associated with it. Because I want to enable the user to select what group, subgroup and level he wants to see, I want to inspect the logfile and see what groups, subgroups and levels are available and store this information in a datastructure. The global structure should be something like a list or set of groups where every group has a set of subgroups and every subgroup a set of levels. Something structured like this:

group
- subgroup
-- level
-- level
- subgroup
-- level
group
- subgroup
-- level

I tried to implement this the following way:

typedef std::set<int> levels;
typedef std::map<int,levels> subgroup;
typedef std::set<subgroup> subgroups;
typedef std::map<int,subgroups> group;
typedef std::set<group> groups;

But I can't seem to acces my elements. Maybe I'm doing it the wrong way or maybe this is just not a recommendable datastructure. Anybody any advice?

[kuphryn]

There are several solutions. One solution is a map within a map. Another solution is to wrap the innermost data in a structure and design a map to house the structure.

Kuphryn

[Joe Nellis]

class level
{ 
    int level;
    std::string message;
}

class subgroup
{
   std::string subgroupname;
   std::vector<level> Levels;
}

class group
{
    std::string groupname;
    std::vector<subgroup> Subgroups;
}

int main()
{
    std::vector<group> logfile;
}

[Mza]

Thnx for the help

I tried several implementations including an adjustment to what I posted earlier, namely:

typedef std::set<int> levels;
typedef std::map<int,levels> subgroups;
typedef std::map<int,subgroups> groups;

But when implementing another part I discoverd that I needed more data then just an int so I tried something like the code of Joe Nellis and it works fine.

But this raises another question. How to directly acces the vector's elements (with O(1), like in an array). I thought Vectors should be able to do that but I saw it only with an integer or string, not with a class. The integer value that every class has could act as a key.

[PadexArt]

You should overwrite the [] operator for that set:

class level
{
	//...
};

struct VectorLevels
{
private:
	std::vector< level> vct;

public:
	inline level operator [] ( int n)
	{	
		int pos = 0;

		//search for level = n and store it's value in pos ( or in an iterator)
		//...

		return vct.at( pos);
	}
};

class subgroup
{
   std::string subgroupname;
   VectorLeveles levels;
}

//...

[Mza]

Originally posted by PadexArt
You should overwrite the [] operator for that set:

class level
{
	//...
};

struct VectorLevels
{
private:
	std::vector< level> vct;

public:
	inline level operator [] ( int n)
	{	
		int pos = 0;

		//search for level = n and store it's value in pos ( or in an iterator)
		//...

		return vct.at( pos);
	}
};

class subgroup
{
   std::string subgroupname;
   VectorLeveles levels;
}

//...

But won't this searching for level = n cost me O(n) time? Or is this inevitable with the way I use vectors?

[PadexArt]

Yes, the cost will be indeed O(n).

A fatser way ( that I can think of) would be to duplicate the information :

class VectorLevels
{
//same as above

private:
map::<int, level> searchMap; //same data as in the levels std::vector
}

So, in the [] operator you would actually use the search map.

[Mza]

So I guess it is not possible to keep using Vectors in this situation. Then a map indeed sounds like a better solution, although I don't like the idea of data duplication. Of course I could always remove the key from the level class and access that information via the key of the map. The stl documentation that I have also mentions a hash_map so I probably should use that one (I don't care about the order of the map, just the direct access is important). In any case, thanks for the help.

[PadexArt]

The data duplication was mentioned as I didn't know how fond you were of using vectors. If no requirements are for using the vector you can verry well use the map.

[Mza]

Well, I don't have a preference for any datastructure as long as it does the job. So I started with the adjustments for map, but now It won't compile anymore. The implementation using vectors was working fine and I think I try to acces the map elements the right way.

Could it be that a map imposes additional constraints on its elements? Should I add some operators on the level class

[PadexArt]

Can you post your current code?

[Mza]

class CLevel  
{
public:
	bool visible;
	CString text;
	int level;

	CLevel(int l_level);
	virtual ~CLevel();
};

class CSubgroup  
{
public:
	int subgroup;
	CString text;
	std::map<int,CLevel> levels;
	
	CSubgroup(int l_subgroup, int l_level);
	virtual ~CSubgroup();
};

class CGroup  
{
public:
	int group;
	CString text;
	std::map<int,CSubgroup> subgroups;

	CGroup(int l_group, int l_subgroup, int l_level);
	virtual ~CGroup();
};

class CGroups  
{
public:

//I'm planning to add some access and alter function here

	std::map<int,CGroup> m_groups;

	CGroups();
	virtual ~CGroups();
};

// This is where I use these classes, m_logData is an instance of CGroups

void CSimpelDlg::addLine(int g, int s, int l)
{
	std::map<int,CGroup>::iterator g_pos = m_logData.m_groups.begin();
	while (g_pos != m_logData.m_groups.end())
	{
		if (g_pos->first == g)
		{
			// insert s and l in g
			std::map<int,CSubgroup>::iterator s_pos = g_pos->second.subgroups.begin();
			while (s_pos != g_pos->second.subgroups.end())
			{
				if (s_pos->first == s)
				{
					//insert l in s and g

					std::map<int,CLevel>::iterator l_pos = s_pos->second.levels.begin();
					while (l_pos != s_pos->second.levels.end())
					{
						if (l_pos->first == l)
						{
							// l does already exist in g and s, do nothing
							return;
						}
						l_pos++;
					}
					//l does not exists in g and s, make new l in s with value l
					s_pos->second.levels[l] = CLevel(l);
					return;
				}
				s_pos++;
			}
			//s does not exist in g, make new s in g with values s and l
			g_pos->second.subgroups[s] = CSubgroup(s,l);
			return;
		}
		g_pos++;
	}
	// g does not exist yet, make new g in m_classgroups with values g,s and l
	m_logData.m_groups[g] = CGroup (g,s,l);
	return;

}//addLine

I really appreciate you helping me out, cause without such help I would never get so far

[Mza]

Nevermind, I already discovered the origin of the compile errors. A map needs a standard constructor and I made a constructor with arguments (although all arguments had default values). Now I just added a default constructor and both the compiler and I are happy.

[PadexArt]

This makes me happy too.

[Philip Nicoletti]

I think the reason for the compile error is as follows:

// g does not exist yet, make new g in m_classgroups with values g,s and l
m_logData.m_groups[g] = CGroup (g,s,l);

you are using operator [] to add to the m_groups map. This
is OK - except you need to know how it usually works
internally (following is basically from Scott Meyer's "Effective STL",
Item 24 : Choose carefully between map::operator [] and
map::insert when efficiency is important).

when doing the following :

m_logData.m_groups[g] = CGroup (g,s,l);

The first thing that is done, is a check to see if the key "g"
is already in the map. If it is, it updates the value. If not,
it creates an object using the VALUE types DEFAULT
constructor, then updates it (CGroup(g,s,l)). Your class
CGroup does not have a default constructor, so it can
not create an object to add. You can get around this in one
of two ways :

1) change CGroup's constructor :

CGroup(int l_group = 1, int l_subgroup = 1, int l_level = 1);

2) or use insert instead of operator [] ...

m_logData.m_groups.insert( make_pair(g,CGroup (g,s,l)) );

Note: the same is true for your other classes