Adding to middle of std::vector

Question

Is there a way to add values to the middle of a vector in C++? Say I have:

vector <string> a;
// a gets filled up with "abcd", "wertyu", "dvcea", "eafdefef", "aeefr", etc

and I want to break up one of the strings and put all of the pieces back into the vector. How would I do that? the strings I break can be anywhere, index = 0, somewhere in the middle, or index = a.size() - 1.

Calvincalvina

Answer 1

You can insert into a vector at position i by writing

v.insert(v.begin() + i, valueToInsert);

However, this isn't very efficient; it runs in time proportional to the number of elements after the element being inserted. If you're planning on splitting up the strings and adding them back in, you are much better off using a std::list, which supports O(1) insertion and deletion everywhere.

Amundson

oh well. my vector is quite short, so performance isnt an issue. yet. and i think i have to use vectors for some reason or another. i have to check – Calvincalvina

Performance all depends on the amount of data in question. I find vector to be quite good for performance compared to list up to a half-meg or so. – Worrywart

Really long std::lists<> get crappy performance because the CPU cannot do cache prefetch and each link is an indirect pointer lookup. – Worrywart

Stating a std::list has O(1) insertion was always a little misleading to me. Assuming you already know exactly where you want to insert (and have a pointer to it), its O(1). However, if you first need to find() the location to insert-- its O(n) to find, and then O(1) to insert, right? – Industrialize

It's not only the amount of data, it's also the complexity of copying/assigning the objects. If copying is expensive, a list could very well be better. – Aida

@JaredC- Yes, that's true. However, in the context of the OP's problem (where the location of the string being split is known), we can separate this time out from the rest of the time. – Amundson

Consider using a std::deque. – Owen

@wilhelmtell- std::deque does not support O(1) insertion or deletion at arbitrary points; however, it is a great choice if the insertions are always at the beginning or end. – Amundson

Answer 2

You can do that, but it will be really slow:

int split = 3; // where to split
a.insert(a.begin()+index, a[index].substr(0, split));
a[index+1] = a[index+1].substr(split);

Canotas

Answer 3

in this example dynamically find the vector middle and insert new element.

std::vector <std::string> friends;

friends.push_back("Ali");
friends.push_back("Kemal");
friends.push_back("Akin");
friends.push_back("Veli");
friends.push_back("Hakan");
    
// finding middle using size() / 2
int middleIndexRef = friends.size() / 2;

friends.insert(friends.begin() + middleIndexRef, "Bob");

Lithomarge