8
\$\begingroup\$

I often use C API's in C++ that force me to use C-style arrays. I got sick of constantly using a dynamic vector with &vec[0], so I wrote this C-style array container. Please review and give suggestions.

I also have one question: is my implementation of swap correct? My biggest worry is swapping two C-style arrays with different allocators, will this go boom on the deallocation?

The current "demands" for the C-style array:

  • Static size, so no resize().
  • Implicitly converts to T* when needed to pass to C functions.
  • Support all of std::vector's methods, as long as they are compatible with the two demands earlier.

This is what I have:

/*
    Carray - a C++ container that resembles a C-style array very closely
    while supporting high-level methods and dynamic memory allocation.

    Description:
        A Carray is an Random Access Container (http://www.sgi.com/tech/stl/Container.html,
        http://www.sgi.com/tech/stl/RandomAccessContainer.html). The number of elements in
        a Carray is fixed and can not vary after construction. Memory management is automatic.

    Template arguments:
        Carray<typename T, typename A = std::allocator<T> >
        T is the type of each element in the array and A is the allocator
        for the array. The allocator defaults to std::allocator.
        Carray<int, std::allocator<int> >

    Constructors:
        Carray(size_t n) - create new Carray with n uninitialized elements
        Carray(size_t n, value_type newobj) - create new Carray with n elements initialized to newobj
        Carray(const Carray& carray) - copy constructor

        Example:
        Carray<int> arr(50) - Carray of 50 ints - garbage values
        Carray<int> arr(50, int()) - Carray of 50 ints - initialized to default int, 0

    Carray supports all of the associated types, members and methods described on these pages:
        http://www.sgi.com/tech/stl/Container.html
        http://www.sgi.com/tech/stl/ForwardContainer.html
        http://www.sgi.com/tech/stl/ReversibleContainer.html
        http://www.sgi.com/tech/stl/RandomAccessContainer.html
*/

/*
    Copyright 2011 Orson Peters. All rights reserved.

    Redistribution of this work, with or without modification, is permitted if
    Orson Peters is attributed as the original author or licensor of
    this work, but not in any way that suggests that Orson Peters endorses
    you or your use of the work.

    This work is provided by Orson Peters "as is" and any express or implied
    warranties are disclaimed. Orson Peters is not liable for any damage
    arising in any way out of the use of this work.
*/

#ifndef CARRAY_H
#define CARRAY_H

#include <memory> // std::allocator
#include <algorithm> // std::uninitialized_copy
#include <iterator> // std::reverse_iterator
#include <stdexcept> // std::out_of_range
#include <cstddef> // size_t && ptrdiff_t

