Une limite d'allocation contiguë peut-elle être forcée dans un modèle C++?

Question

Exemple simple:

template <class P> class MyT 
{ 
    struct Item 
    { 
    public: 
     Item() {} 
     P *pData; 
     Item *next; 
    }; 
    Item *head; 
public: 
    ...adding etc.. 
    P* operator [](int index) 
    { 
     See question below: 
    } 
}; 

Puis-je faire en quelque sorte assurer que les années « article sont attribués de telle sorte que je puisse calculer le décalage comme suit: (Peut-être pas :) @ Steve si clair ici; ce que j'ai besoin est un moyen rapide d'arriver à l'article sans itération à travers 10000 suivant.

Item *pi = head + (sizeof(Item) * (index - 1)); 

Un (clearer?) explanation de ce que je veux dire

Answer 1

Dépend de ce que vous entendez par "etc", dans "ajouter, etc". Si "etc" inclut "remove", alors vous avez le problème évident que si vous supprimez quelque chose au milieu de votre liste, alors pour maintenir l'indexation vous devez tout décaler vers le bas, ce qui signifie mettre à jour tout les pointeurs next.

Je pense que vous avez peut-être trop simplifié votre exemple. Si vous avez besoin d'un stockage contigu, utilisez un vecteur (P ou Item s'il y a quelque chose d'utile dans Item que vous avez supprimé). Si vous avez un stockage contigu, il n'y a aucun avantage à avoir un pointeur next, puisque vous pouvez simplement le calculer en Item, en ajoutant 1 à this (puis en vérifiant une limite pour vous assurer que vous n'avez pas atteint la fin).

Si vous avez besoin absolument le champ pointeur next public, car il fait partie d'une certaine interface que vous implémentez que vous ne pouvez pas changer, vous pouvez le mettre à jour dans le constructeur de copie et operator= pour Item, et l'interface a mieux interdire aux clients d'y écrire.

Il est impossible de demander à l'allocateur d'allocation de mémoire contiguë pour des allocations distinctes, si c'est ce que vous demandez. Comment cela fonctionnerait-il? Que se passe-t-il si, lorsque vous décidez d'allouer, l'adresse "suivante" est déjà occupée? Que faire si l'allocateur impose une surcharge, pour ses propres structures de contrôle (comme le font presque tous les allocateurs généraux), de sorte que l'allocation d'un Item nécessite plus de sizeof(Item) octets? Vous pouvez obtenir le comportement que vous voulez pendant un certain temps avec un fixed-size allocator, mais il a finalement besoin d'un nouveau bloc, ou vous supprimez quelque chose, et la relation ne tient plus.

Answer 2

Item* pi = (head + (index - 1)); 

fait le travail. Btw, êtes-vous sûr de vouloir faire ça? struct Item ressemble à la structure de liste liée (contient next).

Answer 3

Je suppose que vous avez besoin d'un fichier std :: list ou std :: vector.

Cependant, ce que vous essayez de faire fonctionnerait si vous avez alloué de la mémoire séquentielle pour les éléments et que la tête pointe vers le début avec la modification suggérée par Yossarian.

Vous pouvez pré-allouer lors de l'initialisation si cette limite est dépassée, allouer plus et copier votre contenu dans cette zone, libérant l'existant.

Note: Toutes ces choses sont emballées pour vous dans les conteneurs std.

Answer 4

« Les limites de la mémoire » peut être forcé par mots-clés gcc spéciaux

http://gcc.gnu.org/onlinedocs/gcc/Variable-Attributes.html#Variable-Attributes

regard sur « l'alignement »

Answer 5

Si je comprends bien votre question, vous devez remplacer operator new pour Item et ont l'allocateur pré-allouer suffisamment de mémoire pour stocker tous les Item s dont vous aurez besoin (ce qui n'est pas possible dans le cas général mais peut être possible dans votre scénario spécifique). Puis, à chaque fois qu'un Item est créé, l'allocateur renvoie l'emplacement suivant dans le bloc pré-alloué.

Tout cela semble irréaliste et la solution simple serait d'utiliser std::vector.