Solved

STL Map Class versus Vector Class

Posted on 2004-09-21
9
608 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
  • 4
  • 4
9 Comments
 
LVL 3

Expert Comment

by:Kashra
Comment Utility
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
Comment Utility
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
Comment Utility
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
 
LVL 3

Accepted Solution

by:
Kashra earned 25 total points
Comment Utility
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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 

Author Comment

by:Terra_Nova
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
Alrighty, thank you very much.
0

Featured Post

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
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 be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

762 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

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!

Get 1:1 Help Now