Question

Я не уверен, если это хороший вопрос или нет - закройте его, если нет.

Я намеревался написать (используя boost::coordinate_vector в качестве отправной точки) класс шаблона sparse_vectorэто эффективно реализует вектороподобный интерфейс, но редко.Он реализует все обычные векторные операции и быстрый разреженный итератор, который перебирает заданные элементы.Он также имеет быструю версию rotate.Мне нужен этот класс, потому что у меня есть сценарий использования «один раз для чтения много», и я использую многие из них sparse_vectors.

У меня нет опыта написания шаблонных классов, поэтому я знаю, что есть вещиЯ мог бы быть лучше.Как я могу улучшить этот класс?

// sparse_vector is a sparse version of std::vector.  It stores index-value pairs, and a size, which
// represents the size of the sparse_vector.

#include <algorithm>
#include <ostream>
#include <iostream>
#include <vector>
#include <boost/iterator.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/iterator/reverse_iterator.hpp>
#include <boost/optional.hpp>
#include <glog/logging.h>

template<typename T>
class sparse_vector {
public:
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef size_t size_type;
private:
    struct ElementType {
        ElementType(size_type i, T const& t): index(i), value(t) {}
        ElementType(size_type i, T&& t): index(i), value(move(t)) {}
        ElementType(size_type i): index(i) {}  // allows lower_bound to work
        ElementType(ElementType const&) = default;
        size_type index;
        value_type value;
    };
    typedef std::vector<ElementType> array_type;
public:
    typedef typename array_type::difference_type difference_type;

private:
    typedef const T* const_pointer;
    typedef sparse_vector<T> self_type;
    typedef typename array_type::const_iterator const_subiterator_type;
    typedef typename array_type::iterator subiterator_type;

    struct IndexCompare {
        bool operator()(ElementType const& a, ElementType const& b) { return a.index < b.index; }
    };

public:
    // Construction and destruction
    inline sparse_vector(): size_(0), sorted_filled_(0), data_() {
            storage_invariants(); }
    explicit inline sparse_vector(size_type size): size_(size), sorted_filled_(0), data_() {
            storage_invariants(); }
    inline sparse_vector(const sparse_vector<T> &v):
        size_(v.size_), sorted_filled_(v.sorted_filled_), data_(v.data_) {
            storage_invariants(); }
    inline sparse_vector(sparse_vector<T>&& v):
        size_(v.size_), sorted_filled_(v.sorted_filled_), data_(move(v.data_)) {
            storage_invariants(); }
    sparse_vector(const optional<T> &o): size_(1), sorted_filled_(0) {
            if (o) {
                append_element(0, *o);
                sorted_filled_ = 1;
            }
            storage_invariants();
        }
    sparse_vector(const std::vector<T> &v):
        size_(v.size()), sorted_filled_(0) {
            data_.reserve(v.size());
            for (auto it = v.begin(); it != v.end(); ++it)
                append_element(it - v.begin(), *it);
            sorted_filled_ = v.size();
            storage_invariants();
        }
    sparse_vector(const sparse_vector<optional<T>> &sv):
        size_(sv.size()), sorted_filled_(0) {
            for (auto it = sv.sparse_begin(); it != sv.sparse_end(); ++it)
                if (*it)
                    append_element(it.index(), **it);
            sorted_filled_ = data_.size();
            storage_invariants();
        }
    sparse_vector(size_type size, vector<pair<size_type, T>> init_list):
        size_(size), sorted_filled_(0) {
            for (auto it = init_list.begin(); it != init_list.end(); ++it)
                append_element(it->first, it->second);
            // require that the list be sorted?
            // sorted_filled_ = data_.size();
            storage_invariants();
        }
    /*template<class AE>
        inline sparse_vector(const sparse_vector<AE> &ae):
            size_(ae().size()), sorted_filled_(ae.nnz()), data_() {
                storage_invariants();
                for (auto it = ae.sparse_begin(); it != ae.sparse_end(); ++it) {
                    (*this)[it.index()] = static_cast<T>(*it);
                }
            }*/

