Inserire più valori nel vettore

Question

Ho una variabile std::vector<T>. Ho anche due variabili di tipo T, la prima delle quali rappresenta il valore nel vettore dopo il quale devo inserire, mentre il secondo rappresenta il valore da inserire.

Quindi, consente di dire che ho questo contenitore: 1,2,1,1,2,2

E i due valori sono 2 e 3 rispetto alle loro definizioni di cui sopra. Poi vorrei scrivere una funzione che aggiornerà il contenitore per contenere invece:

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

Sto usando C++ 98 e spinta. Quali funzioni std o boost potrei usare per implementare questa funzione?

L'iterazione sul vettore e l'utilizzo di std :: insert è unidirezionale, ma diventa disordinato quando ci si rende conto che è necessario ricordare di saltare il valore appena inserito.

Answer 1

Questo è quello che vorrei probabilmente fare:

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); 

mettere una chiamata di prenotare in là, se vuoi. Sai che hai bisogno di spazio per almeno gli elementi original.size(). Si potrebbe anche eseguire un'iterazione iniziale sul vettore (o utilizzare std::count) per determinare l'esatta quantità di elementi da prenotare, ma senza test, non so se ciò potrebbe migliorare le prestazioni.

Answer 2

Questo è quello che probabilmente farei:

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); 
} 

ma come potete vedere, non ho potuto evitare l'Incremento lei ha citato. Ma non penso che sarebbe una cosa negativa: metterei questo codice per separare le funzioni (probabilmente in una sorta di modulo "core/utils") e - ovviamente - implementare questa funzione come modello, quindi lo scriverei solo una volta - solo una volta preoccuparsi di incrementare il valore è IMHO accettabile. Molto accettabile

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

o anche migliore (IMHO)

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

EDIT:

bene, risolverebbe problema modo leggermente diverso: primo numero di conteggio del verificarsi valore ricercato (preferibilmente memorizzare in una sorta di cache che può essere conservata e utilizzata in modo ripetibile) così ho potuto preparare l'array prima (solo un'allocazione) e usare memcpy per spostare i valori originali (per tipi come solo int, ovviamente) o memmove (se la dimensione allocata vettore è su già presente).

Answer 3

Propongo una soluzione che funzioni sul posto e in O (n) nella memoria e nel tempo O (2n). Invece di O (n^2) nel tempo dalla soluzione proposta da Laethnes e O (2n) in memoria dalla soluzione proposta da 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; 
} 

Questo algoritmo può essere buggy ma l'idea è quella di copiare solo una volta ogni elementi da:

1. In primo luogo contare quanti elementi abbiamo bisogno di inserire.
2. In secondo luogo passando i dati dalla fine e spostando ogni elemento nella nuova estremità.

Answer 4

Al posto, O (1) memoria aggiuntiva e O (n) (Live at 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]); 
    } 
}