C++ [] operator overload problem

I'm still new to C++ so I daily run into new problems.

Today came the [] operator's turn:

I'm making myself a new generic List class because I don't really like the std's one. I'm trying to give it the warm and fuzzy look of the C#'s Collections.Generic List, so I do want to be able to access elements by index. To cut to the chase:

Extract from the template:

T& operator[](int offset)
    {
        int translateVal = offset - cursorPos;

        MoveCursor(translateVal);

        return cursor->value;
    }

    const T& operator[](int offset) const
    {
        int translateVal = offset - cursorPos;

        MoveCursor(translateVal);

        return cursor->value;
    }

That's the code for the operators. The template uses "template", so as far as I saw on some tutorials, that's the correct way to do operator overloading.

Nevertheless, when I'm trying to access by index, e.g.:

Collections::List<int> *myList;
myList = 开发者_开发问答new Collections::List<int>();
myList->SetCapacity(11);
myList->Add(4);
myList->Add(10);
int a = myList[0];

I get the

    no suitable conversion function from "Collections::List<int>" to "int" exists

error, referring to the "int a = myList[0]" line. Basically "myList[0]" type's is still "Collections::List", although it should have been just int. How Come?

Since myList is a pointer myList[0] doesn't invoke operator[], it returns Collections::List<int>*. What you want is (*myList)[0]. Or better still, Collections::List<int>& myRef = *myList; and then use myRef[0] (Other option is not allocate the memory for myList on the heap, you can create it on stack using Collections::List<int> myList and then use . operator on it).

myList has type pointer to List, not List. In the case where an expression of pointer type is followed by an integral value enclosed in square brackets, (such as myList[0]), the result is identical to "add 0 to the pointer value and dereference it". The result of adding 0 to the address of the list and dereferencing it simply yields the list.

It is common for programmers used to C# and Java to overuse C++ new. In the posted example it is better to use Collections::List<int> myList; and the . operator instead of ->.

Good that you want to learn C++ and practise writing your own collections but your logic is probably flawed.

std::vector and std::deque already allow constant-time random access. std::deque is more like a list in that it allows constant-time insertion and removal at either end and does not invalidate references or iterators due to insertions.

You also seem to be mixing your collection with its iterator into one class, so that a collection contains a current position. I am pretty certain C# collections are not implemented that way.

Finally I would imagine your MoveCursor command is O(N) which means you do not really have random-access at all.

If you want fast random access and insertion time the best you can manage is O(log N) by using a tree structure, with each node on the tree indicating the number of elements in each branch below it. Thus you can find the nth element recursing down the right path. Insertion is also O(log N) as you have to recurse up the tree modifying the counts, and you will of course have to regularly balance the tree.