Quick question about difference between vectors and lists

[theoneandonlyboiler]

Hi there

Just a quick question. I have been messing around with vectors and lists over the past few days and stumbled upon something that I don't quite understand.

First a small program using vectors:

#include <iostream>
#include <vector>

static int ID_Counter = 0;

// Just some simple Class to test Stuff
class C_SomeClass
{
private:

	int Variable1 = 10;
	int Variable2 = 20;
	int Variable3 = 0;

	int ID = 0;

public:

	C_SomeClass()
	{
		ID_Counter++;

		ID = ID_Counter;
	}

	void Calculate()
	{
		Variable3 = Variable1 + Variable2;
	}

	void Display()
	{
		std::cout << Variable3 << " " << ID << std::endl;
	}
};

int main()
{
	// Set up Vector
	std::vector<C_SomeClass> vTestVector;		// vector to store instances of C_SomeClass
	std::vector<C_SomeClass>::iterator Iterator;	// iterator

	// Create 3 Class Instances and store in Vector
	for (int Counter = 0; Counter < 3; Counter++)
	{
		C_SomeClass Instance;
		vTestVector.push_back(Instance);
	}
	
	// Run through Instances, calculate and display Results
	for (Iterator = vTestVector.begin(); Iterator < vTestVector.end(); Iterator++)
	{
		std::cout << Iterator - vTestVector.begin() << " ";
		(*Iterator).Calculate();
		(*Iterator).Display();
	}

	std::cout << std::endl;

	return 0;
}

Now, the following code snipped from the above program works fine for vectors:

	for (Iterator = vTestVector.begin(); Iterator < vTestVector.end(); Iterator++)
	{
		std::cout << Iterator - vTestVector.begin() << " ";
		(*Iterator).Calculate();
		(*Iterator).Display();
	}

But if I adopt the same program for lists, it doesn't work (the rest of the program does though):

	for (Iterator = lTestList.begin(); Iterator < lTestList.end(); Iterator++)
	{
		std::cout << Iterator - lTestList.begin() << " ";
		(*Iterator).Calculate();
		(*Iterator).Display();
	}

The compiler first complains about the "<" operator and if I change that to "!=" (which for some reason works) it then complains about the "-" operator. The compiler also does not recognize the "<<" operator for some reason.

The error is always "no operator " " matches these operands".

It's not a big deal right now as the only thing the offending line does is display the position of the value within the vector/list. But I would still like to understand why it works for vectors but not for lists.

Also, what would be the correct solution to display the position of a value within a list?

Thanks in advance.

[Repeater]

A list iterator is simply a different kind of iterator to a vector iterator. The operators you're trying to use are not supported by a list iterator.

You can yourself write functions that did what you wanted, but they're brutally inefficient compared to the same operations with a vector; which is why they're not provided. You're not meant to use a list that way because it's so brutally inefficient. In a vector, these operations are cheap abd easy because the vector guarantees that all the elements are contiguous in memory. In a list, every element could be anywhere and thr only way to find them is to follow each link in the list; very expensive compared to vector.

"Also, what would be the correct solution to display the position of a value within a list?"

Keep track of how many links you've followed as you cycle over the list.

[theoneandonlyboiler]

Ah, thanks. That makes sense.

I wanted to use the position to access the different objects within the list. I'll see what other solution I can come up with.

[Repeater]

Exactly so; a linked list doesn't have a simple way to get the n'th element. You have to start at the beginning and follow every link until you get there. Expensive. A vector *does* have a cheap, fast way to get the n"th element.

The solution is almost certainly to use a vector. For the majority of real-world uses, they are faster and easier. Even for things like inserting into the middle. Use a vector.

[theoneandonlyboiler]

Hm, I'm trying to create a player inventory system which can potentially have a lot of different items in it and is subject to frequent changes. Since vectors use a continuous memory block, I'm really not sure if a vector would be the right choice here performance wise.

For now I found a cheap workaround for my problem by running an integer variable as a counter alongside the list iterator when cycling through the list to display the different elements. User input is then used similarly to cycle to the right element in the list and interact with it.

Probably a bit dirty, but it does what I wanted ;-)

[Repeater]

Performance wise, vector is probably what you want.

Jumping around memory is really, really expensive. Why do you think a linked list is faster? Vector generally does much better, performance wise.

[jlb]

For now I found a cheap workaround for my problem

How did you deduce that your "cheap workaround" is actually cheap, and is actually better than using a std::vector?

Did you profile the program? If not then you really should consider using a std::vector.

Also with today's operating systems memory is very cheap, your computer probably has more than enough memory to efficiently store several thousand items without problems.

By the way if the "interaction" you mention could involve removal both your "counter" and the iterators could become invalid.

[George P]

https://stackoverflow.com/questions/238008/relative-performance-of-stdvector-vs-stdlist-vs-stdslist

[jonnin]

you are not telling us enough to give you a good starting point, but there are a lot of container types for a reason (each has pros and cons) and you can also mix and match them (a vector of lists, for example, can be very efficient as the lists are kept small so you 'get close' with a vector index 'search' or direct jump and then search just a few items linearly which is not so bad) and so on. You can make a vector into a linked list with a thin wrapper, using the indices as 'pointers'. It still page faults if you jump around in a giant amount of data, but you can minimize this if you know your data well. That is just 2 quick examples of going outside the box just a little to craft something useful from what you have.

If what you did is good enough, that can also be a good place to leave it. Just be sure it really does perform well with the workload you expect -- don't test with 100 items if you plan to store 2 million.

[theoneandonlyboiler]

@ Repeater

