• Advertisement
Sign in to follow this  

A list that does not disturb the order when pushed/popped?

This topic is 1337 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

Currently developing a game in C++.

My server (in C++) holds a list of players that are connected.

 

Players in this list can be either pushed or popped off the list.

Each player has a unique ID that they hold throughout the game.

 

The id is actually their place in the list.

 

For example some pseudo code:
 

List<Player> players = new List();

players.add(new Player("Todd", players.getThisListPosition()));
players.add(new Player("Ricky", players.getThisListPosition()));
players.add(new Player("Bob", players.getThisListPosition()));
players.add(new Player("Tim", players.getThisListPosition()));
players.add(new Player("Anna", players.getThisListPosition()));

For each player, their position in the list is their id. (assuming players.getThisListPosition() sets their ID as their position in the list).

 

Assume that the players were added when they contacted the server.

The list looks like so:

 

players

[0] = Todd

[1] = Ricky

[2] = Bob

[3] = Tim

[4] = Anna

 

Assuming the values of the list are the player instances in memory.

 

Now lets say Ricky leaves, players.pop( getID(playerThatLeft() ) );

The list looks like this now:
[0] = Todd

[1] = null

[2] = Bob

[3] = Tim

[4] = Anna

 

^This is ideal. This is what I want. However in reality the list would look like this:

 

[0] = Todd

[1] = Bob

[2] = Tim

[3] = Anna

 

^This is not what I want.

 

I want to retain the players positions in the list as they originally were. I don't want the list order to be modified.

Is there anything in C++ that I can use that will do this?

 

Share this post


Link to post
Share on other sites
Advertisement

That sounds like a job for an array-like data structure. So I think a vector is suitable for this. When you remove the item, you mark that item's slot as unused.

Share this post


Link to post
Share on other sites

Well I'm off to an okay start.

Made a custom list class that uses a vector.

 

So far when I add players, their ids are fine.

When I remove a player, the players still retain their ids, which is fine, however after removing a player

and then adding a new player, the player does not fill the position of the one that was previously removed.

 

Example:

 

push_back josh, tod, bob, tim, steph, giorgio.

 

[0] Josh

[1] Tod

[2] Bob

[3] Tim

[4] Steph

[5] Giorgio

 

remove bob

List now prints:
 

[0] Josh

[1] Tod

[3] Tim

[4] Steph

[5] Giorgio

 

push_back Greg

 

List now prints:

[0] Josh

[1] Tod

[3] Tim

[4] Steph

[5] Giorgio

[5] Greg

 

The reason why 5 is repeated is because the id that is assigned to the player is based on the size of the list.

However I need it so the ID is based on the position that it fills, but currently the vector isn't filling the list, its just pushing

it to the back. Not sure how to fill empty slots (in this case, position 2 was supposed to be assigned to greg).

 

playerList.h

#include <vector>
#include "player.h"
#include <iostream>
#pragma once

class PlayerList{
	std::vector<Player> playList; //the list
public:
	void addPlayer(Player* p); //adds Player p
	void removePlayer(unsigned int id); //removes player given id
	Player getPlayer(unsigned int id); //gets player given id
	void printList();
};

playerList.cpp

#include "playerList.h"

void PlayerList::printList(){
	for(std::vector<Player>::iterator it = playList.begin(); it != playList.end(); ++it) {
		std::cout << "[" << it->id << "]     " << it->name << std::endl;
	}
}

void PlayerList::addPlayer(Player* p){
	//std::cout << "ADDING PLAYER, LIST SIZE: " << playList.size() << std::endl;
	unsigned int theId = playList.size();
	p->id = theId;
	playList.push_back(*p);
	std::cout << "ADDING PLAYER, theId: " << theId << std::endl;
}

void PlayerList::removePlayer(unsigned int id){
	for(std::vector<Player>::iterator it = playList.begin(); it != playList.end(); ++it) {
		if(it->id == id){
			playList.erase(it);
		}
	}
}

One thing I could do, is when adding a player, check the list for any blank spots that aren't filled, but how do I do this?

When I remove a player, how would I mark its position in the list as "blank" rather than just erase it completely?

Edited by BurdenJohn

Share this post


Link to post
Share on other sites