    // Conversion operators
    // Copy sparse_vector to a vector filling in uninitialized elements with T()
    operator std::vector<T>() {
        std::vector<T> retval(size_);
        for (auto it = data_.begin(); it != data_.end(); ++it)
            retval[it.index()] = *it;
        return retval; 
    }
    // Copy sparse_vector to a vector filling in uninitialized elements with a default value.
    void CopyToVector(std::vector<T>* v, T const& default_value = T()) {
        size_type last_index = 0;
        for (auto it = sparse_begin(); it != sparse_end(); ++it) {
            for (size_type i = last_index; i < it.index(); ++i) {
                (*v)[i] = default_value;
            }
            (*v)[it.index()] = *it;
            last_index = it.index() + 1;
        }
    }

    // Accessors
    inline size_type size() const {
        return size_;
    }
    inline size_type nnz_capacity() const {
        return data_.capacity();
    }
    inline size_type nnz() const {
        return data_.size();
    }

    // Resizing
    inline void resize(size_type size, bool preserve = true) {
        if (preserve) {
            sort();    // remove duplicate elements.
            subiterator_type it(lower_bound(data_.begin(), data_.end(), size, IndexCompare()));
            data_.erase(it, data_.end());
        } else {
            data_.clear();
        }
        size_ = size;
        sorted_filled_ = nnz();
        storage_invariants();
    }

    // Reserving
    inline void reserve(size_type non_zeros, bool preserve = true) {
        if (preserve)
            sort();    // remove duplicate elements.
        else
            data_.clear();
        data_.reserve(non_zeros);
        sorted_filled_ = nnz();
        storage_invariants();
    }

    // Element support
    // find_element returns a pointer to element i or NULL -- it never creates an element
    inline pointer find_element(size_type i) {
        return const_cast<pointer> (const_cast<const self_type&>(*this).find_element(i)); }
    inline const_pointer find_element(size_type i) const {
        sort();
        const_subiterator_type it(lower_bound(data_.begin(), data_.end(), i, IndexCompare()));
        if (it == data_.end() || it->index != i)
            return NULL;
        return &it->value;
    }
    // find_element_optional returns a boost::optional<T>
    inline boost::optional<value_type> find_element_optional(size_type i) const {
        CHECK_LT(i, size_);
        sort();
        const_subiterator_type it(lower_bound(data_.begin(), data_.end(), i, IndexCompare()));
        if (it == data_.end() || it->index != i)
            return boost::optional<value_type>();
        return boost::optional<value_type>(it->value);
    }

    // Element access
    // operator[] returns a reference to element i -- the const version returns a reference to
    // a zero_ element if it doesn't exist; the non-const version creates it in that case.
    inline const_reference operator[] (size_type i) const {
        CHECK_LT(i, size_);
        sort();
        const_subiterator_type it(lower_bound(data_.begin(), data_.end(), i, IndexCompare()));
        if (it == data_.end() || it->index != i)
            return zero_;
        return it->value;
    }
    inline reference operator[] (size_type i) {
        CHECK_LT(i, size_);
        sort();
        subiterator_type it(lower_bound(data_.begin(), data_.end(), i, IndexCompare()));
        if (it == data_.end() || it->index != i)
            return insert_element(i, value_type/*zero*/());
        else
            return it->value;
    }

    // Element assignment
    inline void append_element(size_type i, const_reference t) {
        data_.emplace_back(i, t);
        storage_invariants();
    }
    inline void append_element(size_type i, T&& t) {
        data_.emplace_back(i, move(t));
        storage_invariants();
    }
    inline void sorted_append_element(size_type i, const_reference t) {
        // must maintain sort order
        CHECK(sorted());
        if (data_.size() > 0)
            CHECK_LT(data_.back().index, i);
        data_.emplace_back(i, t);
        sorted_filled_ = data_.size();
        storage_invariants();
    }
    /* This function is probably not useful.
     * inline void sparse_pop_back() {
        // ISSUE invariants could be simpilfied if sorted required as precondition
        CHECK_GT(data_.size(), 0);
        data_.pop_back();
        sorted_filled_ = (std::min)(sorted_filled_, data_.size());
        storage_invariants();
    }*/
    inline reference insert_element(size_type i, const_reference t) {
        DCHECK(find_element(i) == NULL);  // duplicate element
        append_element(i, t);
        return data_.back().value;
    }