Well, in the book I‘m using to learn C++ the Author writes that vectors should only be used for short lists. He claims linked lists are much more efficient performance wise when dealing with large lists. He reasons this is so because linked lists do not need to move stuff around all the time.

If that ist not true, then I‘m of course happy to use vectors instead. I‘m not biased toward either option. I was just following the lessons of my book :-)

[seeplus]

It depends upon what operations are being performed as to which container type is 'best' in the given circumstances.

[Repeater]

Here are some practical benchmarks: https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

If you have hundreds of thousands of big items and you're doing the particular expensive things with them, list might be better. I suspect, based on what you said above, that this is not your situation.

[George P]

theoneandonlyboiler wrote:

the book I‘m using to learn C++

What is the book?

A lot of C++ books are garbage IMO, and outdated.

Learning from just one book teaches you what could be a slanted view of what C++ has to offer. What one particular author deems necessary. You should use/read multiple books.

My "Learn C++" book library has 8 physical books and 4 eBooks. I had more, the 12 are ones I found useful enough to keep as references.

The physical books are years, years and years old, and cover C++11/a bit of C++14. The eBooks cover particular features of C++11/14/17. The eBooks are really reference books. You need to have a decent grasp of C++ basics to understand the material.

One book I highly recommend is by the creator of C++: Bjarne Stroustrup.

Programming: Principles and Practice Using C++ (2nd Edition) - https://www.amazon.com/Programming-Principles-Practice-Using-2nd-dp-0321992784/dp/0321992784/

Looking at online tutorials in addition to books can be useful. There is an outdated one there at CPlusPlus. Another that is updated often is Learn C++: https://www.learncpp.com/

[jonnin]

A lot of C++ books are garbage IMO, and outdated.
To be fair, things that were good info at the time and now outdated are not really 'garbage'. The author may be a great coder, but old info problems. This is very different from a garbage author to begin with.

The best advice I can give you there is specifically for c++ do not buy or study a lot of books that were printed before 2018. The language had a major update in 2017 and anything older is too old now.

[theoneandonlyboiler]

At the moment, I have two books (still working through the first one though), and I plan on getting a third one after working through the first two. After that, I don't know yet. I am also reading a lot of stuff online to complement what the books are teaching or sometimes to reach ahead if I encounter problems that I can not yet solve with my current knowledge. For example I already make heavy use of strings even though the book did not mention them yet. This became necessary when I wanted to to some things that just don't work with char-arrays.

I am also aware that there is a lot of bias when it comes to C++ and that I should not trust just one source. I already came across some oddities in my current book where the Author claims one thing while many on the internet have a different opinion (this here would be another example of that). So no worries, I am aware of the pitfalls and am taking the necessary precautions ;-)

These are the books I mentioned (in German, because I'm from Switzerland):

The one I'm currently working on (I know it's outdated):
https://www.amazon.de/-/en/Heiko-Kalista/dp/3446446443/ref=sr_1_1?crid=1OBDFMR9K1F49&dchild=1&keywords=c%2B%2B+f%C3%BCr+spieleprogrammierer&qid=1606110688&sprefix=c%2B%2B+f%2Caps%2C164&sr=8-1

The second one I have:
https://www.amazon.de/-/en/Michael-Bonacina/dp/1720089973/ref=sr_1_2?crid=GDKCUPZSCMJH&dchild=1&keywords=c%2B%2B+programmieren+f%C3%BCr+einsteiger&qid=1606111476&sprefix=c%2B%2B+programmieren+f%C3%BCr+ein%2Caps%2C164&sr=8-2

The third one I'm planning on buying:
https://www.amazon.de/-/en/gp/product/3446463860/ref=ox_sc_saved_title_3?smid=A3JWKAKR8XB7XF&psc=1

[TheIdeasMan]

IIRC there were 3 things that Stroustrup mentioned that affect the efficiency of operations on containers: move semantics; concurrency ; and cache effects.

The bench mark report linked above mentioned cache, but not the other two. However the bench marks results are still solid evidence.

[theoneandonlyboiler]

Well, based on the benchmarks I'm really torn. While searching a list is very expensive compared to a vector, inserting and deleting objects is more efficient with lists for large data types (which is what I'm using).

It seems however that searching and adding new elements to the back are the two operations that are the most time consuming. So probably I really should be using vectors as the gain is greater than the loss.

[TheIdeasMan]

While searching a list is very expensive compared to a vector, inserting and deleting objects is more efficient with lists for large data types (which is what I'm using).

Just wondering what you mean by "large data types" ?

You would probably get better help if you told us what your actual problem is.

Btw, if you are going to iterate a whole container that contains a suitable sequence, you can use a range based for loop:
https://en.cppreference.com/w/cpp/language/range-for

for (auto& item : container) {
  // do something with item
}

I find that easier than dealing with iterators.

with perfect forwarding, correctly handles lvalues, rvalues, const and non const:

for (auto&& item : container) {
  // do something with item
}

Good Luck !!

[theoneandonlyboiler]

The data I'm inserting into the list/vector are various class objects that contain a number of variables and functions. The size of the ones I'm currently working on is 108 bytes per class object, which would be in the range where, according to the linked benchmark, lists are more efficient when inserting and deleting objects.

I have switched to vectors now as searching the list, accessing objects within and adding new ones to the end is what the program will mostly do. So as I said above, I'm confident the performance gained here will probably more than outweigh the performance hit from inserting (which will probably never even be needed) and deleting objects.

Thanks for all your replies! This really helped and my understanding of vectors and lists has improved quite a bit.

[seeplus]

Have you looked at deque? http://www.cplusplus.com/reference/deque/deque/