You should use ApochPiQ's suggestion of a vector of pointers. Removal of one in the middle becomes invalidating the pointer (whether unique_ptr's reset or a raw null). Adding a new one then requires traversing the array to see if any slots can be reassigned without push_back (which might reallocate and copy, but still better than copying an entire array of large objects).

 

std::vector::erase literally removes the element, copying everything else down a slot. To use a vector of objects like the pointer version, you'd need a way to mark a Player object as invalid so you can search for an available id in the middle of the list before using push_back to add to the end.

Share this post


Link to post
Share on other sites

Hmm not sure what's going on here, but now I'm trying to use std::unique_ptr but I'm getting a private member access error?

#include "playerList.h"

void PlayerList::printList(){
	std::cout << "PRINTING PLAYER LIST" << std::endl;
	for(std::vector<std::unique_ptr<Player>>::iterator it = playList.begin(); it != playList.end(); ++it) {
		Player* p = it->get();
		std::cout << '[' << p->id << ']' << p->name <<  std::endl;
	}
}

void PlayerList::addPlayer(Player* p){
	std::cout << "ATTEMPTING TO ADD PLAYER: " << p->name << std::endl;
	std::unique_ptr<Player> uptr(p);

	unsigned int count = 0;
	unsigned int nullCount = 0;

	//Check for a null player, if we find one, replace it with the new one
	for(std::vector<std::unique_ptr<Player>>::iterator it = playList.begin(); it != playList.end(); ++it) {
		count++;
		Player* ps = it->get();
		if(it->get() == nullptr){
			nullCount++;
			unsigned int pos = it - playList.begin();
			it->swap(uptr);
			it->get()->id = pos;
			return;
		}
	}
	//If we didn't find a null player 
	unsigned int pos = playList.size();
	uptr->id = pos;
	playList.push_back(uptr);
}

void PlayerList::removePlayer(unsigned int id){
	
	for(std::vector<std::unique_ptr<Player>>::iterator it = playList.begin(); it != playList.end(); ++it) {
		Player* p = it->get();
		if(p->id == id){
			std::cout << "REMOVING PLAYER: " << p->name << std::endl;
			it->reset();
		}
	}
	
}

 

C2248: 'std::unique_ptr<_Ty>::unique_ptr' : cannot access private member declared in class 'std::unique_ptr<_Ty>'

 

The idea now is that when I add a player, I check for any null players that are in the list.

 

If I find one, I make swap the null player with the new player I'm adding, and the new player gets the id that's equal to the current position of the iteration

( it - playList.begin() )

 

 

A null player is now a player that, when it gets removed, its unique_ptr is reset().
 
Not sure if this works though, can't figure out why I'm getting that error. I've read that it has to do with making a copy? I don't recall ever making a copy of the unique_ptr?
Edited by BurdenJohn

Share this post


Link to post
Share on other sites
push_back() is probably the culprit, although if you want to know for sure, look at the line that is reporting the error.

Try emplace_back() instead; it will move the pointer instead of copying it.

Share this post


Link to post
Share on other sites

The thing is the error comes from File: "xmemory0" at line 617:

#define _ALLOC_MEMBER_CONSTRUCT( \
	TEMPLATE_LIST, PADDING_LIST, LIST, COMMA, CALL_OPT, X2, X3, X4) \
	template<class _Objty COMMA LIST(_CLASS_TYPE)> \
		void construct(_Objty *_Ptr COMMA LIST(_TYPE_REFREF_ARG)) \
		{	/* construct _Objty(_Types...) at _Ptr */ \
		::new ((void *)_Ptr) _Objty(LIST(_FORWARD_ARG)); \
		}

_VARIADIC_EXPAND_0X(_ALLOC_MEMBER_CONSTRUCT, , , , )
#undef _ALLOC_MEMBER_CONSTRUCT

Also, commenting out push_back() seemed to get the error away, but of course I still need that in (caused an exception).

So I tried your emplace_back() suggestion, and I get the same error as before (cannot access private member...) line 617 of file xmemory0 as posted above.

Here's my playerList.cpp code as it stands:

http://pastie.org/private/0lhdxjoczzjfdg2acyzq

 

Does it seem like my list would work though using these methods?