    // Element clearing
    // TODO(neil): consider replacing size_type functions with iterator functions
    // replaces elements in the range [i, i] with "zero" (by erasing them from the map)
    inline void clear_element(size_type i) {
        sort();
        subiterator_type it(lower_bound(data_.begin(), data_.end(), i, IndexCompare()));
        if (it == data_.end() || it->index != i)
            return;
        data_.erase(it);
        --sorted_filled_;
        storage_invariants();
    }
    // replaces elements in the range [first, last) with "zero" (by erasing them from the map)
    inline void clear_elements(size_type first, size_type last) {
        CHECK_LE(first, last);
        sort();
        subiterator_type it_first(lower_bound(data_.begin(), data_.end(), first, IndexCompare()));
        subiterator_type it_last(lower_bound(data_.begin(), data_.end(), last, IndexCompare()));
        sorted_filled_ -= it_last - it_first;
        data_.erase(it_first, it_last);
        storage_invariants();
    }

    // Zeroing
    inline void clear() { data_.clear(); sorted_filled_ = 0; storage_invariants(); }

    // Comparison
    inline bool operator==(const sparse_vector &v) const {
        if (this == &v)
            return true;
        if (size_ != v.size_)
            return false;
        auto it_this = sparse_begin();
        for (auto it = v.sparse_begin(); it != v.sparse_end(); ++it) {
            if (it_this == sparse_end()
                || it_this.index() != it.index()
                || *it_this != *it)
                return false;
            ++it_this;
        }
        return true;
    }

    // Assignment
    inline sparse_vector& operator=(const sparse_vector &v) {
        if (this != &v) {
            size_ = v.size_;
            sorted_filled_ = v.sorted_filled_;
            data_ = v.data_;
        }
        storage_invariants();
        return *this;
    }
    inline sparse_vector &assign_temporary(sparse_vector &v) {
        swap(v);
        return *this;
    }
    template<class AE>
        inline sparse_vector& operator=(const sparse_vector<AE> &ae) {
            self_type temporary(ae);
            return assign_temporary(temporary);
        }

    // Swapping
    inline void swap(sparse_vector &v) {
        if (this != &v) {
            std::swap(size_, v.size_);
            std::swap(sorted_filled_, v.sorted_filled_);
            data_.swap(v.data_);
        }
        storage_invariants();
    }
    inline friend void swap(sparse_vector &v1, sparse_vector &v2) { v1.swap(v2); }

    // Sorting and summation of duplicates
    inline bool sorted() const { return sorted_filled_ == data_.size(); }
    inline void sort() const {
        if (!sorted() && data_.size() > 0) {
            // sort new elements and merge
            std::sort(data_.begin() + sorted_filled_, data_.end(), IndexCompare());
            std::inplace_merge(data_.begin(), data_.begin() + sorted_filled_, data_.end(),
                               IndexCompare());

            // check for duplicates
            size_type filled = 0;
            for(size_type i = 1; i < data_.size(); ++i) {
                if (data_[filled].index != data_[i].index) {
                    ++filled;
                    if (filled != i) {
                        data_[filled] = data_[i];
                    }
                } else {
                    CHECK(false);  // duplicates
                    // value_data_[filled] += value_data_[i];
                }
            }
            ++filled;
            sorted_filled_ = filled;
            data_.erase(data_.begin() + filled, data_.end());
            storage_invariants();
        }
    }

    // Back element insertion and erasure
    inline void push_back(const_reference t) {
        CHECK(sorted());
        data_.emplace_back(size(), t);
        if (sorted_filled_ == data_.size())
            ++sorted_filled_;
        ++size_;
        storage_invariants();
    }
    inline void pop_back() {
        CHECK_GT(size_, 0);
        clear_element(size_ - 1);
        if (sorted_filled_ == size_)
            --sorted_filled_;
        --size_;
        storage_invariants();
    }

    // Iterator types
private:
    template<typename base_type, typename iterator_value_type>
        class sparse_iterator_private
            : public boost::iterator_adaptor<
              sparse_iterator_private<base_type, iterator_value_type>,  // Derived
              base_type,                                                // Base
              iterator_value_type,                                      // Value
              boost::random_access_traversal_tag                        // CategoryOrTraversal
              > {
        private:
            struct enabler {};  // a private type avoids misuse

        public:
            sparse_iterator_private()
                : sparse_iterator_private<base_type, iterator_value_type>::iterator_adaptor_() {}

            explicit sparse_iterator_private(base_type&& p)
                : sparse_iterator_private<base_type, iterator_value_type>::iterator_adaptor_(p) {}

            size_type index() const { return this->base()->index; }
            iterator_value_type& value() const { return this->base()->value; }

        private:
            friend class boost::iterator_core_access;

            iterator_value_type& dereference() const { return this->base()->value; }
        };

