CODEWITHSUNDEEP
c++oopmemorymemory-management
Remi.b
Remi.b

Reputation: 18219

How to have objects contiguous in memory without loosing OOP?

Consider a code where we have a list of countries that contain a list of cities that contains a list of streets. Each City in a given Country contains exactly the same number of Streets (nbStreetsPerCity) and this number of streets per City is constant over time.

class Street
{

};

class City
{
   // Attribute
   std::vector<Street> Streets;

   // getter
   Street& getStreet(int street_index) {return Streets[street_index];}
   // More stuff 

};

class Country
{
   // Attribute
   std::vector<City> Cities;

   // getter
   City& getCity(int city_index) {return Cities[city_index];}

   // More stuff 

};

I have to loop through each Street and the process is quite fast when I have many Streets and few Cityies but is quite slow when I have many Cityies with few Streets

With such code, the Streets of all Cityies of a given Country are not contiguous in memory. For performance reasons, I would like to try a code with having all Streets of a given Country being contiguous in memory. I can't think of a way to have all the Streets contiguous in memory without destroying part of the object oriented programming.

class Street
{

};


class Country
{
   // Attribute
   std::vector<Street> Streets;
   int nbStreetsPerCity;

   // getter
   City getStreet(int city_index, int street_index)
   {
       Streets[city_index*nbStreetsPerCity + street_index]
   };

   // More stuff 

};

With such code, all Streets of a given country are contiguous in memory, however, I lost the City object and therefore lost the advantage of OOP.

Is there a way to have all streets being contiguous in memory without loosing the advantage of OOP?

A very simple example would be very welcome!

Upvotes: 2

Views: 111

Answers (2)

UKMonkey
UKMonkey

Reputation: 6993

The way to do this is to have a 'StreetManager' that contains your vector of streets. Your City and Country then contain references to the streets held by your street manager.

When I say 'references' these may be just indexes or some id or anything else that will allow lookup as per your read/write requirements.
By read/write requirements, I refer to the fact that references may be broken on vector edit, indexes will be broken on vector removal, and id will require a map of id -> index maintained by the manager.

The functions 'getStreets' in your City/country then just need to hand the indexes/ids to the manager and return the result.

The important thing to bear in mind is that attempting to edit the # of Streets in the manager will result in all the references being broken.

Upvotes: 2

SoronelHaetir
SoronelHaetir

Reputation: 15162

It can be done for the lowest level of such a fan-out but it would be a massive pain, for one thing you would have to know how many streets a city has before the allocation, and for another each street would have to be an equal sized object (meaning street names would have a maximum length).

You would replace the vector with a count and zero-sized array at the end of the city object, and instead of allocating with new you would have to use malloc or some other allocator and then use placement new to initialize the city into that buffer. You would then go through the list of steets and copy them into the array that actually exits after the city object.

Like I said, it can be done but is a pain. Make sure you actually have reason to do something like thins before going down such a path.

Upvotes: 0

Related Questions