STL/Boost эквивалент LLVM SmallVector?

Ответ 1

Во-первых, вы можете, конечно, извлечь LLVM SmallVector, он имеет довольно небольшое количество зависимостей и либеральную лицензию. Насколько я знаю, нет прямого эквивалента STL/Boost SmallVector. В Folly есть небольшой векторный класс (https://github.com/facebook/folly)

Ответ 2

Библиотека Container Boost v1.58 (апрель 2015 г.) имеет экспериментальный small_vector:

small_vector - векторный контейнер, оптимизированный для случая, когда он содержит несколько элементов. Он содержит некоторые предварительно выделенные элементы на месте, что позволяет избежать использования динамического распределения хранилища, когда фактическое количество элементов находится ниже этого заранее установленного порога. small_vector вдохновлен контейнером LLVM SmallVector. В отличие от static_vector, емкость small_vector может увеличиваться за пределы исходной предварительно распределенной емкости.

small_vector<T, N, Allocator> преобразуется в small_vector_base<T, Allocator>, тип, который не зависит от числа предварительно распределенных элементов, что позволяет клиенту, который не нуждается в шаблоне для этого аргумента N. small_vector наследует все функции-члены вектора, поэтому он поддерживает все стандартные функции, такие как размещение, блокировки с использованием состояния и т.д.

Вы также можете быть заинтересованы в некоторых контейнерах из Electronic Arts Standard Template Library.

Там репозиторий на Github (посмотрите на контейнеры фиксированного размера eastl::vector_*, они похожи на LLVM SmallVector).

В Qt есть класс QVarLengthArray.

Ответ 3

Я создаю билет в boost для него как запрос функции: Ticket # 9165 (https://svn.boost.org/trac/boost/ticket/9165)

Ответ 4

Возможно, он может быть реализован с помощью какого-либо класса адаптера/прокси, который инкапсулирует нормальный std::vector и, возможно, использует std::array для обычных операций с "маленьким вектором". Просто используя тот же интерфейс, что, например, std::vector, в то время как перевод индексов должен быть достаточным. Большая проблема была бы итераторами, но это, вероятно, можно было бы преодолеть, инкапсулируя итераторы инкапсулированных коллекций.

Очень много работы, чтобы сшить все это вместе, так что может быть проще просто иметь инкапсулированный std::vector с предварительно выделенной памятью. А затем в функции push_back и т.д., Чтобы проверить, находится ли добавленный элемент в пределах предварительно распределенной памяти, и просто установите элемент в нужное место вместо вызова векторов push_back.

Ответ 5

Я разработал собственную версию SmallVector с семантикой перемещения. Я попытался сохранить это просто. Он не пытается быть безопасным для исключений. Я также использую целые числа без знака для индексирования, поскольку я предпочитаю их по подписанным. Вот код

#pragma once

#include <new>
#include <type_traits>
#include <initializer_list>
#include <utility>
#include <cstddef>
#include <cstdint>
#include <climits>
#include <cstdlib>

typedef std::ptrdiff_t integer;
typedef std::size_t uinteger;
const integer integer_max{ PTRDIFF_MAX };

#ifdef NDEBUG
#define IL_ASSERT(condition) \
        ((void) 0)
#else
#define IL_ASSERT(condition) \
        (condition) ? (void) 0 : abort()
#endif
// This class is a vector class that has small sized optimization and does not
// attempt to be exception safe.
// - data_ always point to the beginning of the vector. It points to some
//   memory on the heap when small size optimization is not used and points
//   to data_small_ when small size optimization is used.
// - Objects on data_small_ are never destructed but are reinitialized to T{ }
//   when not used anymore. Objects on the heap are desctucted when the are not
//   plain old data and not used anymore.
// - The capacity of the vector is always >= than small_size wether small size
//   optimization is in use (in this case the capacity is equal to small_size)
//   or not.
//
// The class has been specialized for small_size = 0.

namespace il {

template <typename T, integer small_size = 0>
class SmallVector {
    static_assert(small_size >= 0,
            "il::SmallVector must have a non-negative small size");
private:
    #ifndef NDEBUG
    integer debug_size_;
    integer debug_capacity_;
    bool debug_is_data_small_used_;
    #endif
    T* data_;
    T* size_;
    T* capacity_;
    T data_small_[small_size > 0 ? small_size : 1];
private:
    bool is_data_small_used() const {
        return data_ == data_small_;
    }
public:
    SmallVector() {
        #ifndef NDEBUG
        debug_size_ = 0;
        debug_capacity_ = 0;
        debug_is_data_small_used_ = true;
        #endif
        data_ = data_small_;
        size_ = data_small_;
        capacity_ = data_small_ + small_size;
    }
    SmallVector(integer n) {
        IL_ASSERT(n >= 0);
        #ifndef NDEBUG
        debug_size_ = n;
        #endif
        if (n <= small_size) {
            #ifndef NDEBUG
            debug_capacity_ = small_size;
            debug_is_data_small_used_ = true;
            #endif
            data_ = data_small_;
            size_ = data_ + n;
            capacity_ = data_ + small_size;
        } else {
            #ifndef NDEBUG
            debug_capacity_ = n;
            debug_is_data_small_used_ = false;
            #endif
            data_ = static_cast<T*>(::operator new(
                    static_cast<std::size_t>(n) * sizeof(T)));
            size_ = data_ + n;
            capacity_ = size_;
            if (!std::is_pod<T>::value) {
                for (integer k = 0; k < n; ++k) {
                    new (data_ + k) T{};
                }
            }
        }
    }
    SmallVector(integer n, const T& x) {
        IL_ASSERT(n >= 0);
        #ifndef NDEBUG
        debug_size_ = n;
        #endif
        if (n <= small_size) {
            #ifndef NDEBUG
            debug_capacity_ = small_size;
            debug_is_data_small_used_ = true;
            #endif
            data_ = data_small_;
            size_ = data_ + n;
            capacity_ = data_ + small_size;
            for (integer k = 0; k < n; ++k) {
                data_[k] = x;
            }
        } else {
            #ifndef NDEBUG
            debug_capacity_ = n;
            debug_is_data_small_used_ = false;
            #endif
            data_ = static_cast<T*>(::operator new(
                    static_cast<std::size_t>(n) * sizeof(T)));
            size_ = data_ + n;
            capacity_ = size_;
            for (integer k = 0; k < n; ++k) {
                new (data_ + k) T{ x };
            }
        }
    }
    SmallVector(std::initializer_list<T> list) {
        integer n{ static_cast<integer>(list.size()) };
        #ifndef NDEBUG
        debug_size_ = n;
        #endif
        if (n <= small_size) {
            #ifndef NDEBUG
            debug_capacity_ = small_size;
            debug_is_data_small_used_ = true;
            #endif
            data_ = data_small_;
            size_ = data_ + n;
            capacity_ = data_ + small_size;
            for (integer k = 0; k < n; ++k) {
                data_[k] = *(list.begin() + k);
            }
        } else {
            #ifndef NDEBUG
            debug_capacity_ = n;
            debug_is_data_small_used_ = false;
            #endif
            data_ = static_cast<T*>(::operator new(
                    static_cast<std::size_t>(n) * sizeof(T)));
            size_ = data_ + n;
            capacity_ = size_;
            for (integer k = 0; k < n; ++k) {
                new (data_ + k) T{ *(list.begin() + k) };
            }
        }
    }
    SmallVector(const SmallVector<T, small_size>& A) {
        integer n{ A.size() };
        #ifndef NDEBUG
        debug_size_ = n;
        #endif
        if (n <= small_size) {
            #ifndef NDEBUG
            debug_capacity_ = small_size;
            debug_is_data_small_used_ = true;
            #endif
            data_ = data_small_;
            size_ = data_ + n;
            capacity_ = data_ + small_size;
            for (integer k = 0; k < n; ++k) {
                data_[k] = A.data_[k];
            }
        } else {
            #ifndef NDEBUG
            debug_capacity_ = n;
            debug_is_data_small_used_ = false;
            #endif
            data_ = static_cast<T*>(::operator new(
                    static_cast<std::size_t>(n) * sizeof(T)));
            size_ = data_ + n;
            capacity_ = size_;
            for (integer k = 0; k < n; ++k) {
                new (data_ + k) T{ A.data_[k] };
            }
        }
    }
    SmallVector(SmallVector<T, small_size>&& A) {
        integer n{ A.size() };
        #ifndef NDEBUG
        debug_size_ = n;
        #endif
        if (n <= small_size) {
            #ifndef NDEBUG
            debug_capacity_ = small_size;
            debug_is_data_small_used_ = true;
            #endif
            data_ = data_small_;
            size_ = data_ + n;
            capacity_ = data_ + small_size;
            for (integer k = 0; k < n; ++k) {
                data_[k] = std::move(A.data_[k]);
            }
        } else {
            #ifndef NDEBUG
            debug_capacity_ = A.debug_capacity_;
            debug_is_data_small_used_ = false;
            #endif
            data_ = A.data_;
            size_ = A.size_;
            capacity_ = A.capacity_;
            #ifndef NDEBUG
            A.debug_size_ = 0;
            A.debug_capacity_ = 0;
            A.debug_is_data_small_used_ = false;
            #endif
            A.data_ = data_small_;
            A.size_ = data_small_;
            A.capacity_ = data_small_ + small_size;
        }
    }
    SmallVector& operator=(const SmallVector<T, small_size>& A) {
        if (this != &A) {
            integer n{ A.size() };
            bool needs_memory{ capacity() < n };
            if (needs_memory) {
                #ifndef NDEBUG
                debug_size_ = n;
                debug_capacity_ = n;
                debug_is_data_small_used_ = false;
                #endif
                if (!std::is_pod<T>::value) {
                    for (integer k = size() - 1; k >= 0; --k) {
                        (data_ + k)->~T();
                    }
                }
                ::operator delete(data_);
                data_ = static_cast<T*>(::operator new(
                        static_cast<std::size_t>(n) * sizeof(T)));
                size_ = data_ + n;
                capacity_ = size_;
                for (integer k = 0; k < n; ++k) {
                    new (data_ + k) T{ A.data_[k] };
                }
            } else {
                if (!std::is_pod<T>::value) {
                    if (is_data_small_used()) {
                        for (integer k = size() - 1; k >=n ; --k) {
                            *(data_ + k) = T{ };
                        }
                    } else {
                        for (integer k = size() - 1; k >= n; --k) {
                            (data_ + k)->~T();
                        }
                    }
                }
                #ifndef NDEBUG
                debug_size_ = n;
                #endif
                size_ = data_ + n;
                for (integer k = 0; k < n; ++k) {
                    data_[k] = A.data_[k];
                }
            }
        }
        return *this;
    }
    SmallVector& operator=(SmallVector<T, small_size>&& A) {
        if (this != &A) {
            integer n{ A.size() };
            if (n <= small_size) {
                if (!is_data_small_used()) {
                    if (!std::is_pod<T>::value) {
                        for (integer k = size() - 1; k >= 0; --k) {
                            (data_ + k)->~T();
                        }
                    }
                    ::operator delete(data_);
                }
                #ifndef NDEBUG
                debug_size_ = n;
                debug_capacity_ = small_size;
                debug_is_data_small_used_ = true;
                #endif
                data_ = data_small_;
                size_ = data_small_ + n;
                capacity_ = data_small_ + small_size;
                for (integer k = 0; k < n; ++k) {
                    data_[k] = std::move(A.data_[k]);
                }
            } else {
                if (is_data_small_used()) {
                    for (integer k = 0; k < small_size; ++k) {
                        data_[k] = T{ };
                    }
                } else {
                    if (!std::is_pod<T>::value) {
                        for (integer k = size() - 1; k >= 0; --k) {
                            (data_ + k)->~T();
                        }
                    }
                    ::operator delete(data_);
                }
                #ifndef NDEBUG
                debug_size_ = A.debug_size_;
                debug_capacity_ = A.debug_capacity_;
                debug_is_data_small_used_ = false;
                #endif
                data_ = A.data_;
                size_ = A.size_;
                capacity_ = A.capacity_;
                #ifndef NDEBUG
                A.debug_size_ = 0;
                A.debug_capacity_ = 0;
                A.debug_is_data_small_used_ = true;
                #endif
                A.data_ = A.data_small_;
                A.size_ = A.data_small_;
                A.capacity_ = A.data_small_ + small_size;
            }
        }
        return *this;
    }
    ~SmallVector() {
        if (!is_data_small_used()) {
            if (!std::is_pod<T>::value) {
                for (integer k = size() - 1; k >= 0; --k) {
                    (data_ + k)->~T();
                }
            }
            ::operator delete(data_);
        }
    }
    const T& operator[](integer k) const {
        IL_ASSERT(static_cast<uinteger>(k) < static_cast<uinteger>(size()));
        return data_[k];
    }
    T& operator[](integer k) {
        IL_ASSERT(static_cast<uinteger>(k) < static_cast<uinteger>(size()));
        return data_[k];
    }
    const T& operator()(integer k) const {
        IL_ASSERT(static_cast<uinteger>(k) < static_cast<uinteger>(size()));
        return data_[k];
    }
    T& operator()(integer k) {
        IL_ASSERT(static_cast<uinteger>(k) < static_cast<uinteger>(size()));
        return data_[k];
    }
    T* data() {
        return data_;
    }
    const T* data() const {
        return data_;
    }
    const T* begin() const {
        return data_;
    }
    const T* end() const {
        return size_;
    }
    integer size() const {
        return static_cast<integer>(size_ - data_);
    }
    integer capacity() const {
        return static_cast<integer>(capacity_ - data_);
    }
    integer max_size() const {
        return integer_max;
    }
    bool empty() const {
        return size_ == data_;
    }
    void resize(integer n) {
        IL_ASSERT(n >= 0);
        if (n <= capacity()) {
            #ifndef NDEBUG
            debug_size_ = n;
            #endif
            if (is_data_small_used()) {
                if (!std::is_pod<T>::value) {
                    if (n < size()) {
                        for (integer k = size() - 1; k >= n ; --k) {
                            data_[k] = T{ };
                        }
                    } else {
                        for (integer k = size(); k < n ; ++k) {
                            data_[k] = T{ };
                        }
                    }
                };
            } else {
                if (!std::is_pod<T>::value) {
                    if (n < size()) {
                        for (integer k = size() - 1; k >= n; ++k) {
                            (data_ + k)->~T();
                        }
                    } else {
                        for (integer k = size(); k < n; ++k) {
                            new (data_ + k) T{ };
                        }
                    }
                }
            }
            size_ = data_ + n;
        } else {
            #ifndef NDEBUG
            debug_size_ = n;
            debug_capacity_ = n;
            debug_is_data_small_used_ = false;
            #endif
            integer n_old{ size() };
            T* new_data = static_cast<T*>(::operator new(
                    static_cast<std::size_t>(n) * sizeof(T)));
            for (integer k = 0; k < n_old; ++k) {
                new (new_data + k) T{ std::move(data_[k]) };
            }
            if (is_data_small_used()) {
                if (!std::is_pod<T>::value) {
                    for (integer k = size() - 1; k >= 0; --k) {
                        data_[k] = T{ };
                    };
                }
            }  else {
                if (!std::is_pod<T>::value) {
                    for (integer k = size() - 1; k >= 0; --k) {
                        (data_ + k)->~T();
                    }
                }
                ::operator delete(data_);
            }
            data_ = new_data;
            size_ = data_ + n;
            capacity_ = size_;
        }
    }
    void reserve(integer p) {
        IL_ASSERT(p >= 0);
        if (p > capacity()) {
            #ifndef NDEBUG
            debug_capacity_ = p;
            debug_is_data_small_used_ = false;
            #endif
            integer n_old{ size() };
            T *new_data = static_cast<T *>(::operator new(
                    static_cast<std::size_t>(p) * sizeof(T)));
            for (integer k = 0; k < n_old; ++k) {
                new (new_data + k) T{ std::move(data_[k]) };
            }
            if (is_data_small_used()) {
                if (!std::is_pod<T>::value) {
                    for (integer k = size() - 1; k >= 0; --k) {
                        data_[k] = T{ };
                    };
                }
            }  else {
                if (!std::is_pod<T>::value) {
                    for (integer k = size() - 1; k >= 0; --k) {
                        (data_ + k)->~T();
                    }
                }
                ::operator delete(data_);
            }
            for (integer k = n_old; k < p; ++k) {
                new (new_data + k) T{ };
            }
            data_ = new_data;
            size_ = data_ + n_old;
            capacity_ = data_ + p;
        }
    }
    void push_back(const T& x) {
        if (size_ == capacity_) {
            integer n_old{ size() };
            integer n{ n_old > 1 ? (3 * n_old) / 2 : n_old + 1 };
            T *new_data = static_cast<T *>(::operator new(
                    static_cast<std::size_t>(n) * sizeof(T)));
            for (integer k = 0; k < n_old; ++k) {
                new (new_data + k) T{ std::move(data_[k]) };
            }
            if (is_data_small_used()) {
                if (!std::is_pod<T>::value) {
                    for (integer k = size() - 1; k >= 0; --k) {
                        data_[k] = T{ };
                    };
                }
            }  else {
                if (!std::is_pod<T>::value) {
                    for (integer k = size() - 1; k >= 0; --k) {
                        (data_ + k)->~T();
                    }
                }
                ::operator delete(data_);
            }
            data_ = new_data;
            #ifndef NDEBUG
            debug_capacity_ = n;
            debug_is_data_small_used_ = false;
            #endif
            capacity_ = data_ + n;
        }
        #ifndef NDEBUG
        ++debug_size_;
        #endif
        if (is_data_small_used()) {
            *size_ = x;
        } else {
            new (size_) T{ x };
        }
        ++size_;
    }
};

}