Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

stack vs heap for vector

Posted on 2014-01-02
7
Medium Priority
?
1,225 Views
Last Modified: 2014-01-03
I have the following structure
class MyClass {
std::vector<struct_1> struct_list_1;
std::vector<struct_2 *> struct_list_2

};

class MainClass {
    MyClass obj;
}

Open in new window

If I keep on pushing elements to both the vectors, does the run stores everything on stack or heap? I just want to make sure, it does not run out of stack space.
0
Comment
Question by:perlperl
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 2
7 Comments
 
LVL 86

Accepted Solution

by:
jkr earned 1200 total points
ID: 39752994
All allocations within a std::vector will be made on the heap, thus leaving your stack space alone - nothing to worry about it. This is one of the charming aspects of containers ;o)

Just as a side note, if your vector varies in size a lot, you might want to consider using a 'list' instead, since that will reduce the chances of heap fragmentation when you store a lot of data in it.
0
 
LVL 40

Assisted Solution

by:evilrix
evilrix earned 800 total points
ID: 39753283
I'd strongly recommend pushing items by value unless you plan to use smart pointers. If you push items by pointer you'll either have to manage a separate list of them or allocate them on the heap first. This then means you'll have to be sure to free up these items before the vector destructs or you'll leak memory (each item in the vector).

My article about STL containers and which to choose for different jobs may be helpful. It discusses the difference between the different containers (including list and vector, as jkr has alluded) and helps you choose the right one for the job at hand.

http://evilrix.com/2012/12/02/which-stl-container/
0
 
LVL 40

Expert Comment

by:evilrix
ID: 39753292
>> since that will reduce the chances of heap fragmentation when you store a lot of data in it.
I don't know that it'll help with fragmentation (it might actually make it worse since list allocates separately for each item whereas the vector's memory is contiguous) but if you are doing lots of appends and you can't pre-size the vector at the start (because you can't estimate how big it will grow) you might find a list is better.

That said, I would nearly always choose a vector over a list as 9 times out of 10 it will be more efficient in terms of memory usage and performance. The amortised time for appending, in both cases, is O(1), and whilst the vector does need to resize if it exceeds its internal buffer, this normally uses a power of 2 strategy (it doubles in size each time), which is generally efficient enough for most circumstances. On resize (and only on resize) the asymptotic time for appending to a vector is O(N), where N is the current size of the vector.

Personally, I'd start with a vector and consider a list only if profiling suggested the vector wasn't performant enough.

Just my 2 cents :)
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 

Author Comment

by:perlperl
ID: 39753786
Thats a really nice document. Its very helpful

But isn't deque much better (instead of list) than vector. As it provides pretty much all functionality that vector does (except reserve and capacity which I don't even use in my case).  In my case I only insert in the back (no insertion or deletion in the middle)

Also good thing about deque is it doesn't use continous memory like vector and growing a deque is much efficient than vector.
0
 
LVL 40

Expert Comment

by:evilrix
ID: 39753882
>> But isn't deque much better (instead of list) than vector.
It depends. Generally, vector is the best generic container and when you're not sure which to use start with a vector and use profiling to determine if you need to change. If your use case specifically draws on the benefits of another container then it is certainly worth trying that too. Ultimately, it's better to profile than to guess but if you have to guess then vector is normally your best first choice.

FWIW, The C++ Standard, section 23.1.1, says:

"vector is the type of sequence that should be used by default... deque is the data structure of choice when most insertions and deletions take place at the beginning or at the end of the sequence."
0
 
LVL 40

Expert Comment

by:evilrix
ID: 39753891
Herb Sutter has an interesting view on this. Who am I to argue with him? :)

http://www.gotw.ca/gotw/054.htm
0
 

Author Comment

by:perlperl
ID: 39753981
Earlier yesterday I read the same article and thought deque was best ;)

It seems at the end of the day different people have different views on STL. As you said one should profile and use the appropriate one :)

Thanks!
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

618 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question