    template<typename container_type, typename iterator_value_type>
        class iterator_private
        : public boost::iterator_facade<
          iterator_private<container_type, iterator_value_type>,    // Derived
          iterator_value_type,                                      // Value
          boost::random_access_traversal_tag,                       // CategoryOrTraversal
          iterator_value_type&,                                     // Reference
          difference_type                                           // Difference
          > {
          private:
              struct enabler {};  // a private type avoids misuse

          public:
              iterator_private(): container_(NULL), index_(0) {}

              iterator_private(container_type* container, size_type index)
                  : container_(container), index_(index) {}

              iterator_private(iterator_private const& other)
                  : container_(other.container_), index_(other.index_) {}

              iterator_private& operator=(iterator_private const& other) {
                  container_ = other.container_;
                  index_ = other.index_;
              }

              container_type& container() const { return *container_; }
              size_type index() const { return index_; }
              iterator_value_type& value() const { return dereference(); }
              /* TODO(neil): how do you make this work?
                 template<typename U>
                 sparse_iterator_private<U> subsequent_sparse_iterator() {
                 return sparse_iterator_private<T>(lower_bound(container_.data_.begin(),
                 container_.data_.end(),
                 index_, IndexCompare()));
                 }
                 */

          private:
              friend class boost::iterator_core_access;
              iterator_value_type& dereference() const { return (*container_)[index_]; }
              bool equal(iterator_private<container_type, iterator_value_type> const& other) const {
                  return index_ == other.index_ && container_ == other.container_; }
              void increment() { ++index_; }
              void decrement() { --index_; }
              void advance(int n) { index_ += n; }
              difference_type distance_to(iterator_private<container_type,
                                          iterator_value_type> const& other) {
                  return index_ - other.index_; }

              container_type*       container_;
              size_type             index_;
          };

public:
    typedef sparse_iterator_private<typename array_type::iterator, value_type> sparse_iterator;
    typedef sparse_iterator_private<
        typename array_type::const_iterator, const value_type> const_sparse_iterator;
    typedef iterator_private<sparse_vector, value_type> iterator;
    typedef iterator_private<const sparse_vector, const value_type> const_iterator;
    typedef boost::reverse_iterator<sparse_iterator> reverse_sparse_iterator;
    typedef boost::reverse_iterator<const_sparse_iterator> const_reverse_sparse_iterator;
    typedef boost::reverse_iterator<iterator> reverse_iterator;
    typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;

    // Element lookup
    // inline This function seems to be big. So we do not let the compiler inline it.    
    sparse_iterator sparse_find(size_type i) {
        sort();
        return sparse_iterator(lower_bound(data_.begin(), data_.end(), i, IndexCompare()));
    }
    // inline This function seems to be big. So we do not let the compiler inline it.    
    const_sparse_iterator sparse_find(size_type i) const {
        sort();
        return const_sparse_iterator(lower_bound(data_.begin(), data_.end(), i, IndexCompare()));
    }
    // the nth non-zero element
    const_sparse_iterator nth_nonzero(size_type i) const {
        CHECK_LE(data_.size(), i);
        sort();
        return const_sparse_iterator(data_.begin() + i);
    }

    // Forward iterators
    inline sparse_iterator sparse_begin() { return sparse_find(0); }
    inline sparse_iterator sparse_end() { return sparse_find(size_); }
    inline const_sparse_iterator sparse_begin() const { return sparse_find(0); }
    inline const_sparse_iterator sparse_end() const { return sparse_find(size_); }
    inline iterator begin() { return iterator(this, 0); }
    inline iterator end() { return iterator(this, size()); }
    inline const_iterator begin() const { return const_iterator(this, 0); }
    inline const_iterator end() const { return const_iterator(this, size()); }

    // Reverse iterators
    inline reverse_sparse_iterator sparse_rbegin() {
        return reverse_sparse_iterator(sparse_end()); }
    inline reverse_sparse_iterator sparse_rend() {
        return reverse_sparse_iterator(sparse_begin()); }
    inline const_reverse_sparse_iterator sparse_rbegin() const {
        return const_reverse_sparse_iterator(sparse_end()); }
    inline const_reverse_sparse_iterator sparse_rend() const {
        return const_reverse_sparse_iterator(sparse_begin()); }
    inline reverse_iterator rbegin() {
        return reverse_iterator(end()); }
    inline reverse_iterator rend() {
        return reverse_iterator(begin()); }
    inline const_reverse_iterator rbegin() const {
        return const_reverse_iterator(end()); }
    inline const_reverse_iterator rend() const {
        return const_reverse_iterator(begin()); }

