Написание пользовательской функции вставки для std :: vector - PullRequest
Новая
       1

Написание пользовательской функции вставки для std :: vector

0 голосов
/ 21 января 2020

Я писал функцию вставки для std :: vector для моего личного проекта.

Векторный макет перед вставкой: 

position : 0 1 2 3 4
Value    : a b c e f

Предполагается, что емкости достаточно Я хочу вставить 'd' в позиции 3.

Векторный макет после вставки: 

position : 0 1 2 3 4 5
Value    : a b c d e f

Я написал функцию для смещения значений вправо после заданной позиции вставки (в в примере это 3), а затем я присваиваю заданное значение в запрошенной позиции вставки.

Функция, которую я написал для shift_right, выглядит следующим образом: 

template <typename T>
void vector<T>::shift_right(typename vector<T>::iterator given_pos) {
    for (auto iter = end() - 1; iter != given_pos - 1; iter--) {
        *(iter + 1) = *iter;
    }
}

Есть ли std :: алгоритма , или его вариант, который может помочь мне избавиться от моего необработанного l oop в функции shift_right?

Ответы [ 3 ]

1 голос
/ 21 января 2020

Кажется, вы имеете в виду что-то вроде следующего: 

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

template <typename T>
typename std::vector<T>::iterator 
shift_right( std::vector<T> &v, typename std::vector<T>::size_type pos )
{
    v.resize( v.size() + 1 );

    typename std::vector<T>::iterator result = std::end( v );

    if ( pos < v.size() )
    {
        result = std::copy_backward( std::next( std::begin( v ), pos ), 
                                     std::prev( std::end( v  )),
                                     std::end( v ) );
    }

    return std::prev( result ); 
}

int main() 
{
    std::vector<int> v;

    auto it = shift_right( v, v.size( ) );

    *it = 2;

    for ( const auto &item : v ) std::cout << item << ' ';
    std::cout <<'\n';

    it = shift_right( v, v.size() );
    *it = 3;

    for ( const auto &item : v ) std::cout << item << ' ';
    std::cout <<'\n';

    it = shift_right( v, 0 );
    *it = 0;

    for ( const auto &item : v ) std::cout << item << ' ';
    std::cout <<'\n';

    it = shift_right( v, 1 );
    *it = 1;

    for ( const auto &item : v ) std::cout << item << ' ';
    std::cout <<'\n';

    return 0;
}

Выход программы: 

2 
2 3 
0 2 3 
0 1 2 3

Обратите внимание, что лучше использовать std::copy_backward вместо std::move_backward потому что в первом случае состояние всех элементов вектора будет согласованным аналогично элементам массива фундаментальных типов после их смещения.

Если использовать std::move_backward, то соответствующая функция может выглядеть следующим образом как показано в демонстрационной программе ниже. 

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

template <typename T>
typename std::vector<T>::iterator 
shift_right( std::vector<T> &v, typename std::vector<T>::size_type pos )
{
    v.resize( v.size() + 1 );

    typename std::vector<T>::iterator result = std::end( v );

    if ( pos < v.size() )
    {
        result = std::move_backward( std::next( std::begin( v ), pos ), 
                                     std::prev( std::end( v  )),
                                     std::end( v ) );
    }

    result = std::prev( result );
    *result = T();

    return result; 
}

int main() 
{
    std::vector<int> v = { 1, 2, 4, 5, 6 };

    for ( const auto &item : v ) std::cout << item << ' ';
    std::cout <<'\n';

    auto it = shift_right( v, 2 );

    for ( const auto &item : v ) std::cout << item << ' ';
    std::cout <<'\n';

    *it = 3;

    for ( const auto &item : v ) std::cout << item << ' ';
    std::cout <<'\n';

    return 0;
}

Вывод программы: 

1 2 4 5 6 
1 2 0 4 5 6 
1 2 3 4 5 6
1 голос
/ 21 января 2020

Вы можете использовать std::move_backward: 

template< class BidirIt1, class BidirIt2 ><br>
BidirIt2 move_backward( BidirIt1 first, BidirIt1 last, BidirIt2 d_last );

Перемещение элементов из диапазона [first, last) в другой диапазон, заканчивающийся на d_last. Элементы перемещаются в обратном порядке (последний элемент перемещается первым), но их относительный порядок сохраняется.

Таким образом, ваш код может выглядеть так (не проверено): 

template <typename T>
void vector<T>::shift_right(typename vector<T>::iterator given_pos) {
    std::move_backward(given_pos, end()-2, end()-1);
}

Предполагается, что емкость уже была увеличена, если это необходимо, и что end() возвращает новый конечный итератор (т. Е. Один за последним элементом после вставки нового пространства). Измените на std::move_backward(given_pos, end()-1, end());, если это не так.

0 голосов
/ 21 января 2020

Сначала я определил бы шаблон вспомогательной функции, right_shift_by_one(), который сдвигает элементы вправо на одну позицию в допустимом диапазоне итераторов [first, last): 

template<typename BidirIt>
void right_shift_by_one(BidirIt first, BidirIt last) {
   std::move_backward(first, std::prev(last), last);
}

Затем ваша пользовательская функция-член shift_right(), которая в конечном итоге вызывает вспомогательную функцию, определенную выше: 

template<typename T>
auto shift_right(typename vector<T>::iterator pos) {
   auto dist = std::distance(begin(), pos);

   // this only compiles if T is default constructible
   resize(size()+1);

   // resize() may have invalidated the pos iterator due to vector's reallocation
   // recompute it
   pos = begin() + dist;

   right_shift_by_one(pos, end());
   return pos;
}

Эта функция-член возвращает итератор, указывающий на элемент, соответствующий новому пространству, созданному смещением вправо. Это работает, даже если вектор не имеет достаточной пропускной способности, потому что была принята во внимание недействительность итераторов при перераспределении. Вы должны реализовать resize() в своей пользовательской векторной реализации.

Использование: 

auto it = shift_right(vec.begin() + 2);
*it = 'c';
...