template<typename T, typename A = std::allocator<T> > class Carray {
public:
    // types
    typedef T value_type;
    typedef A allocator_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

    typedef T* pointer; // for C
    typedef const T* const_pointer; // for C
    typedef T* iterator;
    typedef const T* const_iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    typedef T& reference;
    typedef const T& const_reference;

    // contructors
    Carray(size_type size) { // array with N uninitialized elements
        elements = size;
        data = allocator.allocate(size);
    }

    Carray(size_type size, const_reference newobj) { // array with N elements initialized to newobj
        elements = size;
        data = allocator.allocate(size);
        for (iterator it = begin(); it != end(); it++) allocator.construct(it, newobj);
    }

    Carray(const Carray<value_type>& other) { // copy constructor
        elements = other.size();
        data = allocator.allocate(elements);

        std::uninitialized_copy(other.begin(), other.end(), begin());
    } 

    Carray<value_type, allocator_type>& operator=(const Carray<value_type, allocator_type>& other) { // same as copy constructor
        elements = other.size();
        data = allocator.allocate(elements);

        std::uninitialized_copy(other.begin(), other.end(), begin());
    }

    ~Carray() {
        for (iterator it = begin(); it != end(); it++) allocator.destroy(it);
        if (data != 0) {
            allocator.deallocate(data, elements);
            data = 0;
            elements = 0;
        }
    }

    // iterators and references
    reference back() { return data[elements - 1]; }
    const_reference back() const { return data[elements - 1]; }

    reference front() { return data[0]; }
    const_reference front() const { return data[0]; }

    iterator begin() { return iterator(data); }
    const_iterator begin() const { return const_iterator(data); }

    iterator end() { return iterator(data + elements); }
    const_iterator end() const { return const_iterator(data + elements); }

    reverse_iterator rbegin() { return reverse_iterator(end()); }
    const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }

    reverse_iterator rend() { return reverse_iterator(begin()); }
    const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

    // methods
    bool empty() const { return elements == 0; }
    size_type max_size() const { return allocator.max_size(); }
    size_type size() const { return elements; }
    allocator_type get_allocator() const { return allocator; }
    void swap(Carray<value_type>& other) {
        std::swap(data, other.data);
        std::swap(elements, other.elements);
    }

    // subscripting
    reference at(size_type n) { if (n >= elements) throw std::out_of_range("Carray::at(size_type n)"); return data[n]; }
    const_reference at(size_type n) const { if (n >= elements) throw std::out_of_range("Carray::at(size_type n)"); return data[n]; }

    reference operator[](difference_type n) { return data[n]; } // difference_type to prevent ambiguity with (operator pointer())[n]
    const_reference operator[](difference_type n) const { return data[n]; } // difference_type to prevent ambiguity with (operator pointer())[n]

    operator pointer() { return data; } // implicit conversion to pointer for C support
    operator const_pointer() const { return data; } // implicit conversion to const pointer for C support

private:
    allocator_type allocator;
    pointer data;
    size_type elements;
};

// comparison operators - operator== and operator> are primitives, the rest is derived from them
template<typename T, typename A> bool operator==(const Carray<T,A>& x, const Carray<T,A>& y) {
    return x.size() == y.size() && std::equal(x.begin(), x.end(), y.begin());
}

template<typename T, typename A> bool operator<(const Carray<T,A>& x, const Carray<T,A>& y) {
    return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}

template<typename T, typename A> bool operator>(const Carray<T,A>& x, const Carray<T,A>& y) { return y < x; }
template<typename T, typename A> bool operator!=(const Carray<T,A>& x, const Carray<T,A>& y) { return !(x == y); }
template<typename T, typename A> bool operator>=(const Carray<T,A>& x, const Carray<T,A>& y) { return !(x < y); }
template<typename T, typename A> bool operator<=(const Carray<T,A>& x, const Carray<T,A>& y) { return !(x > y); }

#endif
\$\endgroup\$
  • 1
    \$\begingroup\$ I will take my stab at this design in a second, but wasn't boost::Array an option for you? \$\endgroup\$ – IAE May 18 '11 at 9:39
  • \$\begingroup\$ @SoulBeaver: Perhaps, but this was both an exercise, and I don't like the design of boost::array. For example I don't like to explicitly call data() all the time. Normally I'm fond of strict-ness, but IMO if you go as far as replacing vector with a C-style array wrapper then make it behave as a C-style array. And the size as template parameter is against my design principles for this array because I want a static-sized array, not necessarily compile-time fixed size. \$\endgroup\$ – orlp May 18 '11 at 10:20
  • \$\begingroup\$ It doesn't seem to implicitly convert to T* at the moment. Am I missing something? \$\endgroup\$ – Tim Martin May 18 '11 at 10:34
  • \$\begingroup\$ @Tim Martin: It does. It supports operator pointer() where pointer is typedef T* pointer. Try passing the Carray to a C function like strcpy (make sure you pass a Carray<char> ofc). \$\endgroup\$ – orlp May 18 '11 at 10:38
6
\$\begingroup\$

It's a subjective point, but declarations of template containers in the standard library don't use the typedefs for the template type for the rest of the declaration. For example,

template <class T, class Allocator>
class deque {
public:
   typedef T  value_type;

   //...

   void push_front( const T& x );
   // not void push_front(const value_type& x);

   //...
}

I'm used to looking for the template parameter in member function declarations, and your use of value_type etc. confused me.

