Need advice with datastructure

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?

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

Code:

---

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;
}

---

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.

You should overwrite the [] operator for that set:

Code:

---

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;
}

//...

---

Quote:

---

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

Code:

---

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?

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

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

Code:

---

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.

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.

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.

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 :confused:

Can you post your current code?

Code:

---

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 :thumb:

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.

This makes me happy too. :)

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

Code:

---

// 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 :

Code:

---

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 :

Code:

---

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

---

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

Code:

---

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

---

Note: the same is true for your other classes

It took me too long to post ...

another point : you have a number of loops which are basically like this :

Code:

---

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)
  {
  }
  g_pos++;
}

---

You are looping thru the map looking for a particular key. This
is O(N). std::map has a find function that is O(LOG(N)) :

Code:

---

std::map<int,CGroup>::iterator g_pos = m_logData.m_groups.find(g);

if (g_pos != m_logData.m_groups.end())
{
  // found
}
else
{
  // not found
}

---

Well, thanks anyway for the reply. It teaches me alot about the inner working of maps. By the way, that first solution you suggested does not seem to work in my case, that was the first thing I tried after I Deciphered those cryptic compiler messages. And another thing, "Effective STL". is that a book or an online guide or something? I would love to have some additional documentation on STL. Currently I only have the "Standard Template Library Programmer's Guide" but that's a bit too abstract for me.

The Meyers book is not available online. The first book I would
recommend is "The C++ Standard Library : A Tutorial and
Reference" by Nicolai Josuttis. (I also recommend the Meyers
book, but I would get Josuttis first)

Besides being a good reference, the "Tutorial" in the name
is accurate. You can see the types of code presented
in the book at :

http://www.josuttis.com/libbook/toc.html

Note: I don't know if my post concerning using map::find()
instead of loop thru crossed paths with your post. If not,
take a look at it.

A lot of people is asking aout STL and I for one only know what I actually worked with. maybe it would be a good ideea to have a forum dedicated to STL exclusivelly.

STL is an official part of the C++ language, so this forum is the perfect place for discussing STL.

Quote:

---

Originally posted by Philip Nicoletti
The Meyers book is not available online. The first book I would
recommend is "The C++ Standard Library : A Tutorial and
Reference" by Nicolai Josuttis. (I also recommend the Meyers
book, but I would get Josuttis first)

Besides being a good reference, the "Tutorial" in the name
is accurate. You can see the types of code presented
in the book at :

http://www.josuttis.com/libbook/toc.html

---

Looks good to me. I'm getting it ASAP.

Quote:

---

Note: I don't know if my post concerning using map::find()
instead of loop thru crossed paths with your post. If not,
take a look at it.

---

Yes, it is much better. Not only faster but also more logical en better to understand. :thumb:

Quote:

---

Originally posted by Mza
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.

---

I just read from the book, Effective STL, which shown that if the vector is sorted, we can use binary search to locate the required element in O(log n). The caveat is that using a sorted vector is most appropriate only when once the vector is initialized, there is very little chance of adding/removing element during lookup phase.