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..?

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.

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.

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..?

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.

Quote:

---

Originally Posted by laserlight

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!

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)?

Quote:

---

Originally Posted by oogabooga

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++?

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?

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

Will you need random access to the data?

---

No.

Quote:

---

Originally Posted by iMalc

Does the order of items matter?

---

No.

Quote:

---

Originally Posted by iMalc

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

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 --> :D

Quote:

---

Originally Posted by überfuzz

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

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

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

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.

Grumpy - I didn't mean to make anyone grumpy. Read my post above. :-)

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.

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.

Quote:

---

Originally Posted by grumpy

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!

Quote:

---

Originally Posted by überfuzz

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

---

Can you give a demonstration..?
What made you think that 'things' were slow ?
Did you compare the performance with a list or (de)queue ?

Quote:

---

Originally Posted by überfuzz

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!

---

Note that I did not recommend vector because I consider it in any way optimal for your needs. I recommended vector because your (lack of) requirements means that any choice of container is sufficient. Vector is a workable default choice, nothing more.

If you care about performance, you need to articulate stronger requirements. If you actually do that, you will actually need to read some articles about the design trade-offs related to selecting containers.

It is possible to slow down things regardless of your choice of container: just pick a series of operations that plays to the weakness of each container. There is no universally optimal container (i.e. each container type supports some operations efficiently by some measure, and other operations inefficiently). It is also possible to hit program performance by unnecessarily creating (non-lazy) copies of entire containers.

Quote:

---

Originally Posted by überfuzz

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++.

---

Ah, but Java has a bunch of standard library components too, including useful containers similiar to those available in the C++ standard library :)

If I were programming in Java, I would consider the container to use based on similiar considerations of how the elements are to be inserted and how they are to be accessed. For example, if I want to map from keys to values such that the keys are sorted, I might go for TreeMap in Java and std::map in C++. If I just want to map from keys to values with the aim of accessing the keys as fast as possible, I might go for HashMap in Java and std::unordered_map in C++, with a suitable hash function.

I would not ask if HashMap might not be good enough such that I should implement my own hash table, unless after testing I really do discover that the general purpose HashMap is not good enough, yet a hash table is appropriate. This is why your question stunned me: it is like a Java programmer asking if he/she should implement a red/black tree instead of using TreeMap because TreeMap might not be good, even before having any evidence that a custom balanced binary tree implementation might beat TreeMap to satisfy performance requirements in this case... when it may well be that choosing HashMap instead is the way to go, or perhaps the performance requirements will already be met by TreeMap.

Quote:

---

Originally Posted by oogabooga

You may be able to speed up the vector by reserving some reasonable amount of space initially:

---

Yeah, then push_back will go from amortised constant time to constant time, at least until the size of the vector exceeds the reserved capacity.

So far my asessment is still that std::vector is best, however I appear to have forgotten to ask more about how the data will be accessed.
Once you put something in there, do you intend to search for it at some point, or are you only ever just going to process the whole lot at once?
Also, will there ever be any duplicates?

oogabooga - Test runs showed: 220 seconds when I stored data or more precisely hits in the form of an integer with push_back in a vector. 177 seconds when I just counted hits. I'll couldn't see any significant different in performance while preallocating a bigger vector. (I don't remember how big i tried, but I'll try a real big and report back.)

Quote:

---

Originally Posted by überfuzz

I'll couldn't see any significant different in performance while preallocating a bigger vector.

---

Yeah, that coincides with Stroustrup's observation in his answer to the FAQ Why are the standard containers so slow?:

Quote:

---

Originally Posted by Bjarne Stroustrup

People sometimes worry about the cost of std::vector growing incrementally. I used to worry about that and used reserve() to optimize the growth. After measuring my code and repeatedly having trouble finding the performance benefits of reserve() in real programs, I stopped using it except where it is needed to avoid iterator invalidation (a rare case in my code).

---

You might also want to read the rest of that FAQ, though much of it does not apply in your case because you are storing objects of a built-in integer type.

By the way, what compiler are you using?

Quote:

---

Originally Posted by laserlight

You might also want to read the rest of that FAQ, ...

---

Yes, it's a nice article. Thanks!