1

I am unable to use the STL and boost library and I have to write my own container in C++. The following code compiles without error in VC++6.

I have not actually tested the code but is concerned whether this generic container will work with both primitive and non primitive types (like class). Will there be any potential issues with the copy constructor and the assignment operator especially?

Any other suggestions and comments are most welcomed. :)

template <class T>  
class __declspec(dllexport) StdVector{

private:  
    int _pos;  
    int _size;  
    const T *_items;  

public:
    StdVector();
    StdVector(const StdVector &v);
    StdVector(int size);
    virtual ~StdVector();

    void Add(const T &item);
    void SetSize(int size);
    int GetSize();

    const T * Begin();
    const T * End();
    const T * ConstIterator();

    StdVector & operator=(const StdVector &v);
};

template <typename T>
StdVector<T>::StdVector() 
    : _pos(0), _size(0), _items(NULL){
}

template <typename T>
StdVector<T>::StdVector(const StdVector &v) 
    : _pos(0), _size(v.GetSize()), _items(new T[_size]){
    std::copy(v.Begin(), v.End(), Begin());
}

template <typename T>
StdVector<T>::StdVector(int size) 
    : _pos(0), _size(size), _items(new T[_size]){
}

template <typename T>
StdVector<T>::~StdVector(){
    if (_items != NULL)
        delete[] _items;
}

template <typename T>
void StdVector<T>::Add(const T &item){
    if (_pos == _size)
        throw new exception("Already at max size!!!");

    _items[_pos++] = item;
}

template <typename T>
void StdVector<T>::SetSize(int size){
    if (_items != NULL)
        delete[] _items;

    _pos = 0;
    _size = size;
    _items = new T[_size];
}

template <typename T>
int StdVector<T>::GetSize(){
    return _size;
}

template <typename T>
const T * StdVector<T>::Begin(){
    return _items;
}

template <typename T>
const T * StdVector<T>::End(){
    return _items + _pos;
}

template <typename T>
const T * StdVector<T>::ConstIterator(){
    return _items;
}

template <typename T>
StdVector<T> & StdVector<T>::operator=(const StdVector &v){
    if (this != &v){
        delete[] _items;
        std::copy(v.Begin(), v.End(), Begin());
    }

    return *this;
}
Lopper
  • 3,499
  • 7
  • 38
  • 57
  • 1
    If you can't use "STL", how do you have access to `std::copy`? By STL which bits of the standard library do you actually mean? – CB Bailey Nov 28 '09 at 11:20
  • I remember writing my own container types when I was a C++ beginner. It's a good exercise. – StackedCrooked Nov 28 '09 at 11:27
  • Maybe this should be made community wiki. There is not 'an answer' but rather different opinions or bits that different people will flag out. – David Rodríguez - dribeas Nov 28 '09 at 12:05
  • 2
    You say you haven't tested it, but a large number of issues would have been flagged up if you had at least compiled it - even under VC6(!). – CB Bailey Nov 28 '09 at 12:12
  • What I actually meant was that the internal implementation of the class can use STL but all the public functions that are exposed cannot contain std::vector, std::string, etc as parameters. – Lopper Nov 28 '09 at 13:28
  • 4
    In that case your best bet is to have a `std::vector` member variable and forward your public functions to this member. – CB Bailey Nov 28 '09 at 13:34
  • If you are not allowed to use std::vector in the public interface, then it is of no use to have it as an internal detail of a template. That is, I am assuming that the problem can be that different compilation units may be using different compilation parameters and as such different STL implementations (say debug/release implementations, checked vs. non-checked iterators...). In that case, having a member std::vector will hit the same problem: breaking the ODR as different compilation units will instantatiate the façade and that will instantiate different std::vector classes. – David Rodríguez - dribeas Nov 28 '09 at 13:55
  • Using std::vector as a private member of the class std::vector should work I think. I need to call a native VC++6 library from C#. However, because the native library heavily makes use of std::vector and std::string as function parameters and I don't have access to the source code, C# can't use it. So I am coming up with a wrapper dll class that encapsulates the native class and exposes no std::vector and std::string. Have a look at This thread which I posted earlier. – Lopper Nov 28 '09 at 14:25
  • The correct thread http://stackoverflow.com/questions/1806402/how-to-call-native-vc6-library-with-stdstring-as-parameters-from-c – Lopper Nov 28 '09 at 14:26
  • Perhaps I am still green in programming! Always coming up with complex (very much more complex than necessary) solutions for solving simple problems! Still, it is a good exercise. – Lopper Nov 28 '09 at 14:52

3 Answers3

5

