Sorted vector/set class that works with simple types (char, int, double, etc...)

Question

I'm new to C++ (approx. 3 months) and have just read Stroustrup's Programming Principles and Practice. Previously used Python a lot.

As an exercise I tried to implement a custom container, with the following requirements:

1. Data Stored continuously in memory as an array (No linked lists or trees)

2. Dynamically Allocated (std::allocator)

3. Inherently Sorted, but accepting a custom functor to sort the elements.

4. Insert elements in right sorted place;

5. Allows duplicate elements, although easy to deduplicate;

Basically a mix of std::vector and std::set, but as I am using an array to store elements it will be more expensive to insert elements, but quick to search using binary_search, etc... Just an exercise, not trying to reinvent the wheel.

That said, i have the following code that works great so far. I can make SortedVectors with types int, double, char, bool, string literals (const char*) and even vector of vectors (ex.: SortedVector< SortedVector<int> > ) to work as matrix. (However, I cannot use std::string or other complicated types in the container, or I get segfaults.)

Is the design right or should I make it different?

Here's the code I would greatly appreciate to have reviewed.

#ifndef _SORTED_VECTOR_HPP
#define _SORTED_VECTOR_HPP

#include <functional>
#include <memory>
#include <initializer_list>
#include <algorithm>
#include <iostream>


namespace homebrew {

struct out_of_range {}; //exceptions
struct elem_not_found {};

// SortedVector<type, sort_functor, allocator>    
template<typename T, typename S = std::less<T>, typename A =std::allocator<T>>
class SortedVector {
public:
    using size_type = unsigned long;
    using value_type = T;
    using iterator = T*;
    using const_iterator = const T*;

    explicit SortedVector(size_type s, T val)
        : sz{s}, elem{alloc.allocate(s)}, space(s)
        {
            for (size_type i=0; i<sz; ++i) alloc.construct(&elem[i], val);
        }

    explicit SortedVector(size_type s)
        : sz{0}, elem{alloc.allocate(s)}, space{s} {}

    SortedVector() // default constructor
        : sz{0}, elem{nullptr}, space{0} {}

    SortedVector(std::initializer_list<T> lst) // Initializer list constructor
        : sz{lst.size()}, elem{alloc.allocate(lst.size())}, space{lst.size()}
    {
        std::copy(lst.begin(), lst.end(), elem);
        std::sort(elem, elem+sz, functor);
    }

    SortedVector(const SortedVector& arg) // copy constructor (SortedVector v1 = v) -> need deep copy
        : sz{arg.sz}, elem{alloc.allocate(arg.sz)}, space{arg.sz}
    {
        for (size_type i=0; i<arg.sz; ++i) alloc.construct(&elem[i], arg.elem[i]);
    }

    SortedVector& operator=(const SortedVector& arg) //copy assignment -> need deep copy
    {
        if (this == &arg) return *this;  //self assignment, return

        if (arg.sz <= space) {  //enough space, no need for reallocation
            for (size_type i=0; i<arg.sz; ++i) alloc.construct(&elem[i], arg.elem[i]);
            sz = arg.sz;
            return *this;
        }

        T* p = alloc.allocate(arg.sz);
        for (size_type i=0; i<arg.sz; ++i) alloc.construct(&p[i], arg.elem[i]);
        for (size_type i=0; i<sz; ++i) alloc.destroy(&elem[i]);  //deallocate
        alloc.deallocate(elem, sz);                              //old space
        elem = p;
        space = sz = arg.sz;
        return *this;
    }

    SortedVector(SortedVector&& arg)  //move constructor
        : sz{arg.sz}, elem{arg.elem}, space{arg.sz}  // move elem to new owner
    {
        arg.sz = 0; //empty the source
        arg.elem = nullptr;
    }

    SortedVector& operator=(SortedVector&& arg)  //move assignment (move arg to this vector)
    {
        for (size_type i=0; i<sz; ++i) alloc.destroy(&elem[i]);
        alloc.deallocate(elem, sz);
        elem = arg.elem;
        space = sz = arg.sz;
        arg.elem = nullptr;
        arg.sz = arg.space = 0;
        return *this;        
    }

