Using std::vector as a "memory stream"

Would it be a good idea to use std::vector as a fast memory stream class?

Code:

---

std::vector<char> memoryStream;

---

Just wondering if the performance of this class would be sufficient as a generic memory stream class. How does it resize? (power of 2?). Is it common to use std::vector like this? I don't want to use stringstream because it's part of the IOstream library, which is too bulky for my needs.

>> Is it common to use std::vector like this? I don't want to use stringstream because it's part of the IOstream library, which is too bulky for my needs.

I'm not sure what you're getting at, but vector and iostreams aren't really used in the same context. Can you give a better example of what you're trying to do?

>> How does it resize? (power of 2?).

It depends on the implementation. The standard doesn't dictate how it's actually done.

To me, "stream" suggests data going in one end and data coming out the other. I translate that to a push_back of items, and a pop_front. That would be bad.
Perhaps a deque would be better for you.
What do you really expect this "memory stream" to be able to do? What are your needs?

The standard doesn't dictate exactly how a vector grows, BUT afaik it does require amortized-constant-time push_back, and does require that all elements are contiguous in memory. The only solution to this is to grow the vector by a constant factor. Whether the implementation grows by a factor of 1.1 or 8 or somewhere in between, that's basically what it is required to do.

the most common implementation is to double its capacity every time it re-allocates memory.

Quote:

---

Originally Posted by Elkvis

the most common implementation is to double its capacity every time it re-allocates memory.

---

Just curious how you came to that answer? How many different STL implementations have you actually looked at to determine that?

[I'm NOT saying you are wrong as such - just that it's quite a sweeping statement, and unless you have actually looked at MOST of the STL implementations available, it would be hard to say such for a fact].

--
Mats

Quote:

---

Originally Posted by matsp

Just curious how you came to that answer? How many different STL implementations have you actually looked at to determine that?

[I'm NOT saying you are wrong as such - just that it's quite a sweeping statement, and unless you have actually looked at MOST of the STL implementations available, it would be hard to say such for a fact].

--
Mats

---

I also saw that in "Effective STL" by Scott Meyers, but I haven't tried to verify it.

GNU C++'s reallocation strategy is to double.

Apache's library seems - from inspection of the source - to not allocate by a factor, but only as necessary. If this is in fact true, this is a serious bug in the implementation.

I don't know any other open-source STL implementations.

I've read on forums before that Visual Studio (not sure which version) uses a factor of 1.5

Neither GCC or VS uses a factor of 2 if my test program works:

Code:

---

#include <iostream>
#include <vector>
using namespace std;

int main()
{
        vector<int> v;
        cout << "Initial capacity is: " << v.capacity() << endl;
        for(int i = 0; i < 10; ++i)
        {
                v.insert(v.end(), v.capacity() - v.size() + 1, 0);
                cout << "New capacity is: " << v.capacity() << endl;
        }
}

---

Output from VS 2005:

Code:

---

Initial capacity is: 0
New capacity is: 1
New capacity is: 2
New capacity is: 3
New capacity is: 4
New capacity is: 6
New capacity is: 9
New capacity is: 13
New capacity is: 19
New capacity is: 28
New capacity is: 42

---

Output from GCC 4.3.3

Code:

---

Initial capacity is: 0
New capacity is: 1
New capacity is: 2
New capacity is: 4
New capacity is: 6
New capacity is: 10
New capacity is: 14
New capacity is: 22
New capacity is: 30
New capacity is: 46
New capacity is: 62

---

True, I misinterpreted the GCC code. GCC's implementation comes down to this:

Code:

---

newsize = oldsize + max(num_added, oldsize)

---

So when it runs out of space, it will allocate twice its size, or as much as needed, whichever is greater.

Let's check this against the results.
C: 0, S: 0, A: 1 -> allocate S + A = 1
C: 1, S: 1, A: 1 -> allocate S + A = 2
C: 2, S: 2, A: 1 -> allocate S + S = 4
C: 4, S: 3, A: 2 -> allocate S + S = 6
C: 6, S: 5, A: 2 -> allocate S + S = 10
C: 10, S: 7, A: 4 -> allocate S + S = 14
Yep, looks correct.