Jump to content

  • Log In with Google      Sign In   
  • Create Account

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


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
21 replies to this topic

#1 BurdenJohn   Members   -  Reputation: 132

Like
2Likes
Like

Posted 23 May 2014 - 09:55 PM

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?

 



Sponsor:

#2 ultramailman   Prime Members   -  Reputation: 1572

Like
2Likes
Like

Posted 23 May 2014 - 10:11 PM

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.



#3 Servant of the Lord   Crossbones+   -  Reputation: 19665

Like
5Likes
Like

Posted 23 May 2014 - 10:20 PM

Why is their position in the list important? You seem to be using their 'id' for two separate uses:

1) As a unique identifier, and 2) to look the player up. Would these be better off separated?

 

Have you considered an unordered map? std::unordered_map<PlayerID, Player>

If their relative position is important, perhaps an ordered map would be better suited. std::map<PlayerID, Player>


Edited by Servant of the Lord, 23 May 2014 - 10:25 PM.

It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]


#4 ApochPiQ   Moderators   -  Reputation: 15824

Like
5Likes
Like

Posted 23 May 2014 - 10:24 PM

The simple solution is to have a std::vector<std::unique_ptr<Player*>> and simply reset() the unique_ptr when a player leaves.

#5 BurdenJohn   Members   -  Reputation: 132

Like
0Likes
Like

Posted 23 May 2014 - 11:21 PM

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, 23 May 2014 - 11:26 PM.


#6 beans222   Members   -  Reputation: 1109

Like
0Likes
Like

Posted 23 May 2014 - 11:37 PM

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.


New C/C++ Build Tool 'Stir' (doesn't just generate Makefiles, it does the build): https://github.com/space222/stir

 


#7 BurdenJohn   Members   -  Reputation: 132

Like
0Likes
Like

Posted 24 May 2014 - 12:16 AM

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, 24 May 2014 - 12:24 AM.


#8 ApochPiQ   Moderators   -  Reputation: 15824

Like
0Likes
Like

Posted 24 May 2014 - 12:37 AM

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.

#9 BurdenJohn   Members   -  Reputation: 132

Like
0Likes
Like

Posted 24 May 2014 - 01:14 AM

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, 24 May 2014 - 01:16 AM.


#10 GuardianX   Crossbones+   -  Reputation: 1506

Like
0Likes
Like

Posted 24 May 2014 - 03:04 AM

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


Edited by GuardianX, 24 May 2014 - 03:04 AM.


#11 ApochPiQ   Moderators   -  Reputation: 15824

Like
2Likes
Like

Posted 24 May 2014 - 03:32 AM

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, 24 May 2014 - 03:35 AM.


#12 kunos   Crossbones+   -  Reputation: 2207

Like
0Likes
Like

Posted 24 May 2014 - 04:03 AM

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.


Stefano Casillo
Lead Programmer
TWITTER: @KunosStefano
AssettoCorsa - netKar PRO - Kunos Simulazioni

#13 Giallanon   Members   -  Reputation: 1223

Like
3Likes
Like

Posted 24 May 2014 - 07:39 AM

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

#14 BurdenJohn   Members   -  Reputation: 132

Like
0Likes
Like

Posted 24 May 2014 - 12:18 PM

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?



#15 Servant of the Lord   Crossbones+   -  Reputation: 19665

Like
0Likes
Like

Posted 24 May 2014 - 01:19 PM

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, 24 May 2014 - 01:21 PM.

It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]


#16 Giallanon   Members   -  Reputation: 1223

Like
2Likes
Like

Posted 24 May 2014 - 03:42 PM

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, 24 May 2014 - 04:03 PM.


#17 Mussi   Crossbones+   -  Reputation: 2027

Like
4Likes
Like

Posted 24 May 2014 - 04:27 PM


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.



#18 BurdenJohn   Members   -  Reputation: 132

Like
0Likes
Like

Posted 24 May 2014 - 05:48 PM

Thank you all for the suggestions.

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

 

Thanks guys.



#19 Hodgman   Moderators   -  Reputation: 30424

Like
3Likes
Like

Posted 24 May 2014 - 06:12 PM

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, 24 May 2014 - 06:23 PM.


#20 Servant of the Lord   Crossbones+   -  Reputation: 19665

Like
4Likes
Like

Posted 26 May 2014 - 08:35 PM

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, 26 May 2014 - 11:15 PM.

It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS