operation signatures for a dictionary type

[Spur]

Hi all,

Suppose I want to implement a dictionary data structure of some kind,
say using a simple BST. I'm wondering how to express the basic
operations in the nicest manner. Especially the operations FIND, INSERT
and DELETE. I'm aware of the way STL does it, but I don't want to use
iterators.

The dictionary has a key/value structure:

template <class KEY_T, class DATA_T>
class bstree
....
....

My operations are declared as follows:

// Try to find the key in the tree. If found, a pointer
// to the data is returned, else 0 is returned
//
const DATA_T* bstree::find(const KEY_T& key)

// Insert a new key/data pair into the tree.
// True is returned if such a key already existed (and
// was replaced), false otherwise
//
bool bstree::insert(const KEY_T& key, const DATA_T& data)

// Remove a key from the tree. True is returned if such
// a key was found (and removed), false otherwise
//
bool bstree::remove(const KEY_T& key)

My biggest concern is with "find", naturally, because it
returns a pointer to the data. I couldn't use a reference
because I want to be able to test via the return value also
whether the element was found at all (now just testing the
pointer with 0).

I know there are several ways to implement it, but I wonder
at what's the best. I could, for instance, make it:

bool bstree::find(const KEY_T& key, DATA_T& data)

And return true (and fill the data) if found, false otherwise.
But this seems more cluttered to me - first because the caller
has to pass another argument, and second because it's unclear
what to place in "data" if nothing is found.

As I mentioned, STL solves these problems by using iterators.
But I want an implementation without iterators, so a constant
pointer seems like the safest way (my dictionary "owns" the
memory for the key/data, just like STL's containers do).

Any ideas ?

Thanks in advance
Eli