Personally, I don't like the implicit conversion to T*. You need to make sure you've thought of all the cases where this could cause unexpected behaviour, e.g. in boolean contexts, arithmetic operators and with ostream::operator<<. In my opinion an extra function call on the conversion is a small price to pay for avoiding cases where code looks right, compiles and does something subtly wrong.

\$\endgroup\$
  • \$\begingroup\$ Ahh, my use of pointer confused you :) I'll think about it and look in compiler implementations too to see what the majority of library designers think and adapt to that. I like to write semantically, so for me using typedefs like const_reference and value_type are easier to understand. \$\endgroup\$ – orlp May 18 '11 at 10:52
4
\$\begingroup\$

Alright, I made a couple of minor changes:

  1. Changed ctor to use initialization list:

    Carray(size_type size) 
    : elements(size), data(allocator.allocate(size))
    {     }
    
    Carray(size_type size, const_reference newobj) 
    : elements(size), data(allocator.allocate(size))
    { // array with N elements initialized to newobj
        for (iterator it = begin(); it != end(); it++) 
            allocator.construct(it, newobj);
    }
    
    Carray(const Carray<value_type>& other) 
    : elements(other.size), data(allocator.allocate(elements))
    { // copy constructor
        std::uninitialized_copy(other.begin(), other.end(), begin());
    } 
    
  2. Rearranged members (you were initializing in the wrong order):

    allocator_type allocator;
    size_type elements;
    pointer data;
    
  3. Used the copy-and-swap idiom on your operator=:

    Carray<value_type, allocator_type>& operator=(const Carray<value_type, allocator_type>& other) { // same as copy constructor
        // This may be a short piece of code, but why not use the copy-and-swap idiom?        
        Carray<T, A> temp(other);
        swap(*this, temp);
    
        return *this;
    }
    
  4. Make your swap have the no-throw guarantee:

    void swap(Carray<value_type>& other) throw()
    

I would also like to add that your throw() in the at() functions isn't very descriptive. This probably isn't a problem, since the error is apparent from looking at the function, but why not give it a more descriptive message anyway? Then I won't even have to look at the function to know what went wrong.

EDIT

As Tim Martin pointed out, the throw() is usually bad style and should be avoided. I have included it for the swap function because of two reasons:

  1. It is usually a non-throwing swap, which is more of a semantic rather than syntactic choice. This let's the programmer know that swap should not ever throw, but it is not prevented.

  2. Quoting Herb Sutter from Exceptional C++ Item 12:

    Note that Swap() supports the strongest exception guarantee of all—namely, the nothrow guarantee; Swap() is guaranteed not to throw an exception under any circumstances. It turns out that this feature of Swap() is essential, a linchpin in the chain of reasoning about [Container]'s own exception safety.

\$\endgroup\$
  • \$\begingroup\$ Thanks, this was very helpful. I'm not known with the copy-and-swap idiom yet. But I think you meant swap(*this, temp);. And perhaps you could add some information about my swap implementation, especially about swapping between two Carray's with different allocators. \$\endgroup\$ – orlp May 18 '11 at 10:27
  • \$\begingroup\$ I'm guessing you know, but it never hurts to emphasise: the throw() annotation on the declaration doesn't prevent the function from throwing an exception, and doesn't cause the compiler to warn if the code within can throw. Sutter and Alexandrescu in C++ Coding Standards recommend against using exception specifications for this reason. \$\endgroup\$ – Tim Martin May 18 '11 at 10:54
  • \$\begingroup\$ @nightcracker: edited, and I wouldn't allow the swapping with containers that have differing allocators. An easy way to prevent this is by changing the declaration of swap to void swap(Carray<T, A>& other) throw() \$\endgroup\$ – IAE May 18 '11 at 10:55
  • \$\begingroup\$ I know it's easy to prevent. I was thinking that it might be possible to swap two Carray's with different allocators, but it was foolish. They are essentially different types. \$\endgroup\$ – orlp May 18 '11 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.