We help IT Professionals succeed at work.

Adding a new node?

nidan
nidan asked
on
Medium Priority
219 Views
Last Modified: 2010-04-02
I created a class derived from std::list.  I'm adding an insertion method where if an item is already present, the list items will become ordered by the frequency with which they have occured, most frequent items first.  If I wasn't using STL, I'd just add an int item to the node struct to hold the number of times the item had been accessed.  I'd like a suggestion about how I can keep track of the frequency of the items.  Also how I can access the frequency data so I can sort the items later on.
Comment
Watch Question

AxterSenior Software Engineer

Commented:
Try creating the template object with a pair and an int.

Example:

template<class T>
class foo_list : public std::list<std::pair<int,T> >
{
public:
};

You can use the integer to store occurences.


Using this method, you'll have to override all the iterators functions so that they just point to T, and not std::pair<int,T>
AxterSenior Software Engineer

Commented:
Actually, using this method, you'll have to override all the functions that deal with T.

Author

Commented:
I'm unsure about what the std::pair<int,T> means.  Also, what does it mean that I'll have to override all the functions that deal with T?
AxterSenior Software Engineer

Commented:
Never mind.  I don't think this would be the right approach for you.  In order to use this method, you would need to know a lot about the list container and its memebers.
This method would also take more work then what its worth.
AxterSenior Software Engineer

Commented:
nidan,
Can you explain more about what exactly you're trying to do?

If the calling function attempts to insert and item on the list, and the item already exist in the list, will your call still add another copy to the list?

Are you going to overrite the push_back and push_front member functions?

Can you post the code to your class?

Author

Commented:
I have added 5 methods to my list class.  This one is the final method I need to add to my class.  If an item is already present in the list, order list items by the frequency with which they have occured, most frequent items first, else add it to the rear.  I'm not going to overwrite the push_back and push_front member functions.  Here is my class so far:

template <class T>
class MyList:public std::list<T>
{
     public:
          void myfront(const T& item);
          void rear (const T& item);
          void moveToFront(const T& item);
          void transpose(const T& item);    
          void order(const T& item);
          void count(const T& item);
};

template <class T>
void MyList<T>::count(const T& item)
{
// this is the method i need to implement
}
CERTIFIED EXPERT
Author of the Year 2009

Commented:
You need your list to contain two values per element:  the value itself and the frequency count.  Thus, your list object must be a structure.  

Axter can explain how to do that better than I.  Templates just confuse me.  

-- Dan

Axter: Xref to:
http://www.experts-exchange.com/jsp/qShow.jsp?ta=cplusprog&qid=20183041

Author

Commented:
Wouldn't I have to re-write my whole class in order to have the list object a struct?
CERTIFIED EXPERT
Author of the Year 2009

Commented:
I believe that that is the whole point of using a template.  It understands various data types and you can instantiate a list of type int, struct mystruct, pointer-to-GUID, whatever, and the semantics of data access are the same.  

I think.  I find that I and my team are more productive when we stay away from STL and its voodoo.  For instance, if I need an array of structures, I just make one using normal C or C++ syntax.  It's all right there in the open and when something goes wrong, it is easy to debug.  STL-derived code is unmaintainable.  Just try to use the debugger to look at what *would be* a nice clean array of data after it has been mangled by STL.  

-- Dan

Author

Commented:
Right, a template understands various data types, but  wouldn't I always have to insantiate a list of type struct mystruct:

MyList<mystruct> theList;

What if I wanted to use a list of strings or ints:

MyList<string> theList;

So it would kind of defeat the purpose of using a template if I could only instantiate a list of type mystruct.  



AxterSenior Software Engineer

Commented:
I believe you're using the wrong container for your requirements.
Instead of using std::list, you should use std::map.

I'll post an example shortly.
Senior Software Engineer
Commented:
I decided to go back to a list type.

Example class:

template<class T>
class chache_list : public std::list<T>
{
public:
     void Add(const T& x)
     {
          int Qty = HitQty[x] + 1;
          HitQty[x] = Qty;
          if (Qty == 1)
          {
               push_back(x);
          }
          else
          {
               ReOrder();
          }
     }
     void ReOrder(void)
     {
          std::map<int,T> Temp;
          for (std::map<const T,int>::iterator i = HitQty.begin();i!=HitQty.end();i++)
          {
               Temp[i->second] = i->first;
          }
          clear();
          for (std::map<int,T>::iterator ti = Temp.begin();ti!=Temp.end();ti++)
          {
               push_front(ti->second);
          }
     }
     std::map<const T,int> HitQty;
};
AxterSenior Software Engineer

Commented:
Example implmentation:

int main(int argc, char* argv[])
{
     chache_list<std::string> test;
     test.Add("Tom");
     test.Add("Dick");
     test.Add("Harry");
     test.Add("Axter");
     test.Add("Dick");
     test.Add("Dick");
     test.Add("Dick");
     test.Add("Tom");
     test.Add("Tom");
     test.Add("Dick");
     test.Add("Tom");
     test.Add("Axter");
     for (chache_list<std::string>::iterator i = test.begin();i!=test.end();i++)
     {
          std::cout << i->c_str() << std::endl;
     }
     return 0;
}
AxterSenior Software Engineer

Commented:
The example class I posted has very little code, but it has a high over head for the ReOrder() function.

You can speed the ReOrder function my adding more code to it.
What you would have to do is iterate through the list, and reoder it by the value that is in the HitQty variable.

Author

Commented:
Thanks again for your help.  I was wondering if this can be implemented using the vector container instead of the map container?  I'm fairly new to STL and I haven't studied maps yet.  
AxterSenior Software Engineer

Commented:
>>can be implemented using the vector container instead
>>of the map container

No.  The vector container does not have the functionality that you need.

The map container is designed to hold a pair of objects, and it automatically sorts it's contents by the first object in the pair.
The vector container is not design to do this.

Explore More ContentExplore courses, solutions, and other research materials related to this topic.