1

I have a vector in which i save coordinates. I perform a series of calculations on each coordinate, thats why i have a limit for the vector size. Right now i clear the vector, when the limit is reached. I'm searching for a method, that let's me keep the previous values and only erases the very first value in the vector.

Simplified, something like this (if the maximum size of the vector would be 4).

vector<int> vec;
vec = {1,2,3,4}
vec.push_back(5);

vec = {2,3,4,5}

Is this possible?

CodeCommander
  • 28
  • 4
  • Related: [https://stackoverflow.com/questions/875103/how-do-i-erase-an-element-from-stdvector-by-index](https://stackoverflow.com/questions/875103/how-do-i-erase-an-element-from-stdvector-by-index) – drescherjm Dec 08 '21 at 14:07
  • 3
    Sounds like you want a ring buffer / circular queue. You can implement that in a fixed-size vector by maintaining a 'tail' index and a 'count'. Doing _actual_ repeated erases from the front of a vector is normally a bad idea because each one is O(N). If you really want to grow and shrink the container in a queue-like fashion, use `std::deque` instead. – paddy Dec 08 '21 at 14:22

2 Answers2

2

As suggested by @paddy, you can use std::deque, it is most performant way to keep N elements if you .push_back(...) new (last) element, and .pop_front() first element.

std::deque gives O(1) complexity for such operations, unlike std::vector which gives O(N) complexity.

Try it online!

#include <deque>
#include <iostream>

int main() {
    std::deque<int> d = {1, 2, 3, 4};
    for (size_t i = 5; i <= 9; ++i) {
        d.push_back(i);
        d.pop_front();

        // Print
        for (auto x: d)
            std::cout << x << " ";
        std::cout << std::endl;
    }
}

Output:

2 3 4 5 
3 4 5 6 
4 5 6 7 
5 6 7 8 
6 7 8 9
Arty
  • 14,883
  • 6
  • 36
  • 69
1

I think you should properly encapsulate this behaviour in your own vector class, as a std::vector wrapper. You could pass the max capacity as an argument to your constructor. And you could reimplement the methods that may cause "overflow" while just reusing the std::vector ones for the others.

To simplify what you pretend to achieve for the push_back case, using a function and a global variable, you could:

  • check against a max capacity and,
  • if that capacity is already reached, rotate your vector contents left by one position; then simply overwrite the last element;
  • otherwise do a normal push_back.

[Demo]

#include <algorithm>  // rotate
#include <iostream>  // cout
#include <vector>

const size_t max_capacity{4};

void push_back(std::vector<int>& v, int n)
{
    if (v.size() == max_capacity)
    {
        // Rotate 1 left
        std::rotate(std::begin(v), std::begin(v) + 1, std::end(v));
        v[v.size() - 1] = n;
    }
    else
    {
        v.push_back(n);
    }
}

int main() 
{
    std::vector<int> v{};
    for (auto i{1}; i < 9; i++)
    {
        push_back(v, i);

        for (auto&& n : v) { std::cout << n << " "; }
        std::cout << "\n";
    }
}
rturrado
  • 7,699
  • 6
  • 42
  • 62
  • 1
    Thanks for nice variant of solution, up-voted! I didn't know that there exists `std::rotate`, new thing to learn for me! – Arty Dec 08 '21 at 14:51
  • 2
    Then you have to see this CppCon 2013 video by Sean Parent's. I think he made `rotate` a bit more famous since then :) https://youtu.be/W2tWOdzgXHA – rturrado Dec 08 '21 at 15:12