Creating a custom template container class (vector alike)

Question

What can be done better? What should I learn to make these tasks better and more efficiently?

The template (template.h):

#pragma once
#include <iostream>

template <typename TData>
class CArray
{
public:

  CArray(int capacity = 0);

  CArray(
    const CArray & _array
  );

  ~CArray();

  void push_back(
      const TData & _value
  );

  void insert(
      unsigned int  _index,
      const TData & _value
  );

  void erase(
      unsigned int _index
  );

  void clear();

  unsigned int getSize() const;

  void sortAsAscending(
      int _left,
      int _right
  );

  TData & operator[](
      unsigned int _index
      )
  {
    return buffer[_index];
  }

protected: 
  int size;
  int capacity;
  TData* buffer;

private:

  TData & print(
    unsigned int _index
  ) const
  {
    return buffer[_index];
  }

  friend std::ostream & operator<<(
    std::ostream & stream,
    const CArray<TData> & arr
    )
  {
  if (arr.getSize() > 0)
  {
        for (unsigned int i = 0; i < arr.getSize(); ++i)
        {
            stream << arr.print(i) << " ";
        }
  }
  else
  {
    stream << "The array is empty now.";
  }
    stream << std::endl;
    return stream;
  }
};

  template <typename TData>
  CArray<TData>::CArray(
      int _capacity = 0
  )
  {
    capacity = _capacity;
    size = 0;
    buffer = new TData[capacity];
  }

  template <typename TData>
  CArray<TData>::CArray(
      const CArray & _array
  )
  {
      size = _array.size;
      capacity = _array.capacity;
      buffer = new TData[capacity];
      for (unsigned int i = 0; i < size; ++i)
      {
          buffer[i] = _array.buffer[i];
      }
  }

  template <typename TData>
  CArray<TData>::~CArray()
  {
      delete[] buffer;
  }

  template <typename TData>
  void CArray<TData>::push_back(
        const TData & _value
  )
  {
    if (size >= capacity) 
    {
    int newCapacity = 1 << capacity;
    TData * newBufferForArray = new TData[newCapacity];

    for (unsigned int i = 0; i < size; ++i)
    {
     newBufferForArray[i] = buffer[i];
    }
    capacity = newCapacity;
    delete[] buffer;
    buffer = newBufferForArray;
    }
    buffer[size] = _value;
    size++;
  }

   template <typename TData>
  void CArray<TData>::insert(
      unsigned int  _index,
      const TData & _value
  )
  {
    buffer[_index] = _value;
  }

  template <typename TData>
  void CArray<TData>::erase(
      unsigned int _index
  )
  {
      TData * newBufferForArray = new TData[size - 1];

      for (unsigned int i = 0; i < _index; ++i)
      {
          newBufferForArray[i] = buffer[i];
      }

      for (unsigned int j = _index + 1; j < size; ++j)
      {
          newBufferForArray[j - 1] = buffer[j];
      }

      delete[] buffer;
      buffer = newBufferForArray;
      size--;
  }

  template <typename TData>
  void CArray<TData>::clear()
  {
      for (unsigned int i = 0; i < size; ++i)
      {
          buffer[i] = 0;
      }
  }

  template <typename TData>
  unsigned int CArray<TData>::getSize() const
  {
      return size;
  }

  template <typename TData>
  void CArray<TData>::sortAsAscending(
      int _left, 
      int _right
  )
  {
      int i = _left;
      int j = _right;
      TData tmp;
      TData pivot = buffer[(_left + _right) / 2];
      while (i <= j) {
          while (buffer[i] < pivot)
              i++;
          while (buffer[j] > pivot)
              j--;
          if (i <= j) {
              tmp = buffer[i];
              buffer[i] = buffer[j];
              buffer[j] = tmp;
              i++;
              j--;
          }
      };
      if (_left < j)
          sortAsAscending(_left, j);
      if (i < _right)
          sortAsAscending(i, _right);
  }

Testing the template in the main.cpp file:

#include <string>
#include "template.h"
#include <time.h>  

