c++ - sparse_vector 模板类：如何清理它？

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 << "]";
}

Answer 1

对于没有编写类模板经验的人来说，您已经创建了一些相当复杂的东西。不幸的是，我目前无法进行深入分析：给出所呈现的代码数量和问题的普遍性需要太多时间。我只能简要地回答一个概述。

首先，在 operator[] const 和 begin/end 方法上对可变数据进行排序有点吓人。即使对于并发读取访问，此类也不是线程安全的。处理多线程可能超出了这个类的范围，但是这种行为是非常特殊的，所以如果这个类是为非常通用的用途而设计的，它可能应该有很好的文档说明。

另一种选择是要求客户端显式地对向量进行排序并使用线性访问方法来获取数据，直到完成。这并不像您的解决方案那样自动化，但它将使您的类更安全地跨线程使用以进行读取。

在我看来，您没有在分析器的帮助下内联此代码似乎也很明显。没有探查器的帮助，不要这样做。我不只是在这里泛泛而谈。作为我工作的一部分，我每天都使用 vtune 和并行工作室使用光线追踪器和配置文件代码，并且像这样的内联代码会对性能产生不利影响。最明显的情况是由于代码膨胀，但还有第二个不太明显的情况，大多数人似乎都忽略了。

即使对于单行访问器之类的东西，如果将它们全部内联，也会干扰优化器充分利用寄存器和其他优化的能力。使用编写良好的小型函数，逐个函数地优化编译器效果最好。它们通常在函数间级别上做得不那么好，如果你开始内联所有内容，结果类似于一个大型平面函数访问各种数据，即使 ICC（英特尔的优化编译器）也不会这样做处理得很好。首先，编译器无法读懂您的想法，因此内联所有内容会使执行较少的分支与更常执行的分支同样优化（基本上会损害编译器优化公共分支的能力）。

使用分析器，您可以看到这些更常执行的分支并有选择地内联它们，但永远不要从内联开始：分析器会很好地告诉您应该考虑内联的内容，但绝不会告诉您不应该内联的内容。事实上，当你开始内联几乎所有内容时，你会严重破坏你分析代码的能力。

至于公共接口，我可以看到这样做的全部目的是实现连续性并减少内存和访问时间（使用 std::vector 作为后端），但考虑到它的性质，我认为你最好提供一个接口类似于map<int, T>。例如， push_back 和 pop_back 行为相当令人困惑。考虑仅具有插入和擦除方法的替代方法以及可以创建新索引（键）的非常量运算符 []，或者至少作为第一步执行此操作。您可以提供一个 insert 方法，该方法仅采用 const_reference 选择要分配的可用索引并返回它（如果您不关心间隙，它可能只是 size() - 1）。

从实现的角度来看，代码看起来很简单。除了“取消内联”您的代码之外，我没有太多建议。

由于看起来速度似乎是创建它的激励因素之一，所以这里有一个小提示。代替：

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

考虑去掉最初的“if”，不要内联这个函数。把它放在类定义之外。您将 sort 用于所有类型的只读访问情况，但这是一个例外情况：大多数读取访问应该对已排序的数据进行操作。当你有这样的例外情况时，如果函数没有内联并且你把检查放在外面，你的优化编译器通常会做得更好：

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

每天都在分析器的帮助下进行微优化，我可以向您保证，在大多数优化编译器（包括最新版本的 GCC、ICC 和 MSVC）上，这通常会更快。粗略地说，原因是因为您的 operator[] 函数将执行较少的操作并因此访问较少的内存（没有内联排序来处理，只应在特殊情况下执行）。

最重要的是，我建议您使用分析器并进行一些测试，看看您的瓶颈在哪里。