    ~SortedVector() //destructor
    {
        for (size_type i=0; i<sz; ++i) alloc.destroy(&elem[i]);
        alloc.deallocate(elem, sz);
    }

    // Checked access (cannot assign - would loose sort)
    const T& at(size_type n) const
    {
        if (n<0 || n>=sz) throw out_of_range();
        return elem[n];
    }

    //unchecked access (only access, cannot assign)
    const T& operator[](size_type n) const { return elem[n]; }

    size_type size() const noexcept { return sz; }
    size_type capacity() const noexcept { return space; }
    value_type* data() noexcept { return elem; }
    const value_type* data() const noexcept { return elem; }
    bool empty() const noexcept { return sz == 0 ? true: false; }
    const iterator begin() const noexcept { return elem; }
    const iterator end() const noexcept { return elem == nullptr ? nullptr: elem + sz;}
    const iterator back() const noexcept { return elem==nullptr ? nullptr: elem + sz - 1;}
    const iterator front() const noexcept { return elem==nullptr ? nullptr: elem;}

    void reserve(size_type newalloc) //change memory size (never decrease)
    {
        if (newalloc <= space) return;
        T* p = alloc.allocate(newalloc);
        for (size_type i=0; i<sz; ++i) alloc.construct(&p[i], elem[i]);
        for (size_type i=0; i<sz; ++i) alloc.destroy(&elem[i]);
        alloc.deallocate(elem, sz);
        elem = p;
        space = newalloc;
    }

    //You insert, but the position is determined by the functor sort
    void insert(const T& val)
    {
        if (space == 0) reserve(12);
        else if(space <= sz) reserve(space * 2);

        auto lowerBound = std::lower_bound(elem, elem+sz, val, functor);

        //first copy last element into uninitialized space
        alloc.construct(elem+sz, *back());
        ++sz;
        for (auto pos = end()-1; pos !=lowerBound; --pos) //shift
            *pos = *(pos - 1);
        alloc.construct(lowerBound, val); //insert the val
    }

    void insert(std::initializer_list<T> lst)
    {
        for (auto& obj: lst) this->insert(obj);
    }

    void insert_unique(const T& val)
    {
        if (!contain(val)) insert(val);
    }

    void insert_unique(std::initializer_list<T> lst)
    {
        for (auto& obj: lst) {
            if (!this->contain(obj)) this->insert(obj);
        }
    }

    void erase(const T& val)
    {
        auto pp = std::upper_bound(elem, elem+sz, val, functor);
        if (pp == begin()) throw elem_not_found();
        else if (pp == end()) {
            if (val == *back()) {
                alloc.destroy(back());
                --sz;
                return;
            }else throw elem_not_found();
        }

        alloc.destroy(pp-1);
        for (auto pos = pp-1; pos != end()-1; ++pos)
            *pos = *(pos+1);

        --sz;
    }

    void erase(std::initializer_list<T> lst)
    {
        for (auto& obj: lst) this->erase(obj);
    }

    void erase(iterator position)
    {
        alloc.destroy(position);
        while (position != end()-1) {
            *position = *(position+1);
            ++position;
        }
        --sz;
    }

    void erase(iterator first, iterator last) //erase a range of elements
    {
        int shift = 0;
        for (iterator i = first; i != last; ++i) {
            alloc.destroy(i);
            ++shift;
        }

        for (iterator i = first; i != end()-shift; ++i) {
            *i = *(i + shift);
        }
        sz -= shift;
    }

    void clear()
    {
        for (size_type i=0; i<sz; ++i) alloc.destroy(&elem[i]); //destroy but keep memory allocated
        sz = 0;
    }

    bool contain(const T& arg)
    {
        return std::binary_search(elem, elem+sz, arg, functor);
    }

    size_type count(const T& arg)
    {
        size_type temp = 0;
        for (size_type i=0; i<sz; ++i) {
            if (arg == elem[i]) ++temp;
        }
        return temp;
    }

    void deduplicate()
    {
        //erase(std::unique(begin(), end()), end()); -> Faster??
        for (size_type i=0; i<sz; ++i) {
            while (count(elem[i]) > 1) {
                erase(elem[i]);
            }
        }
    }

