iterator int template class

This is a discussion on iterator int template class within the C++ Programming forums, part of the General Programming Boards category; I am trying to create a Haskell-like list. So I wrapped a normal C++ list. I have a problem though ...

  1. #1
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853

    iterator int template class

    I am trying to create a Haskell-like list. So I wrapped a normal C++ list. I have a problem though declaring an iterator:
    Code:
    template <class T>
    class hList
    {
    	list<T> data;
    public:	
    	hList<T> head() {
    		hList<T>* tail = new hList<T>;
    		if (this->data.size() == 0) return *tail;
    		tail->data.push_back(*(this->data.begin()));
    		data.pop_front();
    		return *tail;
    	}
    	hList<T> operator+(hList<T>& l) {
    		data.insert(data.end(), l.data.begin(), l.data.end());
    		return *this;
    	}
    	hList<T> sel(hList<T>& l, bool (*fun)(const hList<T>&,  const hList<T>&)){	
    		list<T>::iterator it;        // <============= error
    	}		
    };
    I assume you cannot declare an iterator since the T class isn't known?
    In any case what should I do? I wan to iterate through all the elements of list<T> data.

    My goal is to do this:
    Code:
    template <class T>
    hList<T> qsortH(hList<T>& l)
    {
    	hList<T> h = l.head();
    	if (h.data.size() == 0) return l;
    	return qsort(l.sel(l,lesser) + h + qsort(l.sel(l,greater)));
    }
    to simulate this example showing how simple and easy read Haskell can be:
    Code:
    qsort1 []     = []
    qsort1 (p:xs) = qsort1 lesser ++ [p] ++ qsort1 greater
    Any other suggestions are welcome
    Last edited by C_ntua; 10-18-2008 at 10:34 AM.

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    hList doesn't contain an iterator type. How do you expect to declare a variable of that type?

    If you want list's iterator, you need to know that the type is "dependent" - it could depend on the template parameter whether it's a type or an object. Thus, you need the typename keyword to disambiguate:
    Code:
    typename list<T>::iterator it;
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Yes, that was a typo, I meant list<T>::iterator it. I ll edit it. I should have mention it gave me the error error:expected ';' before "it", which didn't really explain a lot.

    But thank you. The typename think worked Didn't even know that there was such a keyword!

  4. #4
    Registered User
    Join Date
    Apr 2006
    Posts
    2,023
    For the rest of your code:

    1)Shouldn't head return a value of type T, the value returned being the first element.
    2)Unlike Haskell, your functions arn't pure. If you are trying to write Haskell functions in C++, then all your functions should be pure, implying that they take const references (or copies) as arguments, and are all methods are const.
    3) Unlike Haskell, C++ does not have lazy evaluation. To order to implement lazy evaluation in C++, your functions should not return their result. Instead, they must return the sequence of steps to reach those results, including the sequence of steps resulting from function they call. Only functions like show actually force the evaluation of functions in Haskell. Not that you necessarily want to go to that length, but that is what it would toke to translate that function into C++.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  5. #5
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Ok, not to create a new topic, I updated the code. I have the return statement unfinished, because I get errors. I will finish it tomorrow. Though, can someone look at the code and give me some opinions? I want to do things as noted in the first post. Any ideas welcomed...
    Code:
    #include <iostream>
    #include <vector>
    #include <list>
    using namespace std;
    
    template <class T>
    class hList
    {
    public:
    	list<T> data;
    	typename list<T>::iterator it;
    	hList<T>* head() {
    		hList<T>* tail = new hList<T>;
    		if (this->data.size() == 0) return tail;
    		tail->data.push_back(*(this->data.begin()));
    		data.pop_front();
    		return tail;
    	}
    	hList<T>& operator+(hList<T>& l) {
    		data.insert(data.end(),l.data.begin(),l.data.end());
    		return *this;
    	}
    	hList<T>& filter(const T c, bool (*fun)(const T&, const T)){
    		hList<T>& result = new hList<T>;
    		for (it = data.begin(); it != data.end(); ++it)
    			if(fun(*it, c))
    				result.data.push_back(*it);
    		return result;
    	}
    };
    
    bool lesser(const int i, const int c)
    {
    	if (i < c) return true;
    	else return false;
    }
    
    bool greater(const int i, const int c)
    {
    	if (i > c) return true;
    	else return false;
    }
    
    template <class T>
    hList<T>& qsortL(hList<T>& l)
    {
    	hList<T> h = *l.head();
    	if (h.data.size() == 0) return l;
    	return ;
    }
    Last edited by C_ntua; 10-18-2008 at 05:33 PM.

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    The objection about the return type of head still applies.
    The name of cmp is poorly chosen. The name implies that the function compares something to something else, and returns a boolean, or possibly a tri-state relation (less, equal, greater). The correct name for this function is filter.
    Passing function pointers is so C. In C++, that should be a member template that takes a proper comparison predicate. This would allow you to take not only std::less<T> etc., but even binders and lambda expressions. It would also be more efficient than function pointers, since functors can be inlined.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  7. #7
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Can you show me a sample code how can this be done without a function pointer?

  8. #8
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Quote Originally Posted by King Mir View Post
    For the rest of your code:

    1)Shouldn't head return a value of type T, the value returned being the first element.
    2)Unlike Haskell, your functions arn't pure. If you are trying to write Haskell functions in C++, then all your functions should be pure, implying that they take const references (or copies) as arguments, and are all methods are const.
    3) Unlike Haskell, C++ does not have lazy evaluation. To order to implement lazy evaluation in C++, your functions should not return their result. Instead, they must return the sequence of steps to reach those results, including the sequence of steps resulting from function they call. Only functions like show actually force the evaluation of functions in Haskell. Not that you necessarily want to go to that length, but that is what it would toke to translate that function into C++.
    1) Well, I just made it return a hList, because that is how it is handled, as a list with one element. Otherwise I could use the overloaded operator + for example with it. I would have to make another one, so it matches this case also. I will eventually...
    2) Yeah, that is how it was in the beginning. But wouldn't that make it ineffective? It would make a lot of copies. Haskell knows how to handle its own language, but doing the same with C++ would mean a lot of copying and memory slowing things down. It would make thinks a lot easier though. But I would prefer to stick with something that has some performance. But anyhow, I want to simulate the list not everything in Haskell!

    Basically I just want the features of filtering (yeah, much better name ) a list and separating the head from the tail so you can do things easily using recursion. And of course being able to use some operators. Like +. I will also overload - and probably []. That is basically it.

  9. #9
    Registered User
    Join Date
    Apr 2006
    Posts
    2,023
    Quote Originally Posted by C_ntua View Post
    1) Well, I just made it return a hList, because that is how it is handled, as a list with one element. Otherwise I could use the overloaded operator + for example with it. I would have to make another one, so it matches this case also. I will eventually...
    Why not make a hList constructor takes one element. Or a cons function that prepends an element to a list.

    2) Yeah, that is how it was in the beginning. But wouldn't that make it ineffective? It would make a lot of copies. Haskell knows how to handle its own language, but doing the same with C++ would mean a lot of copying and memory slowing things down. It would make thinks a lot easier though. But I would prefer to stick with something that has some performance. But anyhow, I want to simulate the list not everything in Haskell!

    Basically I just want the features of filtering (yeah, much better name ) a list and separating the head from the tail so you can do things easily using recursion. And of course being able to use some operators. Like +. I will also overload - and probably []. That is basically it.
    Here's how to do these things with std::list :
    the features of filtering
    Use std::list::remove_if.

    separating the head from the tail
    To get the head, you just return the first element. To get the tail you remove the first element, and return the list.

    Like +
    Use std::copy() with a back inserter as the target.

    I will also overload -
    What do you want - to do?

    It's not inefficient as long as you use those functions. Except that recursion will by it's nature be inefficient.

    and probably [].
    Would this do list indexing, or do you just want a function to return an empty list? You can't overload [] to take no arguments. List indexing is inherently inefficient.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  10. #10
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    OK, will use remove_if() and copy() in my functions. Will still overload operators just to be more readable and sacrifice some speed. I know indexing with [] is inefficient, but it is still useful. Since I want my list to be functional I will make them an option. I ll re-think about head and tail to make it as easy-to-use as possible. Thanks for the help

  11. #11
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Since I want my list to be functional I will make them an option.
    When you need random access, you shouldn't have used list in the first place.

    Can you show me a sample code how can this be done without a function pointer?
    Code:
    template <typename T>
    class hList
    {
    ...
      template <typename UnaryPred>
      hList<T> filter(UnaryPred p) {
        hList<T> target;
        for(typename list<T>::iterator it = data.begin(); it != data.end(); ++it) {
          if(p(*it)) target.data.push_back(*it);
        }
        return target;
      }
    };
    Usage with std::tr1::bind:
    Code:
    #include <tr1/functional>
    
    hList<int> l = ...;
    hList<int> l2 = l.filter(std::tr1::bind(std::less<int>(), std::tr1::_1, 4));
    Usage with boost::lambda:
    Code:
    #include <boost/lambda.hpp>
    
    l2 = l.filter(boost::lambda::_1 < 4);
    By the way, your usage of references and new is not only syntactically invalid, but also very likely a memory leak.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  12. #12
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,536
    Quote Originally Posted by C_ntua View Post
    Can you show me a sample code how can this be done without a function pointer?
    Basically, all you would have to do is create a template type parameter:
    Code:
    template<typename T>
    And then just use that type as-is in the function parameter list:
    Code:
    hList<T> filter(T p)
    Now, all types that match the interface, whether it's a function pointer or some custom class with properly overloaded operators will work.
    It's a technique usually known as static polymorphism and is very powerful.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. template and friend class
    By black_spot1984 in forum C++ Programming
    Replies: 3
    Last Post: 10-21-2008, 05:50 PM
  2. template class default constructor problem
    By kocika73 in forum C++ Programming
    Replies: 3
    Last Post: 04-22-2006, 09:42 PM
  3. Instantiating a template class
    By NullS in forum C++ Programming
    Replies: 11
    Last Post: 02-23-2005, 09:04 AM
  4. Function template in Class template?
    By Aidman in forum C++ Programming
    Replies: 3
    Last Post: 10-28-2003, 08:50 AM
  5. structure vs class
    By sana in forum C++ Programming
    Replies: 13
    Last Post: 12-02-2002, 06:18 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21