Liste liée d'intervalles

Question

J'ai les deux questions suivantes.

1. Je suis au courant du concept d'une liste chaînée . Qu'est-ce qu'une liste liée de intervalles?

2. Je dois stocker un très grand nombre (plus de 100 bits) en C/C++ et effectuer des opérations au niveau du bit. Sans utiliser de bibliothèque de grands nombres, quelle serait la meilleure structure de données pour gérer ce scénario?

Merci Vous

Answer 1

1. Le nom ne sonne pas de cloches. Si les intervalles sont des objets, il s'agit simplement d'une liste liée qui stocke ces objets. Peut-être que vous voulez dire un skip list?
2. Si vous utilisez C++, utilisez un bitset. Sinon, je voudrais juste utiliser une table classique de quatre octets 32 bits.

Answer 2

Pour la deuxième partie de la question, essayez std::bitset

Answer 3

Si vous voulez écrire votre propre classe pour gérer un grand nombre de bits (je ne sais pas pourquoi vous), vous pouvez envelopper un vecteur. Vous devriez cependant attraper votre propre débordement. C'est une énorme douleur, et je ne fais qu'apporter ça parce que c'était un projet final pour nous pour une classe C++ que j'ai suivie, lol. Je n'ai pas recommandé ceci = P

Answer 4

J'ai fait un commentaire sur ceci est une autre question, qui a été posée par quelqu'un d'autre. Ce semble pour faire référence à mon commentaire, alors je vais vous expliquer ce que je voulais dire. Ce que je proposais était:

struct interval_node { 
     int index; 
     struct interval_node* next; 
} 

où l'index stocke tous les points où le bit "retourne". Ceci est un énorme avantage de mémoire si vous avez quelque chose comme 11111111111100000000000, car il suffit de stocker le fait que le premier bit est 1 (en dehors de la structure quelque part), ainsi que le fait que le bit retourne dans le 12ème indice (étant 0- basé), plutôt que de stocker chaque bit individuel lui-même. Cela peut évoluer à 100.000 bits sans manger autant de mémoire tant que la séquence n'a pas une tonne de choses comme

1010101010101010101010101010101010101010101010 

Parce que plus il retourne à chaque bit.