Selfappending vector

Hello,

I've got a strange problem:

#include <vector>
#include <iostream>
#include <string>

int main(){
std::vector<std::string> strvec;
strvec.push_back("A");
strvec.push_back("B");
strvec.push_back("C");
strvec.push_back("D");
strvec.push_back("E");

std::vector<std::string>::size_type i = strvec.size()-1;
for(;i>0;--i)
strvec.push_back(strvec[i-1]);

for each(std::string str in strvec)
std::cout << str << ',';

return 0;
}

Gives me;
A,B,C,D,E,D,,B,A

What am I doing wrong?

You have a vector containing only std::strings and you asked to get every std::string out of strvec here

Code:

---

for each(std::string str in strvec)
std::cout << str << ',';

---

That is what you are doing wrong. What do you exactly want to do?

Thats even stranger. The origenal program is longer than this example.
In the original A,B,C and D are "real" strings.
A for example is X10, B is pauze, C is Y20, D is pauze and E is X-20.

In my program I would like the resulting vector to contian;
("X10","pauze","Y20","pauze","X-20","pauze","Y20","pauze","X10")

But the resulting vector in my program contains;
("X10","pauze","Y20","pauze","X-20","pauze","","pauze","X10")

Thanks for the fast reply, btw.

Give me a second, ill try to fix it myself first then explain it to you.

Well, the output at me is

Quote:

---

Originally Posted by Output

A,B,C,D,E,D,C,B,A

---

o_o.

Nope, keep having this problem. Maybe it's my intel atom, or it's because I'm using visual studio 2008.

However...

for(;i>0;--i){
std::string str = strvec[i-1];
strvec.push_back(str);
}

works.

Thank you very much.

Quote:

---

Originally Posted by po0ky

for each(std::string str in strvec)
std::cout << str << ',';

return 0;
}

Gives me;
A,B,C,D,E,D,,B,A

What am I doing wrong?

---

Use your debugger. What does the vector actually contain? Does it have the items?

Regards,

Paul McKenzie

No, according to the debugger the vector holds all the items the cout is giving me.

Pynolathgeen seems to get the expected results.
Thats why I think its a bug in my compiler.

@Pynolathgeen what compiler are you using?

Quote:

---

Originally Posted by po0ky

No, according to the debugger the vector holds all the items the cout is giving me.

Pynolathgeen seems to get the expected results.
Thats why I think its a bug in my compiler.

---

I don't think it's a bug in the compiler at all. Take a look at this line of code carefully:

Code:

---

strvec.push_back(strvec[i-1]);

---

Do you see the problem with this line of code? The problem is that you're modifying the vector that you're reading from. The push_back() takes a reference to the item to add. You are giving a reference, but at the same time, you're changing the container that gives you that reference. Therefore the behaviour is undefined.

For example, what if adding an item causes a reallocation to occur? That reference you passed is no longer valid, and I have a suspicion this is the reason why your code didn't work -- a reallocation was done, the reference is refering to junk, and you get a blank that is added.

So the bottom line is that there is no such thing as a "self-appending vector" in the sense that you can't call push_back() with a reference to one of the vector's items.

Regards,

Paul McKenzie

Quote:

---

Originally Posted by Paul McKenzie

Do you see the problem with this line of code? The problem is that you're modifying the vector that you're reading from. The push_back() takes a reference to the item to add. You are giving a reference, but at the same time, you're changing the container that gives you that reference. Therefore the behaviour is undefined.

For example, what if adding an item causes a reallocation to occur? That reference you passed is no longer valid, and I have a suspicion this is the reason why your code didn't work -- a reallocation was done, the reference is refering to junk, and you get a blank that is added.

So the bottom line is that there is no such thing as a "self-appending vector" in the sense that you can't call push_back() with a reference to one of the vector's items.

---

Good point, though it seems to me that the conclusion is rather pessimistic. Wouldn't this be okay?

Code:

---

strvec.push_back(string(strvec[i - 1]));

---

But taking another look at the problem, it seems that the aim is to insert to the same vector the elements of the vector starting from the second last element to the first element. Keeping in mind that reallocation could be a problem, would this solution be feasible?

Code:

---

strvec.reserve(strvec.size() * 2 - 1);
strvec.insert(strvec.end(), strvec.rbegin() + 1, strvec.rend());

---

As long as strvec has at least one element, I think that the above snippet should work.

Quote:

---

Originally Posted by laserlight

Good point, though it seems to me that the conclusion is rather pessimistic. Wouldn't this be okay?

---

This should work.
You use the reference to create a temporary string object (safe)
You use the temporary string object to add to a vector (safe)
the fact it's the same vector in this case isn't a problem anymore. At the moment you do the add, the reference used to create the temporary string will be invalid, but you have made a copy of the contents.

Quote:

---

would this solution be feasible?

Code:

---

strvec.reserve(strvec.size() * 2 - 1);
strvec.insert(strvec.end(), strvec.rbegin() + 1, strvec.rend());

---

---

