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?

Quote:

---

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().

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.

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]