Inspecting pointers to objects inside a vector C++

Question

I am currently going through some code and I currently have a road class, with a vector of pointers to lanes (a private member), and this road class includes a lane class. This lane class contains a vector of pointers to vehicles, which is another class that contains simple get and set functions to update and obtain a vehicle's position, velocity etc. Now, I have vehicles moving in separate lanes and I allow them to switch lanes, as it is so in traffic flow. However, I would like my vehicles to continuously find a distance from it and the vehicle in front, i.e., look in the vehicles vector and find the closest vehicle. Then I intend to use that to instruct whether a car should decelerate or not. I would also like to make sure that cars which are leading the rest, since once a vehicle leaves the displaywindow height, they should be deleted.

My attempt at this is as follows:

void Lane::Simulate(double time)
{ // This simulate allows check between other vehicles.

double forwardDistance = 0;
    for (unsigned int iV = 0; iV < fVehicles.size(); iV++) 
    {
        for(unsigned int jV = 0; jV < fVehicles.size(); jV++)
        {
            forwardDistance = fVehicles[iV]->getPosition() - fVehicles[jV]->getPosition();
        }
    }

    if(fVehicles.size() < 15)
    {
        addRanVehicle(); // Adds a vehicle, with position zero but random velocities, to each lane.
    }

    for (unsigned int iVehicle = 0; iVehicle < fVehicles.size(); iVehicle++)
    {
        fVehicles[iVehicle]->Simulate(time); // Updates position based on time, velocity and acceleration.
    }
}

There may be a much better method than using this forwardDistance parameter. The idea is to loop over each pair of vehicles, avoid the point iV == jV, and find the vehicle which is in front of the iVth vehicle, and record the distance between the two vehicles into a setDistance() function (which is a function of my Vehicle class). I should then be able to use this to check whether a car is too close, check whether it can overtake, or whether it just has to brake.

Currently, I am not sure how to make an efficient looping mechanism for this.

