Thread: Speed in array or list structure

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    110

    Speed in array or list structure

    I have a program where I tried the vector structure to store number. A small vector is declared filled and then push_back is used to store numbers as they pop up. However, this is quite slow. I java, which is my first language, I use lists or arrays to do this, but in c++ I'm not sure of how to choose, performance wise.

    The program stores between 0 to 10000 integers. So should I go with a list or an array.
    Code:
    List
    node | node
    data | data
    Just add a node when a number pops up.

    Code:
    Array[1000] = {data, data, etc...}
    Redeclare if array is full and copy the old, then insert new numbers.

    I usually lean against list as I think it's easier, no tinkering with arrays that's to small. But when I read papers on the subject it seems many c++ coders are using vectors and arrays to do this kind of stuff. Is there a reason for this, speed wise, or have I just stumbled upon gnarly papers..?

  2. #2
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    An array (vector) will always give you better random access time.
    But it is faster to remove or insert something in case of a list.
    Choose the correct one suitable for the purpose at hand.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by überfuzz
    I have a program where I tried the vector structure to store number. A small vector is declared filled and then push_back is used to store numbers as they pop up. However, this is quite slow.
    push_back on a vector runs in amortised constant time.

    A likely reason for what you observe as a performance problem is that your standard library implementation comes with safety features for standard containers enabled by default. This is a Good Thing, but if speed is needed, it becomes bad, and you should disable the checking. How to do that depends on your standard library implementation (and compiler).

    Quote Originally Posted by überfuzz
    The program stores between 0 to 10000 integers. So should I go with a list or an array.
    If you know that you are going to store up to 10000 integers, then a possible solution is to just use a fixed size array (or the std::array<int, 10000> equivalent). Choosing between std::vector and std::list would depend on how you are going to use the list of numbers.

    Quote Originally Posted by überfuzz
    Redeclare if array is full and copy the old, then insert new numbers.
    That does not make sense. You cannot change an array's size at run time.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Mhmm, I guess a list is more robust in my case. The program is going to run on different compilers.

    About the standard list library, is it good or should I set up my own list class..?

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by überfuzz
    Mhmm, I guess a list is more robust in my case.
    More robust than what? I presume that by "list" you mean "linked list", and a linked list is not "more robust" than an array or std::vector.

    Quote Originally Posted by überfuzz
    The program is going to run on different compilers.
    I think you mean "be compiled" rather than "run", but what has that got to do with choosing to use a linked list? It looks like you are making a choice based on incorrect assumptions.

    You should be talking about how you are going to access the numbers. Without that information, saying that "I usually lean against list as I think it's easier" is rubbish.

    Quote Originally Posted by überfuzz
    About the standard list library, is it good or should I set up my own list class..?
    I am stunned by that question. The questions that you have asked in this thread indicate that you are not an expert, but the way you so casually dismiss a standard library component as being potentially not up to scratch makes it seem like you are an expert who already has a set of custom components ready for use.
    Last edited by laserlight; 03-30-2012 at 10:48 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Quote Originally Posted by laserlight View Post
    More robust than what? I presume that by "list" you mean "linked list", and a linked list is not "more robust" than an array or std::vector.


    I think you mean "be compiled" rather than "run", but what has that got to do with choosing to use a linked list? It looks like you are making a choice based on incorrect assumptions.

    You should be talking about how you are going to access the numbers. Without that information, saying that "I usually lean against list as I think it's easier" is rubbish.


    I am stunned by that question. The questions that you have asked in this thread indicate that you are not an expert, but the way you so casually dismiss a standard library component as being potentially not up to scratch makes it seem like you are an expert who already has a set of custom components ready for use.
    I'm not posting here to keep up awake at night, sorry for causing such a reaction. Not sure I want to address your questions or whatever the things you wrote should be called. However, I believe wrote that I'm use to work with java, not C++ hence my questions and inexperience. Further, for someone with some code experience it should then be quite obvious that I don't know much about how different libraries preforms in C++. Peace out!

  7. #7
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    You haven't specified what you're going to do with your number list.

    Are you only going to add number to the end? Or do you need to "insert" numbers in the middle?

    Do you need "random access", i.e., do you need to access them other than linearly (from beginning to end)?
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  8. #8
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Quote Originally Posted by oogabooga View Post
    You haven't specified what you're going to do with your number list.

    Are you only going to add number to the end? Or do you need to "insert" numbers in the middle?

    Do you need "random access", i.e., do you need to access them other than linearly (from beginning to end)?
    Hi! Actually, I think it might be beneficial to leave it open, as I'm not sure of what data needs to be stored. The integers are going to be there for sure, but I was told, just now, that there are other things that needs to be stored.

    Do you mean that the content will limit my choice? I guess a linked list wont limit the content... Isn't it possible to have an array populated by objects in C++?

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    No, the content never limits your choice.
    Nothing you have mentioned allows for a definite answer yet. So far you can only go by the rule that says "vector is the default choice".
    If you really want the correct answer as to whether std::vector or std::list etc is best, then you must tell us what kind of things will you be doing with the data. Answer as many of these questions as possible:

    Will you need random access to the data?
    Does the order of items matter?
    Will you be inserting or removing items from anywhere other than the end?
    Do you need to keep the data in sorted order?
    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"

  10. #10
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    I didn't think anyone would take on the task of trying to answer so precisely. More like, here's an article about C++ - list vs vector, etc. But thanks for the effort to make sence of what I post. :-)

    Quote Originally Posted by iMalc View Post
    Will you need random access to the data?
    No.
    Quote Originally Posted by iMalc View Post
    Does the order of items matter?
    No.
    Quote Originally Posted by iMalc View Post
    Will you be inserting or removing items from anywhere other than the end?
    Enywhere just store data, end is fine. (But if you have the position working inside list is no problem.)
    Quote Originally Posted by iMalc View Post
    Do you need to keep the data in sorted order?
    Nope.

    So my main suspect is linked list. Now if I'm allowed digress off topic once again. When I read about LIST in the reference I see functions such as unique, sort, merge, etc, and how they're used, but not a word about their complexity? I guess the folks writing these libraries knows what they're doing, but isn't it buying the pig in the poke if you don't know these things..? So, once again, if someone could shade some light I'd go -->
    Last edited by überfuzz; 03-30-2012 at 04:05 PM.

  11. #11
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by überfuzz View Post
    sure I want to address your questions or whatever the things you wrote should be called.
    Laserlight was just pointing out that the factors you are using to select a container, and the questions you are asking, are actually irrelevant to making such a choice.

    You are fundamentally missing the point, which others have said, that the requirements that determine choice of container are independent of type type of data you will put into the container. The requirements are based on factors like how often your code will add and remove elements from the container versus how often it will retrieve elements.

    The compiler and library you are using is also irrelevant to choice of container. If you need to use a vector, in C++, #include <vector>. If you need to use a list, #include <list>. <vector> and <list> are not libraries. They are header files that specify interface to parts of the C++ library.

    Quote Originally Posted by überfuzz View Post
    However, I believe wrote that I'm use to work with java, not C++ hence my questions and inexperience.
    The questions you're asking would be equally irrelevant to choice of container if you asked them in a Java forum.

    The basic properties of containers (vector versus linked list versus .... ) are independent of programming language. It is the properties you need that decide what container you use.


    Basically, I recommend you use vector. That is the default choice of container, when you don't know (or in your case, apparently can't describe) what requirements the container must meet.

    And, given your clear lack of understanding, you will be better off using a standard container rather than rolling your own.


    Quote Originally Posted by überfuzz View Post
    Hi! Actually, I think it might be beneficial to leave it open, as I'm not sure of what data needs to be stored.
    No, it is not beneficial to "leave it open". You are refusing to answer questions that are actually relevant to choosing what container you need.

    Quote Originally Posted by überfuzz View Post
    The integers are going to be there for sure, but I was told, just now, that there are other things that needs to be stored.
    That suggests your requirements are unclear and evolving. I suggest you get the requirements clear, BEFORE trying to decide what container you use. In fact, you need to decide what the elements are that you will place in the container. Or just stick with vector. It is the useful default choice.
    Last edited by grumpy; 03-30-2012 at 04:05 PM.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  12. #12
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Grumpy - I didn't mean to make anyone grumpy. Read my post above. :-)

  13. #13
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    I have. Stick with the default choice. vector.

    The C++ standard specifies complexity constraints on various algorithms (sorting, etc) and on specific operations (insertion, sorting, etc) supported by particular containers. The library implementers just have to meet those constraints. The way they do so is up to them.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  14. #14
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    You may be able to speed up the vector by reserving some reasonable amount of space initially:
    Code:
    vector<int> v;
    v.reserve(1000);
    That way you'll avoid a bunch of reallocations early on.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  15. #15
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Quote Originally Posted by grumpy View Post
    I have. Stick with the default choice. vector.

    The C++ standard specifies complexity constraints on various algorithms (sorting, etc) and on specific operations (insertion, sorting, etc) supported by particular containers. The library implementers just have to meet those constraints. The way they do so is up to them.
    Ok, I guess I don't need any links to any articles then. Thanks!

    oogabooga I've been tinkering with vectors and I always seem to end up slowing things down... Shame on those who give in!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 04-02-2009, 06:51 AM
  2. Array Speed
    By ch4 in forum C Programming
    Replies: 3
    Last Post: 12-17-2008, 12:27 PM
  3. Speed of pointers vs. speed of arrays/structs
    By Kempelen in forum C Programming
    Replies: 32
    Last Post: 06-27-2008, 10:16 AM
  4. what does a linked list structure look like?
    By MalickT in forum C Programming
    Replies: 9
    Last Post: 05-26-2008, 05:19 PM
  5. Speed comparison between vector and 2*2 array
    By cunnus88 in forum C++ Programming
    Replies: 5
    Last Post: 11-25-2007, 02:05 AM