Edited by BurdenJohn

Share this post


Link to post
Share on other sites

Release the pointer at specific position when the player leaves and assign nullptr to it?

Edited by GuardianX

Share this post


Link to post
Share on other sites
Post the entire compile error, from the Output pane in Visual Studio, with the Debug filter selected from the dropdown. Your compiler is telling you exactly where the problem is, all the way from the "real" error up through the templates of the standard library implementation and into your own code; it can be hard to read, but learning to interpret these error chains is immensely valuable.

The last chunk of the error output should point you exactly to what part of your code is causing the issue.


[edit] Afterthought: you should emplace_back the raw pointer, not the unique_ptr. In fact you shouldn't need to create a unique_ptr inside the function at all. Edited by ApochPiQ

Share this post


Link to post
Share on other sites
List<Player> players = new List();

 

ah! Java/C# programmer in the room tongue.png That's no C++. 

 

Anyway.. to answer your question, you are trying to have a player ID being equal to his position in the list. This is basically, impossible, or possible but VERY error prone.

 

There are many ways to go around the problem, the one I use for my server stuff is to have the player ID as part of the Player data structure. My player list is a std::vector and then I have an helper function Player* getPlayerFromID(unsigned char id); that looks for a player with that ID in my list and returns it. A map might work better if you discover that your getPlayerFromID is a bottleneck.. personally it isn't so don't bother.

 

The other convoluted way would be to reassign IDs every time a player is added or removed to the list. The adding part is easy because it only involves the currently added player.. the removing is tricky because you'll have to notify all your clients "hey your player ID has changed".. which I think it's just a bad idea.

Share this post


Link to post
Share on other sites
Assuming you won't have more than 256 player online, you can use a plain old array, like Player *players[256].
Memset to zero and you'll have all players=NULL.
When a player connect, scan the array and look for the first NULL; when a player leave, delete players[id], and set players[id]=null

Share this post


Link to post
Share on other sites

Assuming you won't have more than 256 player online, you can use a plain old array, like Player *players[256].
Memset to zero and you'll have all players=NULL.
When a player connect, scan the array and look for the first NULL; when a player leave, delete players[id], and set players[id]=null

Honestly this was the simplest solution!

Just a quick question though, here's my removePlayer function:
 

int PlayerList::removePlayer(unsigned int id){
	//std::cout << "===REMOVING PLAYER===" << std::endl;
	if(players[id] != NULL){
		delete players[id];
		players[id] = NULL;
	}
	return 0;
}

It works when I remove the line "delete players[id];"

For some reason when I leave that in, I get an exception when I try to execute removePlayer(2) for example.

It says the heap gets corrupted.

 

Why is that? And also, why do I need to delete that piece of memory, because when I set it to NULL, the reference is gone anyways?

Or would the player instance still be in memory? If that's the case, how do I get around this issue where it corrupts the heap?

Share this post


Link to post
Share on other sites

You need to post more of your code if you want us to tell you why it's crashing. smile.png

 

Are you calling 'delete' on something you haven't called 'new' on?

Why are you using 'new' or 'delete' at all here? Even smart pointers here is probably unnecessary.

Your code probably shouldn't contain any occurrences of new or delete.

 

In C++, the 'new' keyword and the 'delete' keyword do things very differently from other languages you might have used, and need to be handled with care.

 

Why do you need to delete the memory of your players, anyway? Why not just mark them (with a bool) as not in use?

Why are your Player structs dynamically allocated instead of on the stack?

 

If you use C++11, which you are if you have access to std::unique_ptr, then you should use nullptr, not NULL. There is a reason for that.

 

I mentioned earlier, why does the order in memory of your players matter?

Why are you using a single variable (the ID) to handle more than one purpose (position in memory and identification)?

 

You definitely don't need a custom container. tongue.png

 

Here's my suggested solution: std::unordered_map<PlayerID, Player>

 

If you want to *remove* a player from memory (why?), call myMap.erase(playerID).

 

But if you want to preserve the prior existence of a player, just use a boolean to mark him as no longer active. wink.png

myMap.at(playerID).isActive = false;

For new IDs, just hold the last used ID and increment it. Don't let the current size of your containers dictate your IDs if you're going to be removing elements.