    // Mutating algorithms
    // like vector::erase (erases the elements from the container and shrinks the container)
    inline void erase(iterator const& first, iterator const& last) {
        clear_elements(first.index(), last.index());
        CHECK(sorted());
        subiterator_type it_first(lower_bound(data_.begin(), data_.end(),
                                              first.index(), IndexCompare()));
        size_t n = last.index() - first.index();
        for (auto it = it_first; it != data_.end(); ++it)
            it->index -= n;
        size_ -= n;
    }

    // like vector::insert (insert elements into the container and causes the container to grow)
    inline void insert(iterator const& index, size_type n) {
        sort();
        subiterator_type it_first(lower_bound(data_.begin(), data_.end(),
                                              index.index(), IndexCompare()));
        for (auto it = it_first; it != data_.end(); ++it)
            it->index += n;
        size_ += n;
    }

    // Removes all "zero" elements
    void remove_zeros() {
        size_type filled = 0;
        for(size_type i = 0; i < data_.size(); ++i) {
            if (i == sorted_filled_) {
                // Once we've processed sorted_filled_ items, we know that whatever we've filled so
                // far is sorted.
                CHECK_LE(filled, sorted_filled_);
                // Since sorted_filled_ only shrinks here, and i only grows, we won't enter this
                // condition twice.
                sorted_filled_ = filled;
            }
            if (data_[i].value != value_type/*zero*/()) {
                if (filled != i) {
                    data_[filled] = data_[i];
                }
                ++filled;
            }
        }
        data_.erase(data_.begin() + filled, data_.end());
        storage_invariants();
    }

    void rotate(size_type first, size_type middle, size_type last) {
        CHECK_LT(first, middle);
        CHECK_LT(middle, last);
        sort();
        subiterator_type it_first(lower_bound(data_.begin(), data_.end(),
                                              first, IndexCompare()));
        subiterator_type it_middle(lower_bound(data_.begin(), data_.end(),
                                               middle, IndexCompare()));
        subiterator_type it_last(lower_bound(data_.begin(), data_.end(),
                                             last, IndexCompare()));

        for (auto it = it_first; it != it_middle; ++it)
            it->index += last - middle;
        for (auto it = it_middle; it != it_last; ++it)
            it->index -= middle - first;
        std::rotate(it_first, it_middle, it_last);
        // array remains sorted
    }

    sparse_vector<value_type> concatenate(sparse_vector<value_type> const& other) const {
        sparse_vector<value_type> retval(size() + other.size());
        for (auto it = sparse_begin(); it != sparse_end(); ++it) {
            retval[it.index()] = *it;
        }
        for (auto it = other.sparse_begin(); it != other.sparse_end(); ++it) {
            retval[it.index() + size()] = *it;
        }
        return retval;
    }

private:
    void storage_invariants() const {
        CHECK_LE(sorted_filled_, data_.size());
        if (sorted())
            CHECK_EQ(sorted_filled_, data_.size());
        else
            CHECK_LT(sorted_filled_, data_.size());
        if (!data_.empty())
            CHECK_LT(data_.back().index, size_);
        for (size_type i = 1; i < sorted_filled_; ++i)
            CHECK_GT(data_[i].index, data_[i - 1].index);
    }

    size_type                                   size_;
    mutable typename array_type::size_type      sorted_filled_; 
    mutable array_type                          data_;

    static const value_type                     zero_;
};

template<typename T>
const typename sparse_vector<T>::value_type sparse_vector<T>::zero_ = T();

template<typename T>
ostream& operator<<(ostream& os, const sparse_vector<T>& v) {
    os << "[" << v.size() << ": ";
    for (auto it = v.sparse_begin(); it != v.sparse_end(); ++it) {
        os << "(" << it.index() << ": " << it.value() << ") ";
    }
    return os << "]";
}

stinky472 · Answer 1 · 27 июня 2010

Для кого-то с небольшим опытом написания шаблонов классов вы создали что-то довольно сложное. К сожалению, на данный момент я не могу провести углубленный анализ: это займет слишком много времени, учитывая количество представленного кода и общность вопроса. Я могу только кратко ответить на обзор.

