Pregunta Insertar múltiples valores en el vector


tengo un std::vector<T> variable. También tengo dos variables de tipo T, la primera de las cuales representa el valor en el vector después del cual debo insertar, mientras que la segunda representa el valor para insertar.

Así que digamos que tengo este contenedor: 1,2,1,1,2,2

Y los dos valores son 2 y 3 con respecto a sus definiciones anteriores. Luego deseo escribir una función que actualice el contenedor para que contenga:

1,2,3,1,1,2,3,2,3

Estoy usando c ++ 98 y boost. ¿Qué funciones estándar o de refuerzo podría usar para implementar esta función?

Iterar sobre el vector y usar std :: insert es de una forma, pero se vuelve complicado cuando uno se da cuenta de que necesita recordar saltar sobre el valor que acaba de insertar.


5
2017-08-15 16:01


origen


Respuestas:


Esto es lo que probablemente haría:

vector<T> copy;
for (vector<T>::iterator i=original.begin(); i!=original.end(); ++i)
{
    copy.push_back(*i);
    if (*i == first)
        copy.push_back(second);
}
original.swap(copy);

Haga una llamada para reservar allí si lo desea. Sabes que necesitas espacio para al menos original.size() elementos. También puede hacer una iteración inicial sobre el vector (o usar std::count) para determinar la cantidad exacta de elementos para reservar, pero sin pruebas, no sé si eso mejoraría el rendimiento.


7
2017-08-15 16:13



Propongo una solución que funciona en su lugar y en O (n) en memoria y O (2n) tiempo. En lugar de O (n ^ 2) en el tiempo por la solución propuesta por Laethnes y O (2n) en la memoria por la solución propuesta por Benjamin.

// First pass, count elements equal to first.
std::size_t elems = std::count(data.begin(), data.end(), first);
// Resize so we'll add without reallocating the elements.
data.resize(data.size() + elems);
vector<T>::reverse_iterator end = data.rbegin() + elems;
// Iterate from the end. Move elements from the end to the new end (and so elements to insert will have some place).
for(vector<T>::reverse_iterator new_end = data.rbegin(); end != data.rend() && elems > 0; ++new_end,++end)
{
  // If the current element is the one we search, insert second first. (We iterate from the end).
  if(*end == first)
  {
    *new_end = second;
    ++new_end;
    --elems;
  }
  // Copy the data to the end.
  *new_end = *end;
}

Este algoritmo puede tener errores, pero la idea es copiar solo una vez cada elemento mediante:

  1. Primero, cuente cuántos elementos necesitaremos insertar.
  2. En segundo lugar, pasando por los datos del final y moviendo cada elemento al nuevo final.

3
2017-08-15 16:32



Esto es lo que probablemente haría:

typedef ::std::vector<int> MyList;
typedef MyList::iterator MyListIter;

MyList data;

// ... fill data ...

const int searchValue = 2;
const int addValue = 3;

// Find first occurence of searched value
MyListIter iter = ::std::find(data.begin(), data.end(), searchValue);

while(iter != data.end())
{
    // We want to add our value after searched one
    ++iter;

    // Insert value and return iterator pointing to the inserted position
    // (original iterator is invalid now).
    iter = data.insert(iter, addValue);

    // This is needed only if we want to be sure that out value won't be used
    // - for example if searchValue == addValue is true, code would create
    // infinite loop.
    ++iter;

    // Search for next value.
    iter = ::std::find(iter, data.end(), searchValue);
}

pero como puede ver, no pude evitar el incremento que mencionó. Pero no creo que eso sea malo: pondría este código en funciones separadas (probablemente en algún tipo de módulo "core / utils") y, por supuesto, implementaría esta función como plantilla, por lo que solo escribiría Una vez: solo una vez preocuparse por aumentar el valor es IMHO aceptable. Muy aceptable

template <class ValueType>
void insertAfter(::std::vector<ValueType> &io_data,
                 const ValueType &i_searchValue,
                 const ValueType &i_insertAfterValue);

o incluso mejor (IMHO)

template <class ListType, class ValueType>
void insertAfter(ListType &io_data,
                 const ValueType &i_searchValue,
                 const ValueType &i_insertAfterValue);

EDITAR:

bueno, resolvería el problema de una manera diferente: el primer número de conteo de la ocurrencia del valor buscado (preferiblemente almacenar en algún tipo de caché que pueda conservarse y usarse repetidamente) para poder preparar una matriz antes (solo una asignación) y usar memcpy para mover valores originales (para tipos como solo int, por supuesto) o memmove (si el tamaño asignado del vector ya es suficiente).


1
2017-08-15 16:21



En su lugar, O (1) memoria adicional y O (n) tiempo (Vive en Coliru)

template <typename T, typename A>
void do_thing(std::vector<T, A>& vec, T target, T inserted) {
    using std::swap;

    typedef typename std::vector<T, A>::size_type size_t;
    const size_t occurrences = std::count(vec.begin(), vec.end(), target);
    if (occurrences == 0) return;

    const size_t original_size = vec.size();
    vec.resize(original_size + occurrences, inserted);

    for(size_t i = original_size - 1, end = i + occurrences; i > 0; --i, --end) {
        if (vec[i] == target) {
            --end;
        }
        swap(vec[i], vec[end]);
    }
}

1
2017-08-15 17:19