Jump to content
  • Advertisement
Sign in to follow this  
Funkymunky

Should i use a linked list for this (C++)?

This topic is 2102 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been reading up about how linked lists are terrible for random access and cache locality, and how the inventor of the language Bjarne Stroustrup himself says you should always use vectors... but I think I have a special case.

 

I'm going to have a dynamically sized list of pointers.  The only reason for keeping track of the set is so that I can iterate over it when my program closes and free up any of the pointers that haven't already been released.  Other than that, I'll never iterate over the list.  I'm only going to be adding to the end of it (it's doubly linked).  I'm going to be deleting from anywhere within it at any time.  Anyone who uses data from the set is going to get a pointer to the new element in the list to use directly, so again no iteration for access or deletion.  Cache misses are still a concern, but since these are all pointers I don't think the vector really buys me anything.

 

Does anyone have an argument why a linked list in this instance isn't the best option?

Share this post


Link to post
Share on other sites
Advertisement

When the program closes, it doesn't really matter anymore, leave it up to the OS if you like (bad advice, although you shouldn't consider one off termination case to influence your run time case at all).

 

Lists are good if you frequently remove objects from the middle of the list and don't need random access.

 

Use a profiler.

Share this post


Link to post
Share on other sites


Does anyone have an argument why a linked list in this instance isn't the best option?

 

It sounds like you're going to end up fragmenting your memory space with list nodes everywhere.

 

Really, the idea doesn't make any sense to me. What problem exactly is this list meant to solve?

Share this post


Link to post
Share on other sites

Paradigm Shifter, that is blasphemy.  I'm going to delete all my allocated memory before I leave.  I'm never going to iterate in order to access an element, so the random access clause isn't an issue.

 

ApochPiQ, what about the fact that I'm going to add to the list at any time?  I don't see a performance hit with the list, but with the vector I'll hit the resize & copy routines regularly.

 

Pink Horror, I'm going to fragment the memory regardless of whether I use a vector or a list, since the elements are pointers to dynamically allocated memory.  This list is literally for managing a collection of pointers that I'll only need to iterate over when the program closes and I want to delete anything that's left over.

Share this post


Link to post
Share on other sites

Yes, I now it was blasphemy. However, you should consider the usual case (run time, every frame) before the exceptional case (program termination). It is better to save time in the usual case than plan ahead for the unusual case (program termination), so, don't let your runtime performance suffer because you plan ahead for the easy termination case. My tuppence.

Share this post


Link to post
Share on other sites

Paradigm Shifter, I agree completely with that.  I'll only iterate at termination, which is when I'm fine with taking that performance hit.

 

SiCrane, I don't think a deque would give me better performance over a linked list.  I'm going to be removing elements from the middle of the list regularly.

Share this post


Link to post
Share on other sites

I agree with ApochPiQ: If the order of your elements don't matter, use a vector and swap-and-pop.

 

ApochPiQ, what about the fact that I'm going to add to the list at any time?  I don't see a performance hit with the list, but with the vector I'll hit the resize & copy routines regularly.

 

First, if you're using C++11, you'd hit the resize and move your elements regularly (make sure your move-constructors are labeled noexcept, or you will in-fact copy). Second, your elements are pointers (so a move vs a copy isn't any different). Copying a range of pointers is as fast as copying a range of integers. It's a single memcpy() for the entire vector of pointers - very fast.

 

You can reserve() the amount of memory you're likely to need in advance, but even if you fail to reserve() you'll likely rarely need many actual reallocations.

 

Swapping and popping is very very fast also - no reallocation required. When you later push_back() a new element, you still won't need to reallocate, because your previous 'pop' (from the swap-and-pop) didn't reallocate, and so still has the not-yet-filled capacity.

 

I like having a SwapAndPop() templated function that I can pass a lambda to:

#include <iostream>
#include <algorithm> //For std::swap
#include <memory> //For std::unique_ptr
#include <vector>

//std::make_unique implementation (it was forgotten in the C++11 standard, and will be added later).
//Once it's added, I can just remove this from here.
template<typename T, typename ...Args>
std::unique_ptr<T> make_unique( Args&& ...args )
{
	return std::unique_ptr<T>( new T( std::forward<Args>(args)... ) );
}

//Swaps and pops every element in 'container', for which the callback function 'predicate(element)' returns true.
//This is faster than std::remove_if(), but does not preserve the order of the elements like 'remove_if()' does.
template<typename ContainerType, typename FunctionType>
void SwapAndPop(ContainerType &container, FunctionType predicate)
{
	for(typename ContainerType::iterator it = container.begin(); it != container.end();)
	{
		if(predicate(*it))
		{
			//Swap the value of the current element with the element at the back of the container.
			std::swap(*it, container.back());
			//Pop the back of the container.
			container.pop_back();

			if(container.empty())
			{
				break;
			}
		}
		else
		{
			++it;
		}
	}
}

class Object
{
	static unsigned nextID;
	
	public:
	Object() : timeToDelete(++nextID % 3), id(nextID) { }
	
	bool timeToDelete = false;
	size_t id = 0;
	
	public:
	typedef std::unique_ptr<Object> uPtr;
};

unsigned Object::nextID = 0;

int main()
{
	const size_t NumObjectsForTest = 40;
	
	std::vector<Object::uPtr> objects;
	
	//Create all the objects.
	for(size_t i = 0; i < NumObjectsForTest; ++i)
	{
		objects.push_back(make_unique<Object>());
	}
	
	//Print all the objects.
	for(const auto &object : objects)
	{
		std::cout << "Object " << object->id << ": " << (object->timeToDelete? "[Time to delete]":"[Still alive]") << std::endl;
	}
	
	std::cout << "------------------------------------\n"
	          << "Calling SwapAndPop...\n"
	          << "------------------------------------\n";
	
	SwapAndPop(objects, [](Object::uPtr &objectPtr) -> bool { return objectPtr->timeToDelete; });
	
	//Print all the objects again.
	for(const auto &object : objects)
	{
		std::cout << "Object " << object->id << ": " << (object->timeToDelete? "[Time to delete]":"[Still alive]") << std::endl;
	}
	
	return 0;
}

[run the code]

 

If you're likely to add/erase alot of objects of the exact same type (and if you find that this area of code is actually a bottleneck), you might even want to just 'swap', but leave the pointer and the memory hanging around so you can re-use it without the overhead of another call to 'new'.

Edited by Servant of the Lord

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!