Method insert

cpp/src/arrow/util/small_vector.h:393–424

  template <typename InputIt>
  iterator insert(const_iterator insert_at, InputIt first, InputIt last) {
    const size_t n = storage_.size_;
    const size_t it_size = static_cast<size_t>(last - first);  // XXX might be O(n)?
    const size_t pos = static_cast<size_t>(insert_at - const_data_ptr());
    storage_.bump_size(it_size);
    auto* p = storage_.storage_ptr();
    if (it_size == 0) {
      return p[pos].get();
    }
    const size_t end_pos = pos + it_size;

    // Move [pos; n) to [end_pos; end_pos + n - pos)
    size_t i = n;
    size_t j = end_pos + n - pos;
    while (j > std::max(n, end_pos)) {
      p[--j].move_construct(&p[--i]);
    }
    while (j > end_pos) {
      p[--j].move_assign(&p[--i]);
    }
    assert(j == end_pos);
    // Copy [first; last) to [pos; end_pos)
    j = pos;
    while (j < std::min(n, end_pos)) {
      p[j++].assign(*first++);
    }
    while (j < end_pos) {
      p[j++].construct(*first++);
    }
    assert(first == last);
    return p[pos].get();
  }

  void resize(size_t n) {
    const size_t old_size = storage_.size_;