s***j
发帖数: 5 | 1 Let's write a new class called int_map which:
1 Is an associative map of int -> int
2 Has a size specified at construction, and all mappings from 0 to size-1
initialized to the same specified value
3 Supports get/set of individual mappings
Let's keep the interface simple:
class int_map
{
... member variables ...
public:
int_map(int num_values, int initial_val);
int get(int index) const;
void set(int index, int value);
};
Problem 1: Write this class using a std::vector.
Problem 2:
Let's suppose we expect the mapping to contain long spans of identical
values, and that run-length encoding the map will yield good storage gains:
class rle_int_map
{
struct run
{
int m_stop;
int m_value;
};
// The first run implicitly starts at 0; all subsequent runs start at
the previous run's m_stop
std::vector m_runs;
public:
rle_int_map(int num_values, int initial_val)
{
m_runs.push_back({ num_values, initial_val });
}
int get(int index) const
{
// It is illegal to pass in an invalid index, for the purposes of
this exercise we can
// just assert()
assert(0 <= index && index < m_runs.back().m_stop);
for (auto const& r : m_runs)
{
if (r.m_stop > index)
return r.m_value;
}
assert(false); // Shouldn't get here
}
void set(int index, int value)
{
???
}
};
Can you write a more efficient version of rle_int_map::get()?
Problem 3: Provide a correct implementation of rle_int_map::set().
求解第二第三问？谁能解释下m_runs struct 的作用 |
|