You don't appear to use `forwardDistance` after computing it. — Justin Randall, Dec 08 '17 at 22:11
I know I haven't used it. I am unsure how to make an efficient loop which finds the smallest distance between two vehicles in the lane, i.e. the distance between a vehicle and a vehicle in front of it. Apologies for being very unclear — PaleoPhys, Dec 08 '17 at 22:18
So you are checking the distance between the current vehicle in the lane and all others in the same lane? Presumably fVehicles is a vector? You want to compute the smallest distance found between any two vehicles in the lane? — Justin Randall, Dec 08 '17 at 22:27
Who owns (is responsible for maintaining and `delete`ing) the `Vehicle`s? If the answer is the lane, save yourself some trouble and let `fVehicles` store the `Vehicle`s directly. Less memory management overhead and most likely significant performance boost (no pointer chasing and better prediction/caching behaviour) — user4581301, Dec 08 '17 at 22:28
You can simplify the code a lot with range-based `for` loops. `for (Vehicle & v_outer: fVehicles){ for (Vehicle & v_inner: fVehicles){ forwardDistance = v_outer.getPosition() - v_inner.getPosition(); } } ` — user4581301, Dec 08 '17 at 22:32
Can vehicles change position inside the lane? If not then all you should need is a single loop that computes `forwardDistance = fVehicles[n]->getPosition() - fVehicles[n-1]->getPosition();` — user4581301, Dec 08 '17 at 22:35
@user4581301 Thanks for that, I am not sure exactly how that works, could you provide more details about what your range-based for loop does? In reply to your question, yes, I have a vector called fVehicles. However, this is a private member of my lane class, and I delete vehicles if they switch lanes. — PaleoPhys, Dec 08 '17 at 22:37
A `std::deque` may be a better data structure to store the vehicles in the lane. A monitored stretch of a road will add cars on one side and remove from the other you add on one side and remove from another, behaviour at which a deque` greatly out performs a `vector`. — user4581301, Dec 08 '17 at 22:37
@user4581301 I don't believe I can do simply `forwardDistance = ` nth vehicle's position `-` (n+1)th vehicle's position, since the order of the vehicles in the vector does not necessarily represent the positional order. This is because a can have vehicles switching lanes, so I just insert these overtaking vehicles into the beginning of the fVehicles vector. — PaleoPhys, Dec 08 '17 at 22:40
In that case, consider how often a `Vehicle` changes lanes vs how often you iterate through the list of `Vehicle`s. Performing an O(N^2) algorithm every simulation tick will probably exceed the costs of performing an O(N) every tick and occasionally an O(N) ordered insert that places the car in the correct position in the lane. This will also make visualization a lot easier. — user4581301, Dec 08 '17 at 22:48

user4581301 · Accepted Answer · 2017-12-09T08:59:13.947

Investigate the cost of performing an ordered insert of Vehicles into the lane. If the Vehicles are ordered according to position on the road, detecting the distance of two Vehicles is child's play:

Eg

for (size_t n = 0; n < fVehicles.size() - 1; n++)
{
    distance = fVehicles[n].getPosition() - fVehicles[n+1].getPosition();
}

This is O(N) vs O(N^2) (using ^ as exponent, not XOR). The price of this simplification is the requiring ordered insert into fVehicles, and that should be O(N): One std::binary_search to detect the insertion point and whatever shuffling is required by fVehicles to free up space to place the Vehicle.

Maintaining ordering of fVehicles may be beneficial in other places as well. Visualizing the list (graphically or by print statements) will be much easier, debugging is generally easier on the human brain when everything is in a nice predictable order, and CPUs... They LOVE going in a nice, predictable straight line. Sometimes you get a performance boost that you didn't see coming. Great write-up on that here: Why is it faster to process a sorted array than an unsorted array?

Only way to be sure if this is better is to try it and measure it.

Other Suggestions:

Don't use pointers to the vehicles.

Not only are they harder to manage, they can slow you down quite a bit. As mentioned above, modern CPUs are really good at going in straight lines, and pointers can throw a kink in that straight line.

You never really know where in dynamic memory a pointer is going to be relative to the last pointer you looked at. But with a contiguous block of Vehicles , when the CPU loads Vehicle N it can possibly also grab Vehicles N+1 and N+2. If it can't because they are too big, it doesn't matter much because it already knows where they are, and while the CPU is processing, and idle memory channel could be reading ahead and grabbing the data you're going to need soon.

With the pointer you save a bit every time you move a Vehicle from lane to lane (pointers are usually much cheaper than objects to copy), but may suffer on each and every loop iteration in each and every simulation tick and the volume really adds up. Bjarne Stroustrup, God-Emperor of C++, has an excellent write up on this problem using linked lists as an example (Note linked list is often worse than vector of pointer, but the idea is the same).

Take advantage of std::deque.

std::vector Is really good at stack-like behaviour. You can add to and remove from the end lightning fast, but if you add to or remove from the beginning, everything in the vector is moved.

Most of the lane insertions are likely to be at one end and the removals at the other simply because older Vehicles will gravitate toward the end as Vehicles are added to the beginning or vise versa. This is a certainty if suggestion 1 is taken and fVehicles is ordered. New vehicles will be added to the lane at the beginning, a few will change lanes into or out of the middle, and old vehicles will be removed from the end. deque is optimized for inserting and removing at both ends so adding new cars is cheap, removing old cars is cheap and you only pay full price for cars that change lanes.

Documentation on std::deque

Addendum

Take advantage of range-based for where possible. Range-based for takes most of the iteration logic away and hides it from you.

Eg this

for (unsigned int iV = 0; iV < fVehicles.size(); iV++) 
{
    for(unsigned int jV = 0; jV < fVehicles.size(); jV++)
    {
        forwardDistance = fVehicles[iV]->getPosition() - fVehicles[jV]->getPosition();
    }
}

becomes

for (auto v_outer: fVehicles) 
{ 
    for (auto v_inner: fVehicles) 
    { 
        forwardDistance = v_outer->getPosition() - v_inner->getPosition(); 
    } 
}

It doesn't look much better if you are counting lines, but you can't accidentally

iV <= fVehicles.size()

or

fVehicles[iV]->getPosition() - fVehicles[iV]->getPosition()

It removes the possibility for you to make silly, fatal, and hard-to-spot errors.

Let's break one down:

for (auto v_outer: fVehicles) 
     ^    ^        ^
  type    |        |
  variable name    | 
           Container to iterate

Documentation on Range-based for

In this case I'm also taking advantage of auto. auto allows the compiler to select the type of the data. The compiler knows that fVehicles contains pointers to Vehicles, so it replaces auto with Vehicle * for you. This takes away some of the headaches if you find yourself refactoring the code later.

Documentation on auto

Unfortunately in this cans it can also trap you. If you follow the suggestions above, fVehicles becomes

std::dequeue<Vehicle> fVehicles;

which means auto is now Vehicle. Which makes v_outer a copy, costing you copying time and meaning if you change v_outer, you change a copy and the original goes unchanged. to avoid that, tend toward

for (auto &v_outer: fVehicles)

The compiler is good at deciding how best to handle that reference or if it even needs it.

I appreciate the extensive reply from yourself. If I use `&v_outer: fVehicles`, does this mean I must use `&v_outer` in the code following the for loop? For example, do I need to use `forwardDistance = &v_outer`...? — PaleoPhys, Dec 09 '17 at 18:28
@KarandeepGiddha The `&` declares `v_outer` [to be a reference](http://en.cppreference.com/w/cpp/language/reference_initialization) to an element in `fVehicles` A reference can be looked at as an alias to a variable. The reference is used exactly the same way you would whatever it refers to, so that means no extra syntax. `v_outer.getPosition()` would call the `getPosition` function. The best way to learn about references would be reading a C++ language text. — user4581301, Dec 09 '17 at 18:37

Inspecting pointers to objects inside a vector C++

1 Answers1

Other Suggestions:

Addendum