?
Solved

STL Map Class versus Vector Class

Posted on 2004-09-21
9
Medium Priority
?
616 Views
Last Modified: 2013-12-14
Hi, my question is fairly simple.  I have a quite large array of small data which up until now I've been using stl vectors for but it seems thats for my purposes maps might be better, but I'm told by some sites that its slower than vectors, and by other sites that its faster.  I was also told that hash_tables are faster but those aren't indexed so I wouldn't be able to use them.

I will also be adding the boost pool allocation method to it to speed it up further, but my question is whether or not a map is actually faster than a vector.  My goal is to find a nice array style datatype that is as fast as possible.
0
Comment
Question by:Terra_Nova
[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
  • 4
9 Comments
 
LVL 3

Expert Comment

by:Kashra
ID: 12117924
They're both fast, depending on what your use is and what you want to be doing with your data. Here's my understanding of the two.

vectors provide constant time random access, which is as fast as it gets.
maps are implemented as a binary tree, which provides log(N) access time I think. The important thing is that its significantly slower than random access into a vector.

vectors have to reallocate the array each time you add an element, so that's fairly slow for large datasets.
maps simply add a new leaf to the tree, which is again somewhere on the log(N) scale. So, for large datasets, maps have a definite advantage here.

So, if you plan on allocating all your data at once and don't change the amount of data very often, and you need random access to your data quickly, then vectors are the right choice.

But if you resize the data dynamically during the course of the program, and that is the rate limiting step, maps will be the right choice.
0
 

Author Comment

by:Terra_Nova
ID: 12118669
I wil be loading alot of data all at once during the start of my program and will be using it often, but I won't really be manipulating the data once the array is fully formed in the beginning.  The only think I'll be doing with the massive multidimensional array is reading segments over and over, but not manipulating the contents.

So in this case, a vector would process faster?
0
 
LVL 21

Expert Comment

by:MogalManic
ID: 12118934
Since you are loading your collection at the start, the map might be faster than an vector.  I say MITGHT because if you know the approximate size before the vector is loaded, then the loading of the vector would be faster.

As for accessing the data, it all depends on how your data is organized, and how you are using the data.

If you are accessing the data by finding "keys" then use Map (You could build the array as a sorted array and use a binary search, but building the sorted vector would take more time)

If you are accessing segments and/or iterating though lists of segments by index, then vector is better.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 3

Accepted Solution

by:
Kashra earned 100 total points
ID: 12119007
Generally, a "load once, access many" problem is better solved by a vector than a map. One thing to consider, if you don't require random access (reading segments over and over suggests that you might be reading them sequentially), is a list. Those resize quickly and can be accessed in linear time.

They'd be as fast as a vector, if you were always reading from front to back or back to front. But they'd be much faster resizing.

As for vectors, if you know the size of the data beforehand, as stated before, they will be much faster than any of your alternatives. You can use the reserve() or resize() functions to make sure the vectors memory gets allocated all at once.
0
 

Author Comment

by:Terra_Nova
ID: 12119146
Well I don't know the _exact_ size at start, basically I'll be taking data and splitting it up multiple times then that will be my data set for the length of the program.

Also, I won't be accessing the array exactly front beginning to end or vice versa but I will have certain positions throughou the array seperating it into segments.  I will read the contents of a segment sequencially from beginning to end but the order o segments will not be specific.  Although now thinking of it I might as well make an array of arrays for that purpose.
0
 
LVL 3

Expert Comment

by:Kashra
ID: 12119166
I'd stick to the vector implementation unless you detect an unacceptable lag during startup of your program. Most programs spend a lot more time accessing the data than they do loading it during the lifetime of the program, so that shouldn't be a problem.
0
 

Author Comment

by:Terra_Nova
ID: 12119238
One last tiny question, would a vector of vectors be any slower or faster than a larger vector in which I just point to certain positions in itself like I previously mentioned?
0
 
LVL 3

Expert Comment

by:Kashra
ID: 12119261
Probably negligible in speed difference. If you have one large vector, you don't pay for two dereferences, but you do pay for any math you have to perform to figure out the correct index into the big vector (usually more trouble than its worth).

Vector of vectors is more obvious and readable, anyway.
0
 

Author Comment

by:Terra_Nova
ID: 12119277
Alrighty, thank you very much.
0

Featured Post

Enroll in August's Course of the Month

August's CompTIA IT Fundamentals course includes 19 hours of basic computer principle modules and prepares you for the certification exam. It's free for Premium Members, Team Accounts, and Qualified Experts!

Question has a verified solution.

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

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
Here is a helpful source code for C++ Builder programmers that allows you to manage and manipulate HTML content from C++ code, while also handling HTML events like onclick, onmouseover, ... Some objects defined and used in this source include: …
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
Suggested Courses

770 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