STL-контейнеры: vector, map, set изнутри

template<class T>
class Vector {
    T* data;
    size_t size_;
    size_t capacity_;

    void reallocate(size_t new_cap) {
        T* new_data = new T[new_cap];
        // перемещаем существующие элементы
        for (size_t i = 0; i < size_; ++i)
            new_data[i] = std::move(data[i]);
        delete[] data;
        data = new_data;
        capacity_ = new_cap;
    }

public:
    void push_back(const T& value) {
        if (size_ == capacity_) {
            reallocate(capacity_ == 0 ? 1 : capacity_ * 2);
        }
        data[size_++] = value;
    }

    T& operator[](size_t i) { return data[i]; }   // O(1)
    size_t size() const { return size_; }
};

#include <map>
using namespace std;

int main() {
    map<string, int> scores;

    // Вставка: O(log n)
    scores["Alice"] = 90;
    scores["Bob"]   = 85;
    scores["Carol"] = 95;

    // Поиск: O(log n)
    auto it = scores.find("Bob");
    if (it != scores.end()) {
        cout << it->first << ": " << it->second << endl;
    }

    // Обход — в алфавитном порядке ключей
    for (auto& [name, score] : scores) {
        cout << name << " - " << score << endl;
    }

    // Удаление: O(log n)
    scores.erase("Bob");
}

#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(5);
    s.insert(3);
    s.insert(7);
    s.insert(5);   // дубликат — не добавится

    // Размер = 3, обход даст {3, 5, 7}
    for (int x : s) cout << x << " ";

    // Проверка наличия: O(log n)
    if (s.count(5)) cout << "5 есть в set" << endl;

    // Удаление: O(log n)
    s.erase(3);
}