Thread: a smarter STL?

  1. #1
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708

    Post a smarter STL?

    One of the fundamental problems with generic algorithms is that the underlying data is often obscured by (sometimes several) layers of indirection. The standard approach is to have the user supply special-purpose function objects for comparison and assignment, adding unnecessary redundancy, bloat, and function-call overhead to otherwise simple tasks. An automated dereferencing mechanism could be built into these algorithms to eliminate this problem, allowing a higher level of abstraction and better overall productivity. Here is an example of how this might be implemented using recursive template specialization:

    Code:
    template <class T, bool dereference = true>
    struct dref
    {
    	typedef T type;
    	
    	static
    	inline
    	type &
    	get(type & value)
    	{
    		return value;
    	}
    };
    
    template <class T>
    struct dref <T*, true>
    {
    	typedef typename dref<T>::type type;
    
    	static
    	inline
    	type &
    	get(T * value)
    	{
    		return dref<T>::get(*value);
    	}		
    };
    
    template <class T>
    inline
    typename dref<T>::type &
    dereference(T & value)
    {
    	return dref<T>::get(value);
    }
    Notice the second template parameter which would allow the mechanism to be 'switched off' in the (unlikely) event that the actual data *is* the pointer. Here is a test program illustrating how the template would be used:

    Code:
     
    #include <iostream>
    using namespace std;
    
    template <class T>
    void
    print(T array[], size_t size)
    {
    	for(size_t i = 0; i < size; ++i)
    	{
    		cout << dref<T>::get(array[i]) << endl;
    	}
    }
    
    int
    main(void)
    {	
    	const size_t size = 5;
    	int 
    		values[size] 
    		= { 5, 10, 15, 20, 25 }, 
    		* p_values[size] 
    		= { &values[0], &values[1], &values[2], &values[3], &values[4] },
    		** p_p_values[size] 
    		= { &p_values[0], &p_values[1], &p_values[2], &p_values[3], &p_values[4] };
    	print(values, size);
    	print(p_values, size);
    	print(p_p_values, size);
    	return 0;
    }
    another example:

    Code:
    #include <list>
    #include <iostream>
    #include <cassert>
    
    using namespace std;
    
    template <class Iterator, class Type>
    Iterator
    find_(Iterator it, Iterator end, const Type & value)
    {
    	while(it != end)
    	{
    		if(dereference(*it) == value)
    		{			
    			return it;
    		}		
    		++it;
    	}	
    	return it;
    }
    
    int
    main(void)
    {	
    	const int size = 5;
    	int values[size] = { 5, 10, 15, 20, 25 };
    	list <int*> pointers;
    	for(int i = 0; i < size; ++i)
    	{
    		pointers.push_back(&values[i]);
    	}
    	assert(find_(pointers.begin(), pointers.end(), 15) != pointers.end());
    	assert(find_(pointers.begin(), pointers.end(), 21) == pointers.end());	
    	return 0;
    }
    Is this something that should be considered for future versions of the standard?
    Last edited by Sebastiani; 04-23-2006 at 06:12 AM. Reason: formatting, additions, inlining
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    The standard approach is to have the user supply special-purpose function objects for comparison and assignment, adding unnecessary redundancy, bloat, and function-call overhead to otherwise simple tasks.
    From what I understand, the use of function objects actually gives compilers more opportunity to inline the code, hence function objects often do not impose a function call overhead. I think this is the reason why std::sort() is cited as often having better performance than qsort().
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Code size is not the most compelling reason for implementing such a framework. The real issue is code reuse. Automatic dereferencing would make generic algorithms even more universal by eliminating the need (in most cases) to supply storage-specific routines to access data. Obviously, the mechanism would need to be extended (overloaded) to work with certain 'handle' classes (such as std::auto_ptr), but this would be done within their respective implementations.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Attached is the latest version. I've decided to submit the library to Boost once the documentation and testing phases are complete. Any comments/suggestions?

    Below is an example of specializing the template for std::auto_ptr:

    Code:
    #include <iostream>
    #include <string>
    #include <memory>
    #include "dref.hpp"
    
    BOOST_DREF_SPECIALIZE(T, std::auto_ptr<T>);
    BOOST_DREF_SPECIALIZE(T, const std::auto_ptr<T>);
    
    int
    main(void)
    {		
    	typedef std::auto_ptr<std::string> ap_string;
    	std::auto_ptr<ap_string> ptr(new ap_string(new std::string("seek")));
    	std::cout << boost::dref::get(ptr) << std::endl;
    	boost::dref::get(ptr) += " and ye shall find";
    	std::cout << boost::dref::get(ptr) << std::endl;
    }
    [note]
    The file extension was changed from '.hpp' to '.cpp' for uploading purposes.
    [/note]

    [caveat]
    The specialization macro expands the declaration within the boost::dref namespace to ensure proper lookup of complex types. For this reason the macro must be declared outside of *any* namespace (including std::).
    [/caveat]
    Last edited by Sebastiani; 04-24-2006 at 01:38 AM. Reason: caveats, notes
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C Formatting Using STL
    By ChadJohnson in forum C++ Programming
    Replies: 4
    Last Post: 11-18-2004, 05:52 PM
  2. im extreamly new help
    By rigo305 in forum C++ Programming
    Replies: 27
    Last Post: 04-23-2004, 11:22 PM
  3. STL or no STL
    By codec in forum C++ Programming
    Replies: 7
    Last Post: 04-12-2004, 02:36 PM
  4. Prime Number Generator... Help !?!!
    By Halo in forum C++ Programming
    Replies: 9
    Last Post: 10-20-2003, 07:26 PM
  5. include question
    By Wanted420 in forum C++ Programming
    Replies: 8
    Last Post: 10-17-2003, 03:49 AM