So this is my first question. I've searched the site, found something and applied the suggestions given in them but I'm still unsure if I've done it the right way.
I'm working on a template library and here's my implementation of BST class template:
template <class T>
class bstree
{
private:
struct bstnode
{
bstnode* pRight; //node to the right (greater)
bstnode* pLeft; //node to the left (lesser)
bstnode* pParent; //parent node
T mValue; //contents
};
class bstnodeiterator : public _iterator_base<T, bstree<T>>
{
public:
bstnodeiterator(bstnode* pNode = nullptr, bstree<T> pCont = nullptr)
: _mpNodePtr(pNode), _mpCont(pCont) {}
//functions from _iterator_base<>
bool is_null() const { return (_mpNodePtr == nullptr); }
const bstree<T>* get_container() const { return this->_mpCont; }
//get_pointer() is intentionally not defined.
//operators (e.g. increment, decrement, advance by, dereference, etc)
//go here!
//...
private:
friend class bstree<T>;
//member elements:
bstree<T>* _mpCont; //the container that the iterator is created by
bstnode* _mpNodePtr; //the actual pointer pointing to the bst-node of '_mpCont'
};
public:
using val = T;
using val_ref = T&;
using val_ptr = T*;
using iter = bstnodeiterator;
public:
iter begin() const;
iter end() const;
//other public member functions (e.g. insert(), remove(), etc.) go here!
//...
private:
bstnode* _mpRoot; //The root node of the BST
size_t _mSize; //The number of elements in the container (guaranteed O(1))
};
bstnodeiterator::get_container() and bstnodeiterator::is_null() are derived from iterator_base<> which is a base class of iterators for all the other containers (e.g. vector<>, fixed_list<>, map<>, etc):
template <class T, class Cont>
struct _iterator_base
{
virtual bool is_null() const = 0;
virtual const Cont* get_container() const = 0;
/*virtual*/ const T* get_pointer() const /* = 0*/;
};
//is_null() and get_container() should be defined in derived classes
//because they are used everywhere in the library!
iterator_helper class, etc). Since a BST is a container of sorted elements, the contents of a node should not be changed dynamically. Because this will break the sorted structure of the tree. Thus, I want to prevent the programmer to use get_pointer(). Even if it returns a const pointer to the contents it can still be changed via member functions of T (For example, if T is a std::string then the contents can be changed via std::string::assign()) and I don't want this.
So, I made the function _iterator_base<*,*>::get_pointer() non-virtual in the base class. And it's not defined in the derived class, bstnodeiterator. So, if the programmer calls it from the derived class ...
bstree<std::string> strTree = { "a string", "another string", "yet another string", "test string" };
//inserted some other elements
bstree<std::string>::iterator it = strTree.begin();
//*it = "something else"; --> this won't work, because read-only dereferencing is allowed in the class.
it.get_pointer()->assign("something else"); //this will break the tree.
... then the compiler will give a linkage error: unresolved external symbol " ... ::get_pointer()".
Is this the correct way? What do you think?
EDIT:
I've just tried dereferencing and modifying:
bstree<std::string> strTree =
{
"a string",
"another string",
"yet another string",
"test string"
};
bstree<std::string>::iter it = strTree.begin();
(*it).assign("modified string"); // ----> error!
std::string pB0 = strTree.begin(); // ----> error
const std::string pB = strTree.begin();
pB->assign("modified string"); // ----> error!
...and it didn't compile. But if I change the last line with following:
it.get_pointer()->assign("modified string");
... it compiles without errors, runs, and works!
EDIT 2:
I've finally found the root of the problem: typedefs.
I didn't show the typedefs in the original question to make it look simpler and easier to read. In the original code, there is a using val_ptr = T*; under the scope of bstree<> and I'm using this typedef under the scope of bstnodeiterator:
template <class T>
class bstree
{
public:
using val = T;
using val_ref = T&;
using val_ptr = T*;
private:
class bstnodeiterator : public _iterator_base<T, bstree<T>>
{
//c'tor comes here!
const val_ptr get_pointer() { return (_mPtr ? &_mPtr->_mVal : nullptr); }
//...
};
//...
};
If I define the function as given above then I can call std::string::assign() from the returning pointer of get_pointer(). However, if I change the function's return type to const val* then I can't call string::assign().
I've finally realized that these two types are different. Probably the compiler puts the const somewhere else.
In response to OP's second edit:
Aliases are not like macros.
If you write using PtrType = T*, then const PtrType is actually
equivalent to T* const, which is a const pointer to a T object, not a pointer to a const T object. When aliases are used, further cv-qualifiers are always added on the top level. It is intuitive - if PtrType is a pointer to T, then const PtrType should be a const pointer to T.
As per the question, if you don't want users to call a virtual function, make it protected, so derived classes can implement it, but outside users cannot call it.
It is likely that you made the return type of bstnodeiterator::get_pointer() T* (instead of const T*).
You may be experiencing the pitfall of c++ covariant return types.
Both types are pointers or references (lvalue or rvalue) to classes. Multi-level pointers or references are not allowed.
The referenced/pointed-to class in the return type of Base::f() must be a unambiguous and accessible direct or indirect base class of (or is the same as) the referenced/pointed-to class of the return type of Derived::f().
The return type of Derived::f() must be equally or less cv-qualified than the return type of Base::f().
Note: c++ reference does not have the "(or is the same as)" clause, but it is added to be coherent with the standard"
So std::string* is a valid return type if the function is overriding a function with return type const std::string*.
Consider this example:
#include <string>
std::string s = "Hello, world";
struct Base {
virtual const std::string* foo() = 0;
};
struct Derived : Base {
std::string* foo() override {
return &s;
}
};
int main() {
Derived d;
d.foo()->assign("You can do this.");
return 0;
}
The above code compiles: you can modify the string pointed by d.foo() because it returns a std::string*.