Exceptional C++ Style 40 New Engineering Puzzles, Programming Problems, and Solutions

Chapter 26. Data Formats and Efficiency, Part 1: When Compression Is the Name of the Game

Difficulty: 4

How good are you at choosing highly compact and memory-efficient data formats? How good are you at writing bit-twiddling code? This Item and the next give you ample opportunity to exercise both skills as we consider efficient representations of chess games and a BitBuffer to hold them.

Background: I assume you know the basics of chess.

JG Question

1. Which of these standard containers uses the least memory to store the same number of objects of the same type T: deque, list, set, or vector? Explain.

Guru Question

1. You are creating a worldwide chess server that stores all games ever played on it. Because the database can get very large, you want to represent ...