    SortedVector<T, S, A>& operator+=(const SortedVector<T, S, A>& rhs)
    {
        for (auto& obj: rhs) this->insert(obj);
        return *this;
    }

    SortedVector<T, S, A>& operator-=(const SortedVector<T, S, A>& rhs)
    {
        for (auto& obj: rhs) this->erase(obj); //Beware it throws if you try to remove
        return *this;                          // a non-existent element
    }


private:
    size_type sz;
    size_type space;
    A alloc;
    T* elem;
    S functor;

}; // class SortedVector

template<typename T, typename S, typename A>
inline SortedVector<T, S, A> operator+(SortedVector<T, S, A> lhs, const SortedVector<T, S, A>& rhs)
{
    lhs += rhs;
    return lhs;
}

template<typename T, typename S, typename A>
inline SortedVector<T, S, A> operator-(SortedVector<T, S, A> lhs, const SortedVector<T, S, A>& rhs)
{
    lhs -= rhs;
    return lhs;
}

template<typename T, typename S, typename A> // to cout and easy my debugging with std types
std::ostream& operator<<(std::ostream& os, const SortedVector<T, S, A>& vec)
{
    os << "[";
    for (auto i = vec.begin(); i != vec.end(); ++i) {
        os << *i;
        if (i == vec.end() - 1) { os << "]"; } else { os << ", "; } // x ? y:z operations didnt work. why?                                                       
    }
    os << "\n";
    return os;
}

} //namespace homebrew

#endif //_SORTED_VECTOR_HPP

Answer 1

"Personally": I like putting private member variables at the top of the class.
That way when I start reading the constructors I can easily refer to all the member variables (as they are beside the constructor) and not have to scroll down 500 lines to see which members have not been initialized.

size_type sz;
size_type space;
A alloc;
T* elem;
S functor;

I would note that std::allocator does not initialize the memory it allocates.

explicit SortedVector(size_type s)
    : sz{0}, elem{alloc.allocate(s)}, space{s} {}

So though elem points at valid memory the content of that memory is in an indeterminate state. Thus it is UB to read from the memory (before it is initialized). Also with non POD data (i.e. if T is not a simple type the constructor has not been run so the data will be undefined). When you construct an object the whole object needs to be in a valid state so you need to make sure this memory is initialized with a default value.

No prizes for writing compressed code:

  for (size_type i=0; i<arg.sz; ++i) alloc.construct(&elem[i], arg.elem[i]);

Also please also use braces '{}` around sub blocks. This will save you one day. As not all code is obviously one statement (especially if you compress it to one line).

  for (size_type i=0; i<arg.sz; ++i) {
      alloc.construct(&elem[i], arg.elem[i]);
  }

Your copy assignment is very close to being correct. Just one common mistake.

You destroy the state of the current object then assign the new state.

    for (size_type i=0; i<sz; ++i) alloc.destroy(&elem[i]);  //deallocate
    alloc.deallocate(elem, sz);                              //old space
    elem = p;

This is dangerous (if T is not a POD). If destroying an element results in an exception you are left with an object that is in an invlid state and have leaked memory. The standard order to avoid this is:

 1) Copy the object into a temporary   (you did this)
 2) Swap the state of the temporary and the current object
 3) Deallocate.

1 and 3 can potentially go wrong and throw. But it will never affect the state of the current object which will always be left in a good state. So re-writting your code it looks like this:

SortedVector& operator=(const SortedVector& arg) //copy assignment -> need deep copy
{
    if (this == &arg) {   //self assignment, return
        return *this;
    }

    if (arg.sz <= space) {  //enough space, no need for reallocation
        for (size_type i=0; i<arg.sz; ++i) alloc.construct(&elem[i], arg.elem[i]);
        sz = arg.sz;
        return *this;
    }

    // 1: Make a copy.
    T* p = alloc.allocate(arg.sz);
    for (size_type i=0; i<arg.sz; ++i) {
        alloc.construct(&p[i], arg.elem[i]);
    }
    size_type tsz    = arg.sz;
    size_type tspace = arg.sz;

    // 2: Safely swap the state.
    std::swap(elem,  p);
    std::swap(space, tspace);
    std::swap(sz,    tsz);

    // 3: Do the potentially dangerous deallocation
    for (size_type i=0; i<tsz; ++i) {  //deallocate
        alloc.destroy(&p[i]);
    }
    alloc.deallocate(p, tsz);  //old space

    return *this;
}