Для начала сортировка изменяемых данных в методах operator [] const и begin / end довольно пугающая. Этот класс не будет потокобезопасным даже для одновременного доступа к чтению. Работа с несколькими потоками, вероятно, выходит за рамки этого класса, но это поведение очень своеобразно, поэтому, вероятно, оно должно быть хорошо документировано, если класс предназначен для использования очень общего назначения.

Другая альтернатива - требовать от клиента явной сортировки вектора и использовать методы линейного доступа для извлечения данных, пока это не будет сделано. Это не так просто, как ваше решение, но оно сделает ваш класс более безопасным для использования в потоках для целей чтения.

Мне также кажется очевидным, что вы не встроили этот код с помощью профилировщика. Не делайте этого без помощи профилировщика. Я не просто излагаю здесь общие слова; Я работаю с raytracers и профильным кодом в vtune и параллельной студии ежедневно, как часть моей работы, и встраивание кода, подобного этому, отрицательно влияет на производительность. Наиболее очевидный случай связан с раздуванием кода, но есть второй, менее очевидный случай, который большинство людей, похоже, упускают из виду.

Даже для таких вещей, как однострочные средства доступа, если вы включите их все, вы помешаете оптимизатору наилучшим образом использовать регистры и другие оптимизации. Оптимизирующие компиляторы лучше всего работают на индивидуальной основе с небольшими, хорошо написанными функциями. Как правило, они не так хорошо справляются с работой на межфункциональном уровне, и если вы начнете все встроять, результат будет сродни одной большой плоской функции, обеспечивающей доступ ко всем видам данных, которые даже ICC (оптимизирующий компилятор Intel) не делает. отличная работа с Во-первых, компилятор не может прочитать ваши мысли, поэтому встраивание всего делает менее выполненные ветви оптимизированными в равной степени, а также более часто выполняемыми (в основном это ставит под угрозу способность компилятора оптимизировать общие ветви).

С помощью профилировщика вы можете видеть эти наиболее часто выполняемые ветви и вставлять их выборочно, но никогда не начинайте с встраивания: профилировщики хорошо подскажут вам, что следует рассматривать встраивание, но никогда не следует делать то, что не следует встраивать. Фактически, вы нанесете ущерб своей способности профилировать свой код, вставляя практически все при запуске.

Что касается общедоступного интерфейса, я вижу, что весь смысл в этом заключается в реализации смежности и сокращении памяти и времени доступа (используя std :: vector для бэкэнда), но, учитывая его природу, я думаю, что вам лучше сделать обеспечить интерфейс, подобный map<int, T>. Например, поведение push_back и pop_back довольно запутанное. Рассмотрим альтернативу только с методами вставки и стирания и неконстантным оператором [], который может создавать новые индексы (ключи), или сделать это хотя бы в качестве первого шага. Вы можете предоставить метод вставки, который принимает только const_reference, который выбирает доступный индекс для назначения и возвращает его (это может быть просто size () - 1, если вам не нужны пропуски).

С точки зрения реализации код кажется достаточно простым. Мне нечего предложить, кроме «деинлайн» вашего кода.

Поскольку кажется, что скорость является одним из мотивирующих факторов для создания этого, вот небольшой совет. Вместо:

inline void sort() const {
    if (!sorted() && data_.size() > 0) {
        ...
}

Подумайте об изъятии этого начального «если» и не вставляйте эту функцию в строку.Поместите это вне определения класса.Вы используете сортировку для всех видов случаев доступа только для чтения, но это исключительный случай: большая часть доступа для чтения должна работать с уже отсортированными данными.Когда у вас есть исключительные случаи, подобные этому, ваш оптимизирующий компилятор, как правило, будет работать намного лучше, если функция не встроена, и вы поставите свой чек вне:

inline const_reference operator[] (size_type i) const {
    CHECK_LT(i, size_);
    if (need_sort() )
        sort();
    ...
}

Ежедневно проводя микрооптимизациии с помощью профилировщика я могу заверить вас, что, как правило, это будет быстрее на большинстве оптимизирующих компиляторов, включая последние версии GCC, ICC и MSVC.Грубо говоря, причина в том, что ваша функция operator [] будет делать меньше и в результате получит меньше доступа к памяти (нет встроенной сортировки для обработки, которая должна выполняться только в исключительных случаях).

Самое главное, ярекомендую вам взять профилировщик и сделать несколько тестов и посмотреть, где ваши узкие места с этим.

Шаблонный класс sparse_vector: как его очистить?

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Шаблонный класс sparse_vector: как его очистить?

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы