Vector that disallows duplicates and has a fast membership check

vectorset.hpp

/**
 * A vector that disallows duplicates and has a fast membership check
 * @author Piotr Maślanka <piotr.maslanka@henrietta.com.pl>
 * @copyright Cervi Robotics sp. z o. o.
 */

#include <vector>
#include <set>
#include <algorithm>

#ifndef VECTOR_SET_H
#define VECTOR_SET_H

class VectorsetException : std::exception {
public:
    const char *message;

    VectorsetException(const char *message) : message(message) {}
};

template<class T>
class vectorset {
private:
    typename std::set<T> vector_set;
    typename std::vector<T> vector_vector;
    /**
     * Whether the vectorset should throw VectorsetException on. eg. adding duplicates
     * or removing NONE_Existent elements
     */
    const bool fail_fast;
public:
    vectorset<T>() noexcept: fail_fast(false) {};

    vectorset<T>(const std::vector<T> &vec) : vectorset<T>(vec, false) {
    };

    vectorset<T>(const bool fail_fast) : fail_fast(fail_fast) {};

    vectorset<T>(const std::vector<T> &vec, const bool fail_fast) : fail_fast(fail_fast) {
        for (auto it = vec.cbegin(); it != vec.cend(); ++it) {
            push_back(*it);
        }
    }

    /**
     * Return and remove the last item
     * @complexity O(log n)
     * @throws VectorsetException if vector was empty
     * @return last item in the vector
     */
    T pop() {
        if (vector_vector.size() == 0) {
            throw VectorsetException("vectorset is already empty");
        }
        const typename std::vector<T>::iterator vec_it = vector_vector.end() - 1;
        T item = *vec_it;
        vector_vector.erase(vec_it);
        const typename std::set<T>::iterator set_it = vector_set.find(item);
        vector_set.erase(set_it);
        return item;
    }

    /**
     * Return an iterator to the first element
     * @complexity O(1)
     */
    typename std::vector<T>::iterator begin() noexcept {
        return vector_vector.begin();
    }

    typename std::vector<T>::const_iterator begin() const noexcept {
        return vector_vector.cbegin();
    }


    /**
     * Find an element in this vectorset and return an iterator to it
     * @complexity O(n)
     */
    typename std::vector<T>::iterator find(const T &item) const noexcept {
        return std::find(vector_vector.begin(), vector_vector.end(), item);
    }

    /**
     * Return the backing vector.
     *
     * Warning! If you modify the vector directly, please call synchronize() afterwards, to rebuild the set.
     * @complexity O(1)
     */
    typename std::vector<T> &as_vector() noexcept {
        return vector_vector;
    }

    /**
     * Rebuild the backing set. Important after directly modifying the backing vector.
     * This will automatically remove duplicates from the vector
     * @throws VectorsetException if fail_fast and there were duplicates in the vector.
     * @complexity O(n)
     */
    void synchronize() noexcept {
        vector_set.clear();
        for (auto it = vector_vector.begin(); it != vector_vector.end(); ++it) {
            if (vector_set.find(*it) != vector_set.end()) {
                if (fail_fast) {
                    throw VectorsetException("synchronize called when there were duplicates in the vector");
                } else {
                    // backtrack, since the for loop will increase the iterator afterwards
                    it = vector_vector.erase(it) - 1;
                    continue;
                }
            }
            vector_set.insert(*it);
        }
    }

    /**
     * Return an iterator to the end of the vector
     * @complexity O(1)
     */
    typename std::vector<T>::iterator end() noexcept {
        return vector_vector.end();
    }

    typename std::vector<T>::const_iterator end() const noexcept {
        return vector_vector.cend();
    }

    /**
     * Return a constant iterator to the first element of the vector
     * @complexity O(1)
     */
    const typename std::vector<T>::const_iterator cbegin() const noexcept {
        return vector_vector.cbegin();
    }

    /**
     * Return a constant iterator to the end of the vector
     * @complexity O(1)
     */
    const typename std::vector<T>::const_iterator cend() const noexcept {
        return vector_vector.cend();
    }

    /**
     * Check if the vector contains given element
     * @complexity O(log n)
     * @param item element to check for
     * @return whether the vector contains it
     */
    bool contains(const T &item) const noexcept {
        return !(vector_set.find(item) == vector_set.end());
    }

    /**
     * Access an element at the given index
     * @complexity O(1)
     * @param index index
     * @return element returned
     */
    T operator[](const int index) const {
        return vector_vector[index];
    }