Test for self assignment.
This looks like a good idea. You look like you are optimizing the performance when performing a self assignment. What you are actually doing is pesimizing the performance in the normal case. Though self assignment does happen (and your code should work if it happens) it happens so infrequently that optimizing for it actually hurts normal code. It hurts it enough that you can measure the difference in real working code.

This is why the standard idiom for doing copy assignment does not check for self assignment (even for large strings). But makes a copy each time. Because we would rather pay a high price for something that barely ever happens than pay a small price that basically happens alllll the time.

Also I believe your optimization for small or same size assignment is wrong if T is a non POD type.

    if (arg.sz <= space) {


        for (size_type i=0; i<arg.sz; ++i) {
            // These elements have already been constructed.
            // If T is a type with a constructor then constructing them again
            // would be undefined behavior. You should just assign them.
            alloc.construct(&elem[i], arg.elem[i]);
        }

        // I would also note that you did not destroy the elements above
        // sz (i.e between sz and space [sz, space).
        //
        // This means the destructor will not destroy these members.
        // If the type T has a destructor this is going to lead to some
        // questionable results. 


        sz = arg.sz;
        return *this;
    }

So the standard way to write the assignment operator is to use The Copy and Swap Idiom.

    SortedVector& operator=(SortedVector arg)   // Notice the pass by value
    {                                           // This is your copy.
        swap(arg);                              // now you swap.
        return this;   
    }                                           // arg goes out of scope and is cleaned up by the detructor.
    void swap(SortedVector& other) noexcept
    {
        using std::swap;
        swap(p,    other.p);
        swap(sz,   other.sz);
        swap(size, other.size);
    }

Your move constructor works. Your move assignment has the same issue as you copy assignment that it is not exception safe. Also you are performing work you don't need to do (so is non optimal). For move assingment you can swap the two objects and defer destruction until the source object goes out of scope. This allows for potential re-use of the object (as long as you can re-set it to a known state).

Also you should try to mark your move operators as noexcept. This will enable certain optimizations if you store your object in standard containers that can take advantage of noexcept move operators and still provide the strong exception guarantee. NOTE: If you use the allocator to allocate or destroy memory in a move operator you can not mark them as noexcept.

SortedVector(SortedVector&& arg) noexcept
    : sz{0}
    , elem{nullptr}
    , space{0}
{
    swap(arg);       // note the destructor of arg will deal with cleanup.
}

SortedVector& operator=(SortedVector&& arg) noexcept
{
    swap(arg);       // note the destructor of arg will deal with cleanup.
    return *this;
}

Using a test to decide which of true or false to return is a waste. Just return the result of the test:

bool empty() const noexcept { return sz == 0 ? true: false; }

Easier to write and read as:

bool empty() const noexcept { return sz == 0;}

Front/Back usually return references to the element not an iterator.

const iterator back() const noexcept { return elem==nullptr ? nullptr: elem + sz - 1;}
const iterator front() const noexcept { return elem==nullptr ? nullptr: elem;}

I would have written them as:

// Note I don't check for nullptr.
// Calling these methods on an empty container is UB
// It is the responsibility of the caller to make the check first
// just like when using `operator[]`
value_type&       back()        { return elem[sz - 1];}
value_type&       front()       { return elem[0];}
value_type const& back()  const { return elem[sz - 1];}
value_type const& front() const { return elem[0];}

You should also look up the requirements for containers:

http://en.cppreference.com/w/cpp/concept/ContiguousContainer

You are missing a couple of type definitions. Like reference.

Worth a read: I wrote a series on how to implement a vector:

• Vector - Resource Management Allocation
• Vector - Resource Management Copy Swap
• Vector - Resize
• Vector - Simple Optimizations
• Vector - the Other Stuff
• Memory Resizing