It will probably appear to work. But I'm not sure it's guaranteed (but my experience with stl isn't perfect).
if I read the documentation for reserve(), it would appear it's valid to implement this by making sure you have the required storage (by allocating a new location for the aray), but not actually copy the array to the new location until necessary.

In practice, I think the reserve method will work, however ...

Concening the last 2 arguments, according the standard, the
pre condition for the last two arguments is that they are not
iterators into the vector (Table 67)

Indeed. So, does the motivation behind that pre-condition also invalidate the use of std::copy with std::back_inserter?

There I go blaming the compiler again. Thanks Paul McKenzie I think I understand the problem better now.

Quote:

---

Originally Posted by laserlight

Good point, though it seems to me that the conclusion is rather pessimistic. Wouldn't this be okay?

Code:

---

strvec.push_back(string(strvec[i - 1]));

---

---

I think this would be a good solution, if not the only solution.
I'll try it right away.

You could also do this using a second, temporary vector:

Code:

---

  vector<string> vec, temp;
  vec.push_back("A");
  vec.push_back("B");
  vec.push_back("C");
  vec.push_back("D");
  vec.push_back("E");
  copy(vec.rbegin()+1, vec.rend(), back_inserter(temp));
  vec.insert(vec.end(), temp.begin(), temp.end());

  copy(vec.begin(), vec.end(), ostream_iterator<string>(cout, " "));

---

Output is

Code:

---

A B C D E D C B A

---

Quote:

---

Originally Posted by cilu

You could also do this using a second, temporary vector:

---

If you want to involve a second vector, then I suggest declaring temp near first use:

Code:

---

vector<string> vec;
vec.push_back("A");
vec.push_back("B");
vec.push_back("C");
vec.push_back("D");
vec.push_back("E");

vector<string> temp(vec.rbegin() + 1, vec.rend());
vec.insert(vec.end(), temp.begin(), temp.end());

---

Right, that is actually even better. ;)

Quote:

---

Originally Posted by cilu

You could also do this using a second, temporary vector:

---

I'm sorry but... thats just awfull, slow and sluggish.

Quote:

---

Originally Posted by po0ky

I'm sorry but... thats just awfull, slow and sluggish.

---

Did you time it?

And no, you can't tell by eyeballing STL code and determine it is slow and sluggish -- too many have made that mistake, and then are shocked that the code is not sluggish at all (once a release, optimized build is produced).

Edit: For Visual C++, you have to set as your preprocessor _SECURE_SCL=0 to make sure iterators are not checked in the release build. Once you do that and produce a release build, then do timing tests. Don't bother posting debug build timing tests, no one will look at them, as they're meaningless.

Regards,

Paul McKenzie

Quote:

---

Originally Posted by Paul McKenzie

Did you time it?

---

How did you know that?

Quote:

---

And no, you can't tell by eyeballing STL code and determine it is slow and sluggish -- too many have made that mistake, and then are shocked that the code is not sluggish at all (once a release, optimized build is produced).

---

It's as if you are looking over my shoulder.

Quote:

---

Edit: For Visual C++, you have to set as your preprocessor _SECURE_SCL=0 to make sure iterators are not checked in the release build. Once you do that and produce a release build, then do timing tests. Don't bother posting debug build timing tests, no one will look at them, as they're meaningless.

---

o_0... I gues i'm still a real noob...

Well I did the timing again, and my god you are right. Cilu's method is faster.

I wonder if there is an even faster way?

Quote:

---

Originally Posted by po0ky

It's as if you are looking over my shoulder.

---

No, not really. A lot of times we get posts from persons who either are just (as I said) eyeballing STL code, and assume "it's slow" because it uses a function object, or a class, or doesn't use pointers all over the place, whatever.

Or we get persons who time debug builds and claim "STL is 10 times slower than when I use pointers". Of course after telling the person to build a release build using the preprocessor _SECURE_SCL=0, then their non-STL code is no faster, and most times, slower than the STL version.

Many programmers believe that if they use a lot of pointers and/or dynamically allocate memory themselves using new[]/delete[] all over the place, that their code is faster than using STL containers and algorithms correctly. The problem is that an overuse of pointers causes the compiler's optimizer to not attempt to optimize the code, due to excessive pointer aliasing by the programmer. Excessive pointer aliasing renders an optimizer practically useless.

With STL, the compiler is well aware of the constructs used, and can optimize the code efficiently (inlining, for example). That's one underlying cause of why "pointered-up" code and STL code that uses little to no pointers seem to be on a par when it comes to speed, with the STL code many times beating the non-STL code.

Quote:

---

Well I did the timing again, and my god you are right. Cilu's method is faster.

---

Not surprising.

Regards,

Paul McKenzie

well it doesn't surprise me it's faster. But for other reasons.

The original implementation does a potential resize (alloc, copy, dealloc) on each insert.
Additionally, it creates a temporary string on each insert.

The temporary vector solution of Cilu pulls ahead because it avoids the above overhead, but does so at the cost of an additional chunk of memory.
Don't have acces to a compiler atm, , but I'd expect the following to be even faster:

Code:

---

int iSize = vec.size();
vec.resize(iSize*2-1);
for (int i=1; i<iSize;i++)
    vec[iSize-1+i]=vec[iSize-1-i];

---

Quote:

---

Originally Posted by OReubens

The original implementation does a potential resize (alloc, copy, dealloc) on each insert.

---

The same amortised expansion happens when std::back_inserter is used though, unless po0ky tested with my suggested modification instead, in which case it might be more like your suggestion. A variant of your suggestion:

Code:

---

const std::vector<std::string>::size_type old_size = strvec.size();
strvec.resize(old_size * 2 - 1);
const std::vector<std::string>::iterator old_end = strvec.begin() + old_size;
std::reverse_copy(strvec.begin(), old_end - 1, old_end);

---

Quote:

---

Originally Posted by laserlight

A variant of your suggestion:

Code:

---

const std::vector<std::string>::size_type old_size = strvec.size();
strvec.resize(old_size * 2 - 1);
const std::vector<std::string>::iterator old_end = strvec.begin() + old_size;
std::reverse_copy(strvec.begin(), old_end - 1, old_end);

---

---

I think we have a winner. This could probably only be faster if the size of the resulting vector would be hard coded.

I have read somewhere that lists are faster in sequential processing, but even with lists I couldn't make this run faster.