おそらく全関数中、最も実装が大変な関数です。
insert()、emplace()、erase()の３つの関数は、要素のスライドが必要です。即ち、insert() の場合ですと、挿入する位置より後ろの要素は、一つずつ後ろにズレる必要があります。このズラす処理を、insert() と合わせて実装する必要があります。
また、insert() は５種類あるので、作業量的にも実装は大変です。
template <typename T>
class myvector
{
...
private:
using slide_switcher = realloc_switcher;
...
public:
/**
* @brief Inserts value before pos.
* @param[in] pos: Iterator before which the content will be inserted. pos may
* be the end() iterator.
* @param[in] value: Element value to insert.
* @return Iterator pointing to the inserted value.
* @throw std::length_error: If new capacity is greater than max_size().
* @throw std::bad_alloc: If malloc() (or realloc()) fails to allocate storage.
*/
iterator insert(const_iterator pos, const value_type& value)
{
// calculate distance
size_type distance = mydistance(static_cast<const_iterator>(&heap_[0]), pos, std::random_access_iterator_tag());
// re-allocate if needed
if (need_twice_capacity()) {
reallocation(twice_length(), realloc_switcher());
}
// slide elements after pos
incremental_slide(distance, 1, slide_switcher());
// set inserted element
new(&heap_[distance]) value_type(value);
size_++;
return static_cast<iterator>(&heap_[distance]);
}
/**
* @brief Inserts value before pos.
* @param[in] pos: Iterator before which the content will be inserted. pos may
* be the end() iterator.
* @param[in] value: Element value to insert.
* @return Iterator pointing to the inserted value.
* @throw std::length_error: If new capacity is greater than max_size().
* @throw std::bad_alloc: If malloc() (or realloc()) fails to allocate storage.
*/
iterator insert(const_iterator pos, value_type&& value)
{
// calculate distance
size_type distance = mydistance(static_cast<const_iterator>(&heap_[0]), pos, std::random_access_iterator_tag());
// re-allocate if needed
if (need_twice_capacity()) {
reallocation(twice_length(), realloc_switcher());
}
// slide elements after pos
incremental_slide(distance, 1, slide_switcher());
// set inserted element
new(&heap_[distance]) value_type(std::forward<value_type&&>(value));
size_++;
return static_cast<iterator>(&heap_[distance]);
}
/**
* @brief Inserts count copies of the value before pos.
* @param[in] pos: Iterator before which the content will be inserted. pos may
* be the end() iterator.
* @param[in] count: The number of copies.
* @param[in] value: Element value to insert.
* @return Iterator pointing to the inserted value.
* @throw std::length_error: If new capacity is greater than max_size().
* @throw std::bad_alloc: If malloc() (or realloc()) fails to allocate storage.
*/
iterator insert(const_iterator pos, size_type count, const value_type& value)
{
// calculate distance
size_type distance = mydistance(static_cast<const_iterator>(&heap_[0]), pos, std::random_access_iterator_tag());
if (count == 0) {
return mynext(&(heap_[0]), distance, std::random_access_iterator_tag());
}
// re-allocate if needed
size_type new_cap = expand_size(size_, count);
if (new_cap > capacity_) {
reallocation(new_cap, realloc_switcher());
}
// slide elements after pos
incremental_slide(distance, count, slide_switcher());
// set inserted element
for (size_type i = 0; i < count; i++) {
new(&heap_[distance + i]) value_type(value);
}
size_ += count;
return static_cast<iterator>(&heap_[distance]);
}
/**
* @brief Inserts elements from range [first, last) before pos.
* @param[in] pos: Iterator before which the content will be inserted. pos may
* be the end() iterator.
* @param[in] first: The first of the range of elements to insert, can't be iterators
* into container for which insert is called.
* @param[in] last: The last of the range of elements to insert, can't be iterators
* into container for which insert is called.
* @tparam InputIt: Iterator to the elements.
* @return Iterator pointing to the inserted value.
* @throw std::length_error: If new capacity is greater than max_size().
* @throw std::bad_alloc: If malloc() (or realloc()) fails to allocate storage.
*/
template <class InputIt>
iterator insert(const_iterator pos, InputIt first,
typename std::enable_if<not std::is_integral<InputIt>::value, InputIt>::type last)
{
// Switcher for mydistance(). Whether InputIt is random access iterator or input iterator.
using iterator_type = typename std::iterator_traits<InputIt>::iterator_category;
// calculate distance
size_type distance = mydistance(static_cast<const_iterator>(&heap_[0]), pos, std::random_access_iterator_tag());
if (first == last) {
return mynext(&(heap_[0]), distance, std::random_access_iterator_tag());
}
// calculate count
size_type count = mydistance(first, last, iterator_type());
// re-allocate if needed
size_type new_cap = expand_size(size_, count);
if (new_cap > capacity_) {
reallocation(new_cap, realloc_switcher());
}
// slide elements after pos
incremental_slide(distance, count, slide_switcher());
// set inserted element
pointer p = (&heap_[distance]);
for (InputIt i = first; i != last; ++i) {
new(p++) value_type(*i);
}
size_ += count;
return static_cast<iterator>(&heap_[distance]);
}
/**
* @brief Inserts elements from initializer list ilist before pos.
* @param[in] pos: Iterator before which the content will be inserted. pos may
* be the end() iterator.
* @param[in] ilist: Initializer list to insert the values from.
* @return Iterator pointing to the inserted value.
* @throw std::length_error: If new capacity is greater than max_size().
* @throw std::bad_alloc: If malloc() (or realloc()) fails to allocate storage.
*/
iterator insert(const_iterator pos, std::initializer_list<value_type> ilist)
{
// calculate distance
size_type distance = mydistance(static_cast<const_pointer>(&heap_[0]), pos, std::random_access_iterator_tag());
if (ilist.size() == 0) {
return mynext(&(heap_[0]), distance, std::random_access_iterator_tag());
}
// re-allocate if needed
size_type new_cap = expand_size(size_, ilist.size());
if (new_cap > capacity_) {
reallocation(new_cap, realloc_switcher());
}
// slide elements after pos
incremental_slide(distance, ilist.size(), slide_switcher());
// set inserted element
pointer p = (&heap_[distance]);
for (const auto& i: ilist) {
new(p++) value_type(i);
}
size_ += ilist.size();
return static_cast<iterator>(&heap_[distance]);
}
...
private:
/**
* @brief Creates and checks new container size.
* @param[in] size: current size. should be size_.
* @param[in] count: expanded size.
* @return New number of elements..
* @throw std::length_error: If (size + count) overflows or (size + count)
* is greater than the maximum size.
*/
size_type expand_size(size_type size, size_type count) const
{
size_type new_cap = size + count;
if ((new_cap < size) || (new_cap < count)) {
throw std::length_error("myvecotr::length_check()");
}
if (new_cap > MAX_SIZE) {
throw std::length_error("myvecotr::length_check()");
}
return new_cap;
}
/**
* @brief Does slide elements into incremental direction.
* value_type shall be TriviallyCopyable.
* @param[in] pos: Element index which is start position of moving.
* @param[in] count: The size of the elements to be moved.
* @param[in] trivially_copyable_tag: Function switcher according to value_type characteristic.
*/
void incremental_slide(size_type pos, size_type count, trivially_copyable_tag)
{
for (size_type i = size_ + count - 1; i >= pos + count; i--) {
heap_[i] = heap_[i - count];
}
}
/**
* @brief Does slide elements into incremental direction.
* value_type shall be MoveConstructible.
* @param[in] pos: Element index which is start position of moving.
* @param[in] count: The size of the elements to be moved.
* @param[in] move_constructible_tag: Function switcher according to value_type characteristic.
*/
void incremental_slide(size_type pos, size_type count, move_constructible_tag)
{
for (size_type i = size_ + count - 1; i >= pos + count; i--) {
new(&heap_[i]) value_type(std::move(heap_[i - count]));
heap_[i - count].~value_type();
}
}
/**
* @brief Does slide elements into incremental direction.
* value_type shall be CopyConstructible.
* @param[in] pos: Element index which is start position of moving.
* @param[in] count: The size of the elements to be moved.
* @param[in] copy_constructible_tag: Function switcher according to value_type characteristic.
*/
void incremental_slide(size_type pos, size_type count, copy_constructible_tag)
{
for (size_type i = size_ + count - 1; i >= pos + count; i--) {
new(&heap_[i]) value_type(heap_[i - count]);
heap_[i - count].~value_type();
}
}
};
補助関数を１＋３つ作成します。expand_size() は複数個の要素が挿入された後のサイズを取得する関数です。ここでは、capacity と size が同じになるようにします。（capacity を倍々ゲームで増やす戦略もありです。）
incremental_slide() は挿入に合わせて要素を後ろへズラします。後ろへズラす処理なので、要素はindexが大←小の方向へ代入されます。代入に要する演算子に応じて、３つの関数を用意しています。
insert() の中身は、①挿入後のサイズ計算、②領域確保、③既存要素の移動、④新要素の代入、という流れになります。これは５つの insesrt() どれも共通です。
全ソースコード： https://github.com/suomesta/myvector/tree/master/026
0 件のコメント:
コメントを投稿