int main()
{
  std::cout << "1. Working with type INT:" << std::endl;

  CArray<int> arr;
  std::cout << arr;

  std::cout << "1.1. Adding 20 random numbers in range between 0 to 100:" << std::endl;
  srand(time(NULL));
  for (unsigned int i = 0; i < 20; ++i)
  {
      arr.push_back(rand() % 101);
  }
  std::cout << arr;

  std::cout << "1.2. Sorting elements in ascending order:" << std::endl;
  arr.sortAsAscending(0, (arr.getSize() - 1));
  std::cout << arr;

  std::cout << "1.3. Deleting every second element: " << std::endl;
  CArray<int> copiedArray;
  unsigned int counter = 0;
  while (arr.getSize() != 10)
  {
      counter++;
      arr.erase(counter);     
  }
  std::cout << arr;

  std::cout << "1.4. Inserting 10 random numbers in range 0-100 into random positions: " << std::endl;
  for (unsigned int i = 0; i < 10; ++i)
  {
      arr.insert(rand() % 10, rand() % 100 + 1);
  }
  std::cout << arr;
  std::cout << "NOTE: as positions are random, they can repeat." << std::endl;

  std::cout << "1.5. Cleaning the array up:" << std::endl;
  arr.clear();
  std::cout << arr;


  std::cout << "2. Working with type STD::STRING:" << std::endl;

  CArray<std::string> arrString;
  std::cout << arrString;

  std::cout << "2.1. Adding 15 random words with Latin letters in lower case: " << std::endl;
  static const char letterString[] = "abcdefghijklmnopqrstuvwxyz";
  std::string randomString = "";
  for (unsigned int i = 0; i < 15; ++i)
  {
      unsigned int strLength = rand() % 10 + 3;
      for (unsigned int j = 0; j < strLength; ++j)
      {
          randomString += letterString[rand() % (sizeof(letterString) - 1)];
      }
      arrString.push_back(randomString);
      randomString = "";
  }
  std::cout << arrString;
  std::cout << std::endl;

  std::cout << "2.2. Sorting string elements in ascending order: " << std::endl;
  arrString.sortAsAscending(0, (arrString.getSize() - 1));
  std::cout << arrString;
  std::cout << std::endl;

  std::cout << "2.3. Deleting words, including letters a, b, c, d, e: " << std::endl;

  unsigned int wordCounter = 0;
  unsigned int wordLength = 0;
  while (true)
  {
      if (wordCounter > arrString.getSize() - 1)
      {
          break;
      }
      else
      {
          wordLength = arrString[wordCounter].length();
      }

      for (unsigned int j = 0; j < wordLength; ++j)
      {
          if (
              arrString[wordCounter][j] == 'a' ||
              arrString[wordCounter][j] == 'b' ||
              arrString[wordCounter][j] == 'c' ||
              arrString[wordCounter][j] == 'd' ||
              arrString[wordCounter][j] == 'e'
              )
          {
              arrString.erase(wordCounter);
              wordCounter--;
              break;
          }
      }
      wordCounter++;
  }

  std::cout << arrString;
  std::cout << std::endl;

  std::cout << "2.4. Inserting 3 new random words into random positions (marked as \"newValue(value)\"): " << std::endl;
  CArray<std::string> newRandomWords;
  std::string newRandomString = "newValue";
  for (unsigned int i = 0; i < 3; ++i)
  {
      for (unsigned int j = 0; j < 5; ++j)
      {
          newRandomString += letterString[rand() % (sizeof(letterString) - 1)];
      }
      newRandomWords.push_back(newRandomString);
      newRandomString = "newValue";
  }
  for (unsigned int i = 0; i < newRandomWords.getSize(); ++i)
  {
      arrString.insert(rand() % arrString.getSize(), newRandomWords[i]);
  }
  std::cout << arrString;
  std::cout << "NOTE: inserting is provided only for existing positions (as previous step may leave less than 3 items in the object). As position is random, it can repeat." << std::endl;
  std::cout << std::endl << std::endl << "Press Enter to close the window." << std::endl;
  std::cin.get();

  return 0;
}

upd: what I already know is wrong is that 1) I put the whole template into one file (header) and I could do it differently; 2) implemented incorrectly methods insert and clear (I should have added/deleted new element(s) instead of rewriting the value); 3) possibly made quicksort too simple - should have used iterators and comparators, like in an adult C++ std version of quicksort.

Any futher comments would be greatly appreciated!

Answer 1

Violation of rule of 0/3/5, if you implement the destructor you must also provide the copy constructor and copy assign (plus optionally the move constructor and move assign).

Speaking of move, there is no advantage taken of move semantics.

You can add a const variant to the subscript overload:

  const TData & operator[](
      unsigned int _index
      ) const
  {
    return buffer[_index];
  }

It lets you avoid having the print function that does exactly the same.

Using new[] default initializes all element in the array, for some types that's a compile error, for others it's an expensive operation.

Bug in erase, it changes the capacity but doesn't update the field -> leads to overflow on next add.

Answer 2

Great try for the first time. If I would like to write vector 2 years ago, I would write it nearly the same as yours. Nevertheless, it is 2016/10/26 ...

The problem is, as you noticed, that it is not mature. I guess you've spent ~20 minutes to write this. I hope you agree with me that almost perfect piece of code, which std::vector is close to, can't be written in 20 minutes.

Do you know why std::vector will be faster than yours? It doesn't seem like there is something to change in the code, isn't it?

The answer is C++ style. What is C++ style? Templates, iterators and being friends with the machine itself (data layout, small vector optimization, hot/cold memory, fragmentation, etc). First of all, most implementations of std::vector use 2-3 pointers and possibly one std::size_t for the size. Despite that, it is not seldom true that those are the only things that are part of std::vector object, it is not even guaranteed that they will exist.

Templates? How can you make it faster with templates? You can, for example, fallback to std::memcpy(), or even better, std::realloc() (the latter can just increase the size of the current chunk, no copy, no more allocation) when the type is POD, which will certainly make it faster on the bigger sizes. You can use move constructor of the object if it's nothrow, which will probably have enormous impact. You can support custom allocators, which will provide flexibility of memory management for the user (and in fact, memory management is one of the crucial performance issues of the contiguous containers). You can just call std::free() (given that you allocated with malloc()), without invoking the destructors if the type is POD. Lots and lots of other things...

I could list all other possible optimizations, but I guess you got the point.