PlayerID newPlayerID = ++lastUsedPlayerID;
Edited by Servant of the Lord

Share this post


Link to post
Share on other sites
I don't understand this new trend against new and delete. In a simple scenario like this, there's no reason not to use new and delete, it's ABC of programming with c++. If you can't handle a simple array of pointers, you have no hope with c++. It's a good exercise for the OP and understanding why he gets an error when deleting a player will save him a lot of troubles in the future.

@burden: your remove fn is correct, the error probably is in your create function Edited by Giallanon

Share this post


Link to post
Share on other sites


I don't understand this new trend against new and delete. In a simple scenario like this, there's no reason not to use new and delete, it's ABC of programming with c++. If you can't handle a simple array of pointers, you have no hope with c++. It's a good exercise for the OP and understanding why he gets an error when deleting a player will save him a lot of troubles in the future.

It's the other way round, there's no reason to use new and delete here.

Share this post


Link to post
Share on other sites

Thank you all for the suggestions.

I'm going to go with Giallanon's suggestion, was very simple and it works!

 

Thanks guys.

Share this post


Link to post
Share on other sites
I'm surprised that no one has mentioned pools in this thread -- they're very common in games and used for this purpose. It's basically an array combined with a free-list.

Normally a pool would be a container like a std::vector that stores data, but here's the basic version of the idea, which only manages handing out ID's, and not actually containing objects.
n.b. all code in this thread is written off the top of my head - may not compile or work...
struct IdPool : NonCopyable
{
public:
  IdPool( int capacity )
    : nodes((Node*)malloc(sizeof(Node)*capacity)
    , free(0)//point to the first node
  {
    assert( capacity );
    //link each node to the next
    for( int i=0, end=capacity-1; i!=end; ++i )
      nodes[i].next = i+1;
    nodes[capacity-1].next = -1;//terminate the list (-1 == null pointer)
  }
  ~IdPool()
  {
    free(nodes)
  }
  int Alloc() // returns -1 if full, otherwise gives out an ID
  {//try and pop one from the front of the free-list
    int id = free;
    if( free != -1 )
      free = nodes[free].next;
    return id;
  }
  void Free(int id)
  {//push this node to the front of the free-list
    nodes[id].next = free;
    free = id;
  }
private:
  struct Node { int next; }//holds the index of the next free node
  Node* nodes;
  int free;//ID of the first unused node
};
A very simple way to expand this into a full container is to pair it up with a std::vector. However, this version constructs/destructs all of the objects when the pool is created/destroyed -- ideally it would use placement new / manual destructors to construct/destruct objects inside the Alloc/Free functions (My version here does this).
template<class T> struct Pool
{
  Pool( int capacity )
    : m_pool(capacity)
    , m_data(capacity)
  {
    m_data.resize(capacity);
  }
  T* Alloc()
  {
    int id = m_pool.Alloc();
    if( id == -1 )
      return 0;
    return &m_data[id];
  }
  void Free(T* obj)
  {
    int id = obj - &m_data[0];
    assert( id>=0 && id<m_data.size() );
    m_pool.Free(id);
  }
private:
  IdPool m_pool;
  std::vector<T> m_data;
}
Also, a good implementation of the Pool idea will actually put the data into the node objects, so when they're in the free-list they're int's, otherwise they're T's e.g.
...
    : nodes((Node*)malloc( max(sizeof(Node),sizeof(T)) * capacity )
...
  struct Node
  {
    int next;
    void Alloc() { new(this) T(); }
    void Free () { ((T*)this)->~T(); }
  }
  Node& At(int index)//use At(index) instead of nodes[index] now
  {
    const int nodeSize = max(sizeof(Node),sizeof(T));
    return *(Node*)(((char*)nodes) + index * nodeSize);
  }
public:
  T* Alloc()
  {
    if( free == -1 )
      return NULL;
    Node& node = At(free);
    free = node.next;
    node.Alloc();//construct the object
    return &node;
  }
  void Free(T* obj)
  {
    int id = obj - (T*)&nodes;
    Node& node = At(id);
    node.Free();//destruct the object
    node.next = free;
    free = id;
  }
...
Edited by Hodgman

Share this post


Link to post
Share on other sites

I don't understand this new trend against new and delete.
[...]
it's ABC of programming with c++. If you can't handle a simple array of pointers, you have no hope with c++.

The 'trend' against new and delete is advocated by very experienced programmers, not just myself. Many of the people advocating against over-use of new and delete, are the people on the C++ standards committee. Granted, saying "person X is accredited must mean he's correct" is silly, but my point is, these people literally wrote the book(s) on new and delete. It's not that they, or myself, "can't handle a simple array of pointers" or "have no hope with c++", they created (and continue to develop) C++ and the C++ best-practices and advocate against unnecessary use of new and delete. mellow.png

 

[Here's one example - there are many other examples by many other C++ experts]

For example, a std::vector already dynamically allocates its memory. So you are stack-allocating a pointer to dynamically allocated memory to store an array of pointers to more dynamically allocated chunks of memory. Bwah? Why not just make that stack-allocated pointer point to the dynamically allocated memory directly? Unless, for performance reasons, you decide that you like distributing every allocated element into a different location in memory to prevent the CPU from effectively fetching them in bulk, and you actually like having to deallocate two pointers instead of one for every element read or write access. 

 

...why not do it in the safer, faster, simpler, cleaner way? wink.png

 

Another example is, if new (or a new equivalent) is getting called once already in the vector, why call it once more for every element? It's the difference between 1 new call verses 1 new call and an additional new call for every element (i.e. for 50 elements, that means it's 1 call to new verses 51 calls to new), when the additional new calls add no benefit (in this situation).

 

I'm not advocating pre-optimization either - but I'm saying doing things the "right" way often leads, as a side-effect, to faster code anyway - or rather, to less bloated code.

If a container is holding pointers, then new and delete is something added on top of the container. I'm saying, wait a minute, why are we adding new and delete into a situation that doesn't benefit, and actually suffers, from the addition of it?

 

There are scenarios where new and delete are the best choice. I'm fairly confident that this is not one of them.

New and delete shouldn't be the default go-to choice - it's the last choice of a list of better possibilities. smile.png

Edited by Servant of the Lord

Share this post


Link to post
Share on other sites

@servant: I voted up your answer, because I like the way you put it down, and also because I agree with everything you wrote.

 

But...

IMO, before using STL, or smart pointers or any "advanced" c++ things, a beginner should understand perfectly what is a (raw) pointer, how it's used, why they exists, what is a memory leak and why/how they are related to the use of pointers.

I think everyone should go trough the process of using pointers and discover that somewhere, sometimes, your program is leaking memory. You should fire up your debugger and go figure.

I think this is the only way to learn. When you understand the power of pointers, then you can choose a (may better) approach, like not using new at all for example.

So my complains against "this new trend" is more about the fear that the the new generation of programmers will grow up without understanding the raw power of c/c++. Why using c++ in first place if you don't have the time/will to learn the hard stuff. There are plenty of other languages that will deal with pointers in a transparent way (c# is a good example).

 

Anyway, in this specific case, I would have used a placement new, over a pre-allocated memory block of 256 * sizeof(Player), maybe with a little care about memory alignment.

The array of 256 pointer to player is still the best option IMO for a few reason:

1) given the player ID, you have O(1) access to the player data

2) search within the array for null pointers is very cache friendly since a single pointer is only 4 or 8 bytew, so the whole array is 1 or 2 KB of memory

3) from a psychologically point of view, calling new when a new player enter the game, and calling delete when he leave, is something that feels right to me

 

When a player come, you have to initialize a player class. If you use new Player(),  the constructor will take care of initialization; if you use an already existing instance of player, then you have to call some method like player[id].initialize() or player[id].whatever() just to setup the class.

I fell like new Player() is better.

The same goes for a player that log off, calling delete player[id] feels better to me than calling player[id].kill()

It's the same thing, just called with different names.

 

I agree that a std::vector of pointers is a non sense, that's why my solution involve a plain old array of pointers.

Share this post


Link to post
Share on other sites

Let's reserve the philosophical debate over learning style (which is endless and therefore pointless) for other threads, and keep this on the subject of the poster's problem, please.

Share this post


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

  • Advertisement