• 15
• 15
• 11
• 9
• 10

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

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

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("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 on other sites

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 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 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;
}
}

//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 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 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;
}
}

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 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 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)); \
}

#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