This default constructs the new objects and assigns them (or would, if the Begin() returned T* and not const T*, see dribeas' answer), it might be more efficient if you used raw storage and constructed the new objects in place. Also as GetSize(), Begin() and End() aren't const they can't be called on the parameter v.

template <typename T>
StdVector<T>::StdVector(const StdVector &v) 
    : _pos(0), _size(v.GetSize()), _items(new T[_size]){
    std::copy(v.Begin(), v.End(), Begin());
}

The if statement is redundant. delete[] on a NULL pointer is fine. Also, is there any point to it being virtual? It doesn't look like this is a class designed to be derived from.

template <typename T>
StdVector<T>::~StdVector(){
    if (_items != NULL)
            delete[] _items;
}

SetSize destroys all the objects and creates new ones. This may be 'surprising' behaviour. Also, if the new throws, the object will be left pointing at deallocated memory. Again, the if guarding the delete is redundant.

template <typename T>
void StdVector<T>::SetSize(int size){
    if (_items != NULL)
            delete[] _items;

    _pos = 0;
    _size = size;
    _items = new T[_size];
}

What's the point of this? It appears to do the same as Begin. It's not even a const method.

template <typename T>
const T * StdVector<T>::ConstIterator(){
    return _items;
}

Doesn't this attempt copy to _items which has just been deleted (again see the points about Begin() returning const T* and about Begin() and End() not being const)?

template <typename T>
StdVector<T> & StdVector<T>::operator=(const StdVector &v){
    if (this != &v){
        delete[] _items;
        std::copy(v.Begin(), v.End(), Begin());
    }

    return *this;
}

What exception class is this? std::exception doesn't have a constructor that takes a const char*. You should also throw exception objects, not pointers to dynamically allocated exception objects. Cleaning up dynamically allocated exceptions which are 'thrown' by pointer is almost impossible to do robustly.

template <typename T>
void StdVector<T>::Add(const T &item){
    if (_pos == _size)
            throw new exception("Already at max size!!!");

    _items[_pos++] = item;
}
CB Bailey
  • 755,051
  • 104
  • 632
  • 656
  • I am most grateful for pointing out in detail the various bugs in the code. Would it be possible for you to give a sample code on how you would go about implementing the StdVector class in C++? – Lopper Nov 28 '09 at 13:22
  • Can you also give example code of what you meant by "it might be more efficient if you used raw storage and constructed the new objects in place" – Lopper Nov 28 '09 at 13:34
  • I've made the mistake of using std::exection(const char*) constructor as well. It is an optional (and set by default) non-standard extension on Microsoft compilers. – StackedCrooked Nov 28 '09 at 14:21
5

There are a couple of things in the code. I still cannot understand why using STL is prohibited in some environments, when it is throughly tested and rather inexpensive (when including STL or any other templated code you only compile the parts you use)... This forces people into reinventing the wheel and more often than not it ends up with rough corners.

I would start discussing why the STL is prohibited, and try to work out a library that is allowed before (consider Electronic Arts version of the STL if the decision is on performance, consider STLPort if they don't trust VC6 STL implementation). It takes quite a lot of effort and knowledge to develop anything close to STL in quality.

Now to your container. First you want to start by defining your class requirements, what operations you want to perform on the vector and its elements. The limitations on your code as it is are:

  • stored elements are constant: they cannot be changed
  • you cannot remove elements from the vector
  • your resize operation will destroy all stored elements, it cannot grow/shrink non-destructively (I am not sure whether this is an interface limitation or a problem with the implementation you provided)

Some particular things with your code:

  • Copy initialization and assignment are impossible: the storage is const T*, so it cannot be changed after construction.
  • Even if it were possible, assignment is not exception safe
  • All elements (used or not) in the vector are constructed (you are paying for construction of non-used elements)
  • All one-argument constructors (but copy constructor) should be explicit to avoid unwanted implicit conversions.
  • GetSize and the methods returning iterators should be constant.

Some side notes... you are not allowed to use STL but you are allowed to use std::copy that is part of the STL? What parts of the STL are out of limits?

David Rodríguez - dribeas
  • 204,818
  • 23
  • 294
  • 489
  • Good spot on the `const T` storage. – CB Bailey Nov 28 '09 at 11:50
  • What I actually meant was that the internal implementation of the class can use STL but all the public functions that are exposed cannot contain std::vector, std::string, etc as parameters. – Lopper Nov 28 '09 at 13:31
  • For those that are voting this question up: there are many issues in Charles Bailey answer that are not identified here (such as the issue with the exception, unneeded checks for null before deleting a pointer), do read his answer. – David Rodríguez - dribeas Nov 28 '09 at 14:05
2

A few quick remarks:

  1. You should write unit tests.
  2. operator= will crash at the std::copy statement
  3. Performance issue: new T[_size] will cause the default constructor to be called _size times. You should also not require T to have a default constructor.
  4. The mechanism with SetSize is weird. You should try to model std::vector's behavior by expanding the size when needed.

Bonus: you may want to check out Stepanov's lecture notes (pdf) for Adobe. The first few chapters are about the design of a vector class.

StackedCrooked
  • 34,653
  • 44
  • 154
  • 278