Solved

Tree .... data structure in C++

Posted on 2003-12-08
3
700 Views
Last Modified: 2010-04-01
Hi Experts,

     I am currently trying to understand the implementation of the tree structure. The following is a tree class and I have several questions about it :
--------------------------------------------------------------------------------------------
class Tree
{   struct Node ;
    typedef string Type ;
    typedef list<Node*> List ;
    typedef List::iterator LIt ;
    List _nodes ;

  public :
    class Iterator ;     //line01, Q1
    Tree() ;
    Tree(const Tree&) ;
    Tree(const Type&) ;
    Tree(const Type&, const list<Tree*>&) ;
    ~Tree() ;
    Tree& operator=(const Tree& t) ;
    void clear() ;
    Iterator begin() ;
    Iterator end() ;
    friend class Iterator    //line02, Q1
    {  Tree* _tree ;
       LIt _lit ;
      public:
       Iterator() ;
       Iterator(const Iterator&) ;
       Iterator(Tree*, Node* = 0) ;
       Iterator(Tree*, LIt) ;
       void operator=(const Iterator& it) ;
       bool operator==(const Iterator& it) ;
       bool operator!=(const Iterator& it) ;
       Iterator& operator++() ;
       Iterator operator++(int) ;
       Type& operator*() const ;  // line03 ...Q2
       bool operator!() ;
       friend class Tree ;
    };
};
---------------------------------------------
  Q1: line01 and line02: It seems to me that the class "Iterator" were declared twice. The first time it was declared as an inner class; the second time it was declared as a friend class. This is a little bit wierd to me. Is that okay to declare something twice ? and is that okay to be an inner class and friend class at the same time ?

 Q2: line03: This is a more general question, not only in the tree structure. Sometimes I saw a declaration of a function looks like :"void fun1() const ;"  or "int fun2() const ;". What does the "const" mean here ???

   Thanks very much !

 meow......
0
Comment
Question by:meow00
  • 2
3 Comments
 
LVL 86

Expert Comment

by:jkr
Comment Utility
Q1: line01 is a 'foward declaration', i.e. you are telling the compiler that you are going to use a typename that is defined later

Q2: The 'const' keyword means that this funcion is not manipulating any members of the class it belongs to - from the docs:

C++ Specific

Declaring a member function with the const keyword specifies that the function is a "read-only" function that does not modify the object for which it is called.

To declare a constant member function, place the const keyword after the closing parenthesis of the argument list. The const keyword is required in both the declaration and the definition. A constant member function cannot modify any data members or call any member functions that aren't constant.

END C++ Specific

Example

// Example of a constant member function
class Date
{
public:
   Date( int mn, int dy, int yr );
   int getMonth() const;       // A read-only function
   void setMonth( int mn );    // A write function;
                               //    cannot be const
private:
   int month;
};

int Date::getMonth() const
{
   return month;        // Doesn't modify anything
}
void Date::setMonth( int mn )
{
   month = mn;          // Modifies data member
}
0
 
LVL 1

Author Comment

by:meow00
Comment Utility
Thanks for the answer.... just have a short question about Q1.
The "Iterator class" was really used between line01 and line02. Then why we need the line01 for forward declaration ? can we get rid of it ? Thanks.

meow....
0
 
LVL 86

Accepted Solution

by:
jkr earned 80 total points
Comment Utility
If you'd move

    Iterator begin() ;
    Iterator end() ;

past the definition of 'Iterator', you can get rid of the fwd. declaration...
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

8 Experts available now in Live!

Get 1:1 Help Now