    /**
     * Modify an element at the given index.
     * Since this directly modifies the vector, please call synchronize() when you're done
     * @complexity O(1)
     * @param index index
     * @return element returned
     */
    T &operator[](const int index) {
        return vector_vector[index];
    }

    /**
     * Replace the element at specified index with another element
     * @complexity O(log n)
     * @throws VectorsetException if fail_fast and the end of the vector was given
     * @param where position of the element to replace
     * @param replace_with replace with
     */
    void replace(typename std::vector<T>::iterator where, const T &replace_with) {
        if (where == vector_vector.end()) {
            throw VectorsetException("Tried to replace the end of the vector");
        }
        vector_set.erase(vector_set.find(*where));
        *where = replace_with;
        vector_set.insert(replace_with);
    }

    /**
     * Replace the provided element with another.
     * No-op if the element does not exist, or VectorsetException if fail_fast
     * @complexity O(n)
     * @throws VectorsetException if fail_fast and to_replace is not in the vector
     * @param to_replace element to replace
     * @param replace_with element to replace with
     */
    void replace(const T &to_replace, const T &replace_with) {
        typename std::vector<T>::iterator it = std::find(vector_vector.begin(), vector_vector.end(), to_replace);
        if (it == vector_vector.end()) {
            if (fail_fast) {
                throw VectorsetException("tried to replace an element that does not exist");
            }
            return;
        }
        replace(it, replace_with);
    }

    /**
     * Clear the vector
     * @complexity O(1)
     */
    void clear() noexcept {
        vector_vector.clear();
        vector_set.clear();
    }

    /**
     * Append an item to the end of the vector
     * @complexity O(log n)
     * @param item item to insert
     * @throws VectorsetException if fail_fast and element is already in the vector
     * @return whether the element was added
     */
    bool push_back(const T &item) {
        if (vector_set.find(item) == vector_set.end()) {
            vector_set.insert(item);
            vector_vector.push_back(item);
            return true;
        } else {
            if (fail_fast) {
                throw VectorsetException("tried to add a double item");
            }
            return false;
        }
    }

    /**
     * Insert an element in a specified position.
     * item will be inserted before the item where the iterator points to
     * @complexity O(n)
     * @param where iterator to the position
     * @throws VectorsetException if fail_fast and element is already in the vector
     * @param item item to insert
     */
    void insert(const typename std::vector<T>::iterator where, const T &item) {
        if (vector_set.find(item) == vector_set.end()) {
            vector_set.insert(item);
            vector_vector.insert(where, item);
        } else {
            if (fail_fast) {
                throw VectorsetException("tried to insert existing element");
            }
        }
    }

    /**
     * Return the index of the item.
     * @complexity O(n)
     * @param item item to look up
     * @return index of the item, or -1 if item was not found
     */
    int index_of(const T &item) const {
        for (int i = 0; i < vector_vector.size(); i++) {
            if (vector_vector[i] == item) {
                return i;
            }
        }
        return -1;
    }

    /**
     * Remove an element at a particular position
     * @complexity O(log n)
     * @throws VectorsetException if fail_fast and element is not in the vector
     * @param where iterator to the element
     */
    void erase(const typename std::vector<T>::iterator where) {
        const T &item = *where;
        typename std::set<T>::iterator it = vector_set.find(item);
        if (it == vector_set.end()) {
            if (fail_fast) {
                throw VectorsetException("Tried to erase NONE_Existing element");
            }
        }
        vector_set.erase(it);
        vector_vector.erase(where);
    }

    /**
     * Remove the given element from the vector.
     * @complexity O(n)
     * @throws VectorsetException if fail_fast and the end of the vector was given
     * @param item item to remove
     */
    void remove(const T &item) {
        typename std::set<T>::iterator set_it = vector_set.find(item);
        if (set_it == vector_set.end()) {
            if (fail_fast) {
                throw VectorsetException("Tried to remove NONE_Existing element");
            }
            return;
        }
        vector_set.erase(set_it);
        vector_vector.erase(std::find(vector_vector.begin(), vector_vector.end(), item));
    }

    /**
     * Return the size of the vector
     * @complexity O(1)
     */
    int size() const noexcept {
        return vector_vector.size();
    }

    /**
     * Is the vector empty?
     * @complexity O(1)
     */
    bool empty() const noexcept {
        return vector_vector.empty();
    }
};

#endif //VECTOR_SET_H