Реализация shrink_to_fit для множества векторов

25 апреля 2021, 09:00

Есть шаблон класса, хранящий множество векторов:

template <class T>
class Lots {
    std::set<std::vector<T>> sv;
public:     
    //есть функции, выполняющие различные действия с элементами sv  
    //в том числе и вставка/удаление    
};

Может быть, что обьект sv вполне может хранить вектора, занимающие память с запасом, например такие(специально грубый пример):

    vector<int> v1, v2, v3;
    v1.reserve(10);
    v2.reserve(v1.capacity() * 3);
    v3.reserve(2 * v2.capacity());
    int n, m;
    cin >> n;
    m = n % 10;
    for (int i = 0; i < m; ++i) {
        v1.push_back(i + 1);
        v2.push_back(i + 2);
        v3.push_back(i + 3);
    }

где неизвестно, какой обьем займут данные. По этой причине я решил добавить в класс метод shrink_to_fit и реализовать следующим образом:

template <class T>
void Lots<T>::shrink_to_fit() {
    auto It = sv.begin();
    for (auto v : sv) {
        v.shrink_to_fit();
        sv.insert(It++, v);
    }
}

Но тут есть недостаток: копируются все вектора и при чтении и при записи.

Как реализовать ее лучше?
Возможно ли сжать вектора не полностью, а, скажем, с запасом на 2 элемента? P.S. Учитывая содержание комментариев... если я не очень ясно выразился, прошу простить и стараться понять суть вопроса

Answer 1

При желании можно что-то придумать, но это не очень правильно.

#include <iostream>
#include <set>
#include <vector>
#include <functional>
template<typename T>
class MyVector{
public:
    MyVector() = default;
    MyVector(const std::initializer_list<T>& l):
        m_v{l}
    {}
    MyVector(const MyVector&) = default;
    MyVector& operator=(const MyVector&) = default;
    virtual ~MyVector() = default;
    void shrink_to_fit() const{
        m_v.shrink_to_fit();
    }
    bool operator<(const MyVector& other) const{
        return m_v < other.m_v;
    }
    std::vector<T>& value() const{
        return m_v;
    }
private:
    mutable std::vector<T> m_v;
};
int main()
{
    std::set<MyVector<int>> sv{
        {1,2,3,5},
        {3,4,5}
    };
    for (auto& v: sv){
        v.value().reserve(100);
        std::cout << v.value().capacity() << std::endl;
    }
    for (auto& v: sv){
        v.shrink_to_fit();
        std::cout << v.value().capacity() << std::endl;
    }
    return 0;
}