Thread: Using std::vector as a "memory stream"

  1. #1
    Registered User
    Join Date
    Apr 2007
    Location
    Sydney, Australia
    Posts
    217

    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.
    Last edited by 39ster; 06-06-2009 at 02:40 AM.

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> 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.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Oct 2006
    Posts
    3,445
    the most common implementation is to double its capacity every time it re-allocates memory.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Elkvis View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by matsp View Post
    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.
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  7. #7
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I've read on forums before that Visual Studio (not sure which version) uses a factor of 1.5

  9. #9
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,268
    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

  10. #10
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 01-18-2006, 11:02 PM