SimpleList - A C# to C++ comparison implementing a SimpleList is an introduction on how a very simple list class works internally, and many of the differences between C# and C++ in its implementation.
Before Starting
This article is all about understanding the basic differences in how to implement a very simple collection class in C# and in C++. It is in no-way going to present the "ultimate" list that you can use as a replacement of the standard collections, nor is it going to teach you C# or C++ standards. This article is simply trying to show the different kind of considerations a C# and a C++ developer are faced with when implementing foundation stuff, without the help of the more advanced frameworks already available in each language.
Introduction
Did you ever implement a collection class? A template or a generic class?
If you did, and you are natural with it, this article is probably not for you. You can read it and give your opinion, but I am not sure I will help you learn anything. This article is for those who either don't know generics/templates... or are going from a "high-level" language, like C# or Java, to a low(er)-level language, like C++. It really tries to show the differences in the complexities of the algorithms in each one of the languages, by using a very common case: A simple collection of items.
This collection of items is SimpleList (or maybe SimpleList<T> depending on how you see it). It is a collection like a List (for .NET)/vector (for C++) but much simpler. It is far from fully featured, so it is only expected to be used as a learning exercise.
What a SimpleList does:
- It allows items to be added
- It allows items to be accessed or modified by index
- It tries to avoid O(N) operations (slow operations) on inserts
- It can be used for different data-types with no casts
That's all!
In C#, I could easily write this class like this:
using System;
public sealed class SimpleList<T>
{
private T[] _array;
public SimpleList():
this(32)
{
}
public SimpleList(int initialCapacity)
{
if (initialCapacity < 1)
throw new ArgumentOutOfRangeException("initialCapacity", "initialCapacity must be at least 1.");
_array = new T[initialCapacity];
}
private int _count;
public int Count
{
get
{
return _count;
}
}
public int Capacity
{
get
{
return _array.Length;
}
}
public T this[int index]
{
get
{
if (index < 0 || index >= _count)
throw new IndexOutOfRangeException("index");
return _array[index];
}
set
{
if (index < 0 || index >= _count)
throw new IndexOutOfRangeException("index");
_array[index] = value;
}
}
public void Add(T value)
{
if (_count == _array.Length)
_Resize();
_array[_count] = value;
_count++;
}
private void _Resize()
{
int newCapacity = _array.Length * 2;
T[] newArray = new T[newCapacity];
for(int i=0; i<_count; i++)
newArray[i] = _array[i];
_array = newArray;
}
}
But, in C++, can I write this class as easily?
Before Continuing
I am going to do a straight conversion of this code to C++ and then try to make it more C++ "style". Also, in my first try, I am even allowing it to be bugged! You don't need to tell me the code is bugged.
Also, as C++ doesn't have properties, I am replacing properties by Get/Set methods. So Count becomes GetCount. The indexer property becomes a pair named Get() and Set(). Only near the end of the article, I would use the operator [] overload to have something more similar in usage to the indexer.
First Try: Almost Direct C# to C++ Conversion... With a Bug!
#ifndef SIMPLELIST_H_
#define SIMPLELIST_H_
#include <stdexcept>
template<class T>
class SimpleList
{
public:
SimpleList():
SimpleList(32)
{
}
SimpleList(int initialCapacity):
_capacity(initialCapacity),
_count(0)
{
if (initialCapacity < 1)
throw std::out_of_range("Invalid initialCapacity.");
_array = new T[initialCapacity];
}
~SimpleList()
{
delete[] _array;
}
int GetCapacity()
{
return _capacity;
}
int GetCount()
{
return _count;
}
T Get(int index)
{
if (index < 0 || index >= _count)
throw std::out_of_range("Invalid index.");
return _array[index];
}
void Set(int index, T value)
{
if (index < 0 || index >= _count)
throw std::out_of_range("Invalid index.");
_array[index] = value;
}
void Add(T value)
{
if (_count == _capacity)
_Resize();
_array[_count] = value;
_count++;
}
private:
T *_array;
int _capacity;
int _count;
void _Resize()
{
int newCapacity = _capacity * 2;
T *newArray = new T[newCapacity];
try
{
for (int i = 0; i<_count; i++)
newArray[i] = _array[i];
}
catch(...)
{
delete[] newArray;
throw;
}
delete[] _array;
_array = newArray;
_capacity = newCapacity;
}
};
#endif // SIMPLELIST_H_
This code works, and I even added the delete [] calls needed. If we use any of its methods, that is, Add() an item, Get() or Set() an item, ask for the actual number of items (that is GetCount()) or for the total items that can be added without an inner array resize (that is, the count stays lower or equal GetCapacity()), it will work. But it is bugged not because of what I wrote, but because of the code I didn't write.
C++ classes aren't required to be allocated using the new keyword. They can very well be allocated on the stack or directly inside other objects, with no references, and they can even behave like primitive types and allow us to use the operator = on them, reassigning their values. The problem is, by default, all classes come with a copy constructor, a move constructor, a copy assignment operator and a move assignment operator, even if we don't want them. And, for this class, this is quite bad. If we do this:
SimpleList<int> list;
SimpleList<int> list2 = list;
The code will compile, but it will crash. This happens because the auto-implemented copy constructor (and also the copy assignment operator) will simply blindly copy all the fields, which includes the pointer to an array, that we are going to destroy. The problem, both instances (list and list2) will delete the same pointer. The first delete works, and the second delete, usually, causes some kind of exception (depending on the optimizations it might not crash every time... which is known as undefined behavior).
How Do We Fix the Issue?
There are two basic answers to this problem. We implement the copy/move constructor/operators. Or we explicitly delete them.
If you download the sample and look at the SimpleList_Fix1.h file, you will see that it has those extra declarations in the private area (compared to SimpleList_Bugged.h):
SimpleList(const SimpleList<T> &) = delete;
SimpleList(SimpleList<T> &&) = delete;
SimpleList<T> &operator = (const SimpleList<T> &) = delete;
SimpleList<T> &operator = (SimpleList<T> &&) = delete;
In order, those lines say:
- Delete the (default-implemented) copy constructor
- Delete the (default-implemented) move constructor
- Delete the (default-implemented) copy assignment operator
- Delete the (default-implemented) move assignment operator
I will not enter in a discussion about this, but I really think that all of those should be deleted by default, only existing if they were explicitly declared as = default. And if we were going to do a full list implementation in C++, I should be implementing those instead of deleting them. Maybe in another article.
Is It Done?
Maybe you are laughing at my implementation. Maybe you think I am done. The reality is: This code could be done.
If we simply want a C++ version of the C# class and we don't care at all at C++ specific traits or optimizations, we are done. This class is going to work. But not only it's performance is not great, it has actual issues by the C++ standard. The first one is that this class doesn't work if an instance is received as const. In theory (and with a fix, in practice), it should be perfectly fine to call GetCount(), GetCapacity() and Get() (that is, all the Get methods) in a const typed instance.
That is, even if it makes no sense to do this, code like this should compile:
const SimpleList<int> list;
list.GetCount();
I know, this is not something we should be doing, at least not like that. But we may very well want to receive a list as input parameter, and to express our intent not to modify it, we may mark it as const, and we want it to work. So, how do we solve this?
Simple: Mark all the methods that can be called in a const instance, as "const". That is, add a const keyword just after the method declaration. Like this:
- Instead of
int GetCount(), we declare int GetCount() const; - Instead of
int GetCapacity(), we declare int GetCapacity() const; - And instead of
T Get(int index), we declare T Get(int index) const.
The Add() and Set() methods are the only public methods not declared as const. This can be seen in the Fix2 if you are looking at the sample source-code.
Now We Are Done... Right?
Maybe you know that C++ has a lot of different traits and performance optimizations. But, if we ignore that, can we say this class is "production ready" and correct?
Well... maybe production ready is already a bad expression, as production ready code usually needs to meet almost the best performance expectations (at least in the C++ world). But, ignoring performance, this class is almost right. It has only one small issue, though.
To explain the issue, I will give you this signature:
void SomeMethod(const SimpleList<int> &list);
What happens if I call SomeMethod with the following code:
SomeMethod(123);
Do you think that:
- It will compile, and call
SomeMethod with a list containing a single item, the int 123? - It will not compile. The method expects a list of
ints. We passed an int. This is clearly invalid. - It will compile... but an empty list will be received. Why?
If you don't know the answer, chose number 3. It will compile, because there's a constructor for SimpleList<T> that receives a single argument. And, in C++, when a constructor receives a single argument (or even more if they have default values), it becomes an "implicit conversion constructor".
That means that every time somebody asks for a SimpleList (by reference or not, const or not), if we pass an int, it will actually invoke the SimpleList constructor that receives an int. And instead of having a list with a single item, which can be expected to be our int number, we will have a list whose capacity is the number we gave.
I know cases where those "implicit" conversion are desirable, but I honestly don't think this is a desired "default implicit" operation or useful for any collection class at all, but this is how C++ works. So, we need to solve another issue, which is simply making the constructor that receives an int, explicit.
If you download the code and look at the source files, the only difference between Fix2 and Fix3 should be the explicit keyword before the single-parameter constructor (if there are more differences, I made some mistake).
Now We Are Done!
This is not a question. If we are talking about correctness, we are done. This code works as expected... as long as we really don't care about performance.
Considering the idea was to compare C# to C++, we already did the job of converting that C# code into C++ code. It compiles. It avoids strange behaviors from having implitit constructors, assignment operators and even implicit "value conversion" constructors that weren't really converting values.
But in this article, I decided I don't want to focus only on how to make one class from C# work in C++. I want to explore "what else" people usually think when they create the same kind of classes in different languages, and this is probably where all the beauty (or the nightmares) come from.
In C#, we don't care if copies are being made, simply because classes are hold by reference and they never do copies (the reference is copied, not the object). Also, .NET has a garbage collector, so we never explicitly delete objects and there are no double-deletions. But, did you think what happens if you use this SimpleList with a std::string? Or even with some more "fancy" types?
Immediate Initialization and Copies, Copies and More Copies
There are two major problems right now, if we want to be able to use this SimpleList efficiently with types like std::string, std::unique_ptr and others.
- Copies are done all over the place;
- All the items in the array are initialized with the default constructor, before the first
Add().
This effectively means: This class is slow if we are going to use classes that have default constructor, copy constructor, etc., which usually means we should be using pointers instead, and it also means it doesn't work at all with classes that do not have a default constructor. So, let's try and solve those problems?
Dealing with classes that do not have a default constructor is considered kinda "hacky" these days, so I will let that one for last. Yet, it is probably the best optimization we can do.
Fix 4
This fix is quite small, and I believe it is available since C++11. C++11 added some nice traits and some important performance optimizations. At the same time, it made creating list-like containers much more complicated. For our first step, we are simply going to avoid making copies of all items during a resize. Instead, we are going to move items from their previous location (the old, small array) to the new location (the new and larger array). Moves, especially for objects that contain lots of data [like a 1gb string] are much faster than a copy, and they also avoid memory-allocations, and are also expected to never throw. So, this means we change from this:
void _Resize()
{
int newCapacity = _capacity * 2;
T *newArray = new T[newCapacity];
try
{
for (int i = 0; i<_count; i++)
newArray[i] = _array[i];
}
catch(...)
{
delete[] newArray;
throw;
}
delete[] _array;
_array = newArray;
_capacity = newCapacity;
}
to this:
void _Resize()
{
int newCapacity = _capacity * 2;
T *newArray = new T[newCapacity];
for (int i = 0; i<_count; i++)
newArray[i] = std::move(_array[i]);
delete[] _array;
_array = newArray;
_capacity = newCapacity;
}
So, if now we have 1 GB in strings already in memory when we resize to add more 1KB, we will end-up with 1GB and 1KB in memory. The previous implementation would have 2GB at some point (and if it threw an exception, the old values would be kept). Now, we simply expect it to never throw (and if it does, something really bad is happening).
If you want to see the benefits of this code, try creating a small SimpleList of this class:
class CopyMove
{
public:
CopyMove() { puts("Created"); }
~CopyMove() {
if (_moved)
puts("Destructor ignored");
else
puts("Destroyed");
}
CopyMove(const CopyMove &) { puts("Copy constructed"); }
CopyMove(CopyMove &&source)
{
puts("Move constructed");
source._moved = true;
}
void operator = (const CopyMove &) { puts("Assigned a copy"); }
void operator = (CopyMove &&source)
{
puts("Assigned by moving");
source._moved = true;
}
private:
bool _moved = false;
};
This class is going to tell us everything that happens with it. Object creation, destruction, copy, move, etc. One very interesting trait is the "Destructor ignored" message. It means the object had its contents moved. I honestly wanted that the compiler avoided calling the destructor for a moved object, but it doesn't. Anyways, an object that had its contents moved, by default, has a really fast destructor compared to one that still has valid contents (or at least it is expected to have).
If we create a SimpleList of this type with its default, we will have way too many messages as, by default, 32 items are created. So, let's check what happens when the initialCapacity is 1, and we add 2 items (that is, we force a single resize).
At Fix3:
Created
Created
Assigned a copy
Destroyed
Created
Created
Created
Assigned a copy
Destroyed
Assigned a copy
Destroyed
Destroyed
Destroyed
At Fix4:
Created
Created
Assigned a copy
Destroyed
Created
Created
Created
Assigned by moving
Destructor ignored
Assigned a copy
Destroyed
Destroyed
Destroyed
To add 2 items, this is a lot, right?
What happens, right now, is that we still do lots of copies. So, at this moment, only focus in the middle, that part that says "Assigned by moving" and then "Destructor ignored".
In our current test, we had only one item in the list when it got resized, so, that item was "constructed by moving" directly into the new array. Then, the old instance was destroyed, but the destructor was "ignored" (well... not really, but it means in a real scenario it would be fast). If we had 1000 items, we would have moved 1000 items, and ignored 1000 destructors.
Yet, we can see that we still have a huge problem. Where are all those "Created" and "Assigned a copy" coming from?
The Remaining Problems - Fix 5
One of our biggest issues right now is that adding values, getting values and setting values always make copies. What's worse, we create a new value only to be added, and it gets copied during the function call to add it, then destroyed. It could be even worse if we were declaring a variable prior to the Add() call, as a new instance could be created, copied to the Add call, and copied again inside the list.
So, can we solve this?
I hope you know the answer is: Of course, we can.
This is why, in the past, most containers used const references to their input values... and since C++11 we have const references and movable references! (also named rvalue-references, xvalues-references... not sure if we should be celebrating, though, as that seems to be the biggest issue with C++ right now).
To fix this (our problem, not the C++ standard), we are going to make two overloads of the Add method. One of them will receive the value to be added as a const reference, which means it needs to be copied. But the other one will receive it as a movable reference (rvalue-reference, if you prefer), which means a move will be done.
So, we go from this:
void Add(T value)
{
if (_count == _capacity)
_Resize();
_array[_count] = value;
_count++;
}
to this:
void Add(const T &value)
{
if (_count == _capacity)
_Resize();
_array[_count] = value;
_count++;
}
void Add(T &&value)
{
if (_count == _capacity)
_Resize();
_array[_count] = std::move(value);
_count++;
}
Seems annoying to have two versions of the Add() method, that look almost alike? Don't be annoyed... it gets better (in fact, worse)! Get and Set also receive similar changes. For the Set() case, it is exactly the same idea as the Add(). The input parameter can be a reference or a movable reference (if you prefer, rvalue-reference, as this is what people usually say when talking about C++). To the Get(), though, the change is that when the SimpleList is seen as const, its const Get() will be called, returning a const reference. When it is not const, the non-const Get() will be called, returning a non-const reference. Take a look at the code if you want. It's a lot of duplication! But as I was never showing the results of Get and Sets (even if they are really important), I will show what changes by creating a SimpleList<CopyMove> with an initial capacity of 1 and add two items, using the new approach:
Created
Created
Assigned by moving
Destructor ignored
Created
Created
Created
Assigned by moving
Destructor ignored
Assigned by moving
Destructor ignored
Destroyed
Destroyed
We see more "Assigned by moving" now, and more "Destructor ignored". If I did the sample differently and didn't show any messages for the ignored cases, you would not see any messages on those cases, so we already have much less copies. Still a lot of object creations, but not as many copies.
Fix 6 - A Different Issue
So, I am sure you might be asking "can we do better?" (or maybe telling yourself: I hate C++, I would never deal with those issues). Anyways, so far I mostly ignored the Get() and Set() methods, even if I did implement them. I know they are useful, I simply had so many other things to explain that I left them untouched.
Well, after the last change, I ended up with two Get() and two Set() methods. This is not only ugly... it generates some strange behavior.
Let me explain: Before the last fix, things were like this:
T Get(int index) const
{
if (index < 0 || index >= _count)
throw std::out_of_range("Invalid index.");
return _array[index];
}
void Set(int index, T value)
{
if (index < 0 || index >= _count)
throw std::out_of_range("Invalid index.");
_array[index] = value;
}
And now they are like this:
T &Get(int index) {
if (index < 0 || index >= _count)
throw std::out_of_range("Invalid index.");
return _array[index];
}
const T &Get(int index) const
{
if (index < 0 || index >= _count)
throw std::out_of_range("Invalid index.");
return _array[index];
}
void Set(int index, const T &value)
{
if (index < 0 || index >= _count)
throw std::out_of_range("Invalid index.");
_array[index] = value;
}
void Set(int index, T &&value)
{
if (index < 0 || index >= _count)
throw std::out_of_range("Invalid index.");
_array[index] = std::move(value);
}
This duplication of methods might seem natural, considering that with move semantics and that by using references instead of copies, we want to cover all the situations. But it is actually covering too much.
Maybe the Set() needed to be duplicated, but the Get() shouldn't get duplicated... or, if it really needed to get duplicated, maybe we should get rid of the Set() altogether.
The thing is: What's the difference of a const reference and a reference? A reference can use the assignment operator (and all non const methods, but that's not my issue). That is, it can have its contents replaced. This is exactly what the Set() method does.
Well... maybe saying "exactly" is a little strong here. A Set() method could potentially do some validation, generate some events, etc. related to the collection, while a direct reference will not do that. But, in our case, we don't do any validations aside of the boundaries check. So, we can remove the Set() methods, and everything will work, if we do list.Get(someIndex) = something;.
But, to me, it looks odd to use a Get() call to then modify the object. Couldn't we do something better?
This is the moment we do our equivalent to the .NET indexer. We use the operator [].
The code for this is:
T &operator [](int index)
{
if (index < 0 || index >= _count)
throw std::out_of_range("Invalid index.");
return _array[index];
}
const T &operator [](int index) const
{
if (index < 0 || index >= _count)
throw std::out_of_range("Invalid index.");
return _array[index];
}
This replaces the Get() and Set() methods. Of course, it would be a little problematic if we did, indeed, want to execute some extra action on the Set() equivalent. But, as we don't, I will not even explore how that could be done (but yeah, it could... operator overloading can do miracles... and also cause very odd bugs... again I can say: maybe another article, not this one).
This change is the Fix6 in the download. And now, instead of doing list.Get(index) or list.Set(index, value), we do: list[index] and list[index] = value.
Dealing with Classes with no-default Constructor
This is probably the most important optimization of all... and I left it to the near end because it is possibly the less accepted one, by the new "standards".
Could you count how many casts I did so far? If you couldn't, this might mean that either you are not paying attention, or you didn't see any, so you don't know what I am talking about.
So far, I didn't use any casts at all. Thanks to the templates, a SimpleList<int> and a SimpleList<std::string> can very well exist with no issues, and neither one needs cast. So, why am I asking that right now?
Because the ultimate optimization involves casts! Well... at least the way I did it... maybe there's a helper function somewhere that could hide the cast from me.
The problem of the new T[] syntax is that if a class has a default constructor, it would be invoked. The SimpleList has a capacity of 32 items if created without specifying the initial capacity, and that means initializating 32 items with the default constructor. This also means that classes with no default constructor can't be used by the solutions presented so far.
But did you ever try to use a std::vector with a class with no default constructor? It works. So, how do they do that?
The entire solution is simple: Instead of allocating an array of items of type T, we allocate an array of bytes large enough to hold items of type T at the amount we want. But this means:
- We need to allocate memory, not items;
- We need to be able to initialize items in a random area of memory, without allocating memory;
- And, of course, we need the opposite steps. Being able to destroy an object in a random area of memory, and then delete the memory cleanly.
Can we do that?
In C++, yes. This means that we should allocate memory, not objects (so, either use malloc or new char[]... STL would use an extra template parameter named Allocator to decide that) with the size necessary to hold all objects (capacity * sizeof(T)), then we need to initialize objects using the placement new (things like new (memoryAddress)(arguments)) and also to remember all those things when doing resizes, delete, etc.
Doing this is ugly from a C++ viewpoint (or from any Object Oriented viewpoint, in my opinion). I used things like...
_array = (T *)new char[sizeof(T) * initialCapacity];
new (&newArray[i]) T(std::move(item));
... to achieve this. It breaks all the good object oriented concepts, encapsulation, etc. But this allowed me to run the sample that generated all those Created, Destroyed calls, like this:
Created
Move constructed
Destructor ignored
Created
Move constructed
Destructor ignored
Move constructed
Destructor ignored
Destroyed
Destroyed
This still looks bad, right?
While for the previous examples using a single resize was better than initializing 32 items (which I never showed, but would start with at least 32 allocations and will end with 32 deallocations), the new code looks better with no resizes:
Created
Move constructed
Destructor ignored
Created
Move constructed
Destructor ignored
Destroyed
Destroyed
That's still not perfect. Why isn't it simply 2 Created and 2 Destroyed values?
The answer is because we need to create the new values before adding them. Can't we solve this?
Sure... that's why I added the method: AddNew() to the class.
While the Add() method needs an instance to exist already (and either copies or movies it), the AddNew() creates the instance directly inside the list.
So, by using it, this is how the result looks like:
Created
Created
Destroyed
Destroyed
This is great, isn't it? For 2 items, we have exactly 2 creations and 2 destructions. That's what I expected since the beginning.
And the best of all is that now we support classes that don't have a default constructor. I am not going to present a sample for this, but this opens lots of possibilities.
But, be warned if you try to pass a solution like this (Fix7) in most companies, other developers would probably never accept your changes. They will not see the improvement in memory allocation/deallocation and how many copy/move operations were avoided. They would only see that you allocated the wrong data-type, did casts, used a strange form of new and also explicitly invoked destructors. And all those things, which were common in the 90s, are now forbidden in most places.
If you are interested in the AddNew, the following code shows how it is implemented. It is a template with "variadic" arguments. That means it can receive from zero to many arguments to match the actual constructor of type T:
template<class... TArgs>
T &AddNew(TArgs... args)
{
if (_count == _capacity)
_Resize();
T *address = &_array[_count];
new (address) T(args...);
_count++;
return *address;
}
Is There a Fix 8?
To the original purpose of the article... the answer is maybe. But don't you think last fix, involving casts, allocating an array of bytes instead of objects and then using the placement new hacky enough? It was definitely worth it (at least in my opinion) but hacky already.
But if your answer is really a "No, it was not hacky enough.", then there are more things that we can do to improve performance. But some of them work on very specific scenarios. One of them is to not allocate memory if the number (and size) of items is small enough (like zero, or 1, 2, etc.). The trick here is: You don't need to allocate any memory, if you can put the new items directly into the SimpleList memory. For example, a SimpleList<char> in a 64-bit computer, could use the _array address itself as a place-holder for up to 8 items before any memory allocations.
What people that use this solution also do is to actually make the object even a little larger, so it could store up to 16 chars (or some minimum number of items) without allocation. To me, those optimizations sometimes become a shoot-in-the-feet, as they make allocating small collections faster, but add extra "ifs" for large collections per Add(), Get(), Set() and during the resize and destruction. Also, the code starts to become harder and harder to understand. I simply decided not to go into that path in this article. Feel free to try if you want.
Alternative Evolution?
OK. If you look the code, there is a Fix8 and even a Fix9. But it doesn't fix anything covered in the C# code so far. It covers something else, which in C# is the support for the foreach keyword. In C++, the "equivalent" is called "range-based" loops.
In C#, the smallest implementation would be to add a GetEnumerator method that returns an IEnumerator<T>. Like this:
public IEnumerator<T> GetEnumerator()
{
for(int i=0; i<_count; i++)
yield return _array[i];
}
Quite simple, isn't it? Some people may actually think that I forgot to implement IEnumerable<T> but I didn't. I simply don't need to implement it to add the support for the foreach keyword. It might be useful to support LINQ, but is not necessary to support the foreach.
So, how can I do the same in C++?
The simplest solution is to add a begin() and an end() method. begin() should return an iterator for the first item (that is, index 0), while end() should return an iterator just after the last index.
So, what is an iterator? It is an object that when dereferenced returns a reference to the item where you are at, and that can be incremented, decremented, etc. The simplest iterator of all is actually a pointer. So, this is what Fix8 does:
const T *begin() const
{
return &_array[0];
}
T *begin()
{
return &_array[0];
}
const T *end() const
{
return &_array[_count];
}
T *end()
{
return &_array[_count];
}
If you think it is annoying to declare both const and non-const versions of the method, I agree with you.
By simply doing this, we already support the range-based for. That is, we can enumerate all items of the list with something like this:
for (auto &value : list)
{
}
This works perfectly with the for keyword and would not cause us any issues if we don't modify the list (that is, don't Add() inside the for). Note that modifying the items in the list is not an issue and, considering we don't support removal of items, we will never have an end() that's beyond the end because some items were removed. Yet we might have real issues if we Add() items during the iteration, as during a resize the array with all the items is gone, but the "iterator" will still be pointing to the address inside the old and deleted array.
You might say that's OK. We aren't supposed to Add() items during the iteration. But check what happens in the C# implementation. The iterator will keep iteratig until it reaches the end of the list, even when resizes happen. In fact, it will not stop at the original Count.
The C++ implementation, on the other hand, will stop on the original count even when items were added, as long as there was no resize, as with a resize you will probably have an access violation (probably, not guaranteed).
Can we do better?
Well... we could make the C# implementation stop at the original Count, if we think that would be better (or simply to have parity with C++). To do that, it is enough to change the implementation to:
public IEnumerator<T> GetEnumerator()
{
int count = _count;
for(int i=0; i<count; i++)
yield return _array[i];
}
By doing this, we store the original count and, independently if the real count changes, we only iterate until the count we stored. To be honest, this is only safe because we don't remove items, if we were able to remove items, we would need to check both the original count and the new count (and maybe we should simply give errors as a way to avoid iterating over the same item again). Anyways, I think this is not the real point. Let's come back to the C++ solution: Can we do better?
Fix 9: Implement Safe Iterators!
So, remember that I talked about how pointers can be iterators? They can be iterators because they can be dereferenced, they can be incremented and compared to each other (the comparison to end()). So, we can create classes that do the same, but in a safer way.
The solution is here:
iterator begin()
{
return iterator(*this, 0);
}
iterator end()
{
return iterator(*this, _count);
}
const_iterator begin() const
{
return const_iterator(*this, 0);
}
const_iterator end() const
{
return const_iterator(*this, _count);
}
We return iterator objects from begin() and end() now, but how are they implemented?
Probably there's a simpler way with helper objects, but I did it from scratch:
class iterator
{
public:
iterator(SimpleList<T> &list, int index):
_list(list),
_index(index)
{
}
T &operator *()
{
return _list[_index];
}
const T &operator *() const
{
return _list[_index];
}
bool operator == (const iterator &other) const
{
if (_index < 0 || _index >= _list._count)
{
return other._index < 0 || other._index >= _list._count;
}
return _index == other._index;
}
bool operator != (const iterator &other) const
{
return !(*this == other);
}
iterator &operator ++() {
_index++;
return *this;
}
iterator operator ++(int) {
iterator temp = *this;
++*this;
return temp;
}
iterator &operator --() {
_index--;
return *this;
}
iterator operator --(int) {
iterator temp = *this;
--*this;
return temp;
}
iterator& operator +=(int value)
{
_index += value;
return *this;
}
iterator& operator -=(int value)
{
_index -= value;
return *this;
}
private:
SimpleList<T> &_list;
int _index;
};
class const_iterator
{
public:
const_iterator(const SimpleList<T> &list, int index):
_list(list),
_index(index)
{
}
const T &operator *() const
{
return _list[_index];
}
bool operator == (const const_iterator &other) const
{
if (_index < 0 || _index >= _list._count)
{
return other._index < 0 || other._index >= _list._count;
}
return _index == other._index;
}
bool operator != (const const_iterator &other) const
{
return !(*this == other);
}
const_iterator &operator ++() {
_index++;
return *this;
}
const_iterator operator ++(int) {
iterator temp = *this;
++*this;
return temp;
}
const_iterator &operator --() {
_index--;
return *this;
}
const_iterator operator --(int) {
iterator temp = *this;
--*this;
return temp;
}
const_iterator& operator +=(int value)
{
_index += value;
return *this;
}
const_iterator& operator -=(int value)
{
_index -= value;
return *this;
}
private:
const SimpleList<T> &_list;
int _index;
};
I know. It is a huge code. But effectively what those iterators do is: They hold a reference to the list and an index.
So, the begin() result will always be pointing at index 0, independently if resizes happen. It doesn't hold a reference to the address of item 0. It holds a reference to the list and knows that it is index 0. So, if the list is still alive, everything should be fine.
Also, to make things extra safe, I made the comparison between two invalid addresses to return as equal, even if they point to different addresses. That means that if we manually increment or decrement the values past end() (which is a common mistake), a comparison to see if it ended will return true.
Is this the right way to do things? Maybe that extra check for safety would be considered bad by C++ standards (lately, things are either safe or unsafe, and iterators are expected to be safe when using for but unsafe if incremented manually and not-checked), as the idea is that people need to learn how to check for the end().
About having the safe iterators instead of pointers? It actually brings "iteration stability" even when adding items during the iteration and having resizes, which can be considered a really desirable trait.
Did you get tired of reading so much code? Well... I actually got tired of writing that much code to have the same kind of stability I had in C#.
Maybe I should have stopped earlier, but my purpose was really to show how many more things a good C++ implementation of a simple list needs to deal with. I am not trying to say C++ is bad, but achieving high standard quality in C++ is a completely different thing than doing the same in C#, Java... and obviously non-statically typed languages.
Possibly the new steps now are to actually follow the real C++ standard. Considering we have begin() and end() now, maybe I should rename the class to simple_vector, rename the Add() method to push_back(), the GetCount() to size()... and I think you got the idea.
Conclusion
C++ really has lots of optimizations to offer that we don't see in other languages. Yet, so many optimizations made it really complicated to implement something as simple as a SimpleList right. Also, as a personal opinion, I don't like names like push_back. add() makes much more sense in my mind (if I used lower_case names at all... I still prefer CamelCase names). Yet, I am not going to discuss that as I am not discussing actual standards in this article.
I hope you have enjoyed the article or, if you didn't, that you at least learned something new[].
