La structure std::vector en C++ est un conteneur de la bibliothèque standard (STL) qui se comporte comme un tableau dynamique. Elle offre la capacité d'ajustement dynamique de sa taille et permet un accès rapide aux éléments par indice. Les éléments d'un vector sont stockés de manière contiguë en mémoire, ce qui facilite l'accès via des pointeurs ou des indices. Le vector gère automatiquement l'allocation et la désallocation de sa mémoire interne, prenant en charge les opérations courantes comme l'insertion, la suppression et le parcours des éléments.

Fonctionnalités courantes d'un vector

Constructeurs

Le vector peut être initialisé de plusieurs manières : - vector(size_type count, const T& value = T()) : Crée un vecteur contenant count copies de value.

• vector(const vector& other) : Constructeur par copie, crée un nouveau vecteur identique à other.
• vector(InputIterator first, InputIterator last) : Construit le vecteur en copiant les éléments de la plage [first, last).

Itérateurs

Les itérateurs permettent de parcourir les éléments du vecteur : - begin() et end() : Retournent des itérateurs pointant respectivement sur le premier élément et sur la position suivant le dernier élément.

• rbegin() et rend() : Retournent des itérateurs inverses pointant sur le dernier élément et sur la position précédant le premier élément.

Capacité

Les fonctions suivantes gèrent la capacité et la taille du vecteur : - capacity() : Retourne la capacité actuelle allouée pour le stockage des éléments.

• size() : Retourne le nombre d'éléments actuellement présents dans le vecteur.
• empty() : Vérifie si le vecteur est vide.
• resize(size_type count, const T& value = T()) : Modifie la taille du vecteur. Si count est supérieur à la taille actuelle, de nouveaux éléments sont ajoutés et initialisés avec value. Si count est inférieur, les éléments excédentaires sont supprimés.
• reserve(size_type new_cap) : Demande au vecteur d'augmenter sa capacité pour au moins new_cap éléments.

Modification

Opérations pour modifier le contenu du vecteur : - push_back(const T& value) : Ajoute un élément à la fin du vecteur.

• pop_back() : Supprime le dernier élément du vecteur.
• insert(const_iterator pos, const T& value) : Insère un élément avant la position spécifiée par pos.
• erase(const_iterator pos) : Supprime l'élément à la position spécifiée par pos.
• swap(vector& other) : Échange le contenu de deux vecteurs.
• operator[](size_type pos) : Accède à l'élément à l'indice pos (sans vérification de limites).
• at(size_type pos) : Accède à l'élément à l'indice pos (avec vérification de limites, lance une exception en cas de dépassement).

Implémentation simulée d'un vector

Pour simuler un vector, nous allons créer une classe template encapsulant trois pointeurs : \_start, \_finish, et \_end\_of\_storage. Ces pointeurs délimitent respectivement le début des données, la fin des données utilisées, et la fin de la mémoire allouée. ```cpp

namespace my_vector { template class Vector { public: using iterator = T*; using const_iterator = const T*;

private:
    iterator _start;             // Pointeur vers le début de la mémoire allouée
    iterator _finish;            // Pointeur vers la fin des données utilisées
    iterator _end_of_storage;    // Pointeur vers la fin de la mémoire allouée

    // Fonction d'aide pour la gestion de la capacité
    void reallocate(size_t new_capacity) {
        // Alloue la nouvelle mémoire
        T* new_data = new T[new_capacity];

        // Copie les éléments existants si la mémoire a été allouée
        if (_start) {
            for (size_t i = 0; i < size(); ++i) {
                new_data[i] = std::move(_start[i]); // Utilise move pour une meilleure efficacité
            }
            delete[] _start; // Libère l'ancienne mémoire
        }

        _start = new_data;
        _finish = _start + size(); // Ajuste _finish en fonction du nombre d'éléments copiés
        _end_of_storage = _start + new_capacity; // Met à jour le pointeur de fin de stockage
    }

public:
    // Constructeur par défaut
    Vector() : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}

    // Constructeur avec taille et valeur
    explicit Vector(size_t count, const T& value = T()) {
        resize(count, value);
    }

    // Constructeur par copie
    Vector(const Vector& other) {
        if (other.capacity() > 0) {
            _start = new T[other.capacity()];
            for (size_t i = 0; i < other.size(); ++i) {
                _start[i] = other._start[i];
            }
            _finish = _start + other.size();
            _end_of_storage = _start + other.capacity();
        } else {
            _start = nullptr;
            _finish = nullptr;
            _end_of_storage = nullptr;
        }
    }

    // Opérateur d'assignation par copie (utilisant la technique du copy-and-swap)
    Vector& operator=(Vector other) {
        swap(other);
        return *this;
    }

    // Destructeur
    ~Vector() {
        if (_start) {
            delete[] _start;
            _start = _finish = _end_of_storage = nullptr;
        }
    }

    // Constructeur à partir d'itérateurs
    template<class inputiterator="">
    Vector(InputIterator first, InputIterator last) {
        assign(first, last);
    }

    // Fonctions de swap
    void swap(Vector& other) {
        std::swap(_start, other._start);
        std::swap(_finish, other._finish);
        std::swap(_end_of_storage, other._end_of_storage);
    }

    // Fonctions de capacité
    size_t size() const {
        return _finish - _start;
    }

    size_t capacity() const {
        return _end_of_storage - _start;
    }

    bool empty() const {
        return _start == _finish;
    }

    void reserve(size_t new_cap) {
        if (new_cap > capacity()) {
            reallocate(new_cap);
        }
    }

    void resize(size_t count, const T& value = T()) {
        if (count > size()) {
            if (count > capacity()) {
                reserve(count); // Assure suffisamment de capacité
            }
            // Ajoute les nouveaux éléments
            while (size() < count) {
                push_back(value);
            }
        } else if (count < size()) {
            // Supprime les éléments excédentaires
            _finish = _start + count;
        }
    }

    // Fonctions de modification
    void push_back(const T& value) {
        if (_finish == _end_of_storage) {
            size_t new_capacity = (capacity() == 0) ? 4 : capacity() * 2;
            reserve(new_capacity);
        }
        *_finish = value;
        ++_finish;
    }

    void pop_back() {
        if (!empty()) {
            --_finish;
            // Détruire l'élément si nécessaire (pour les types non triviaux)
            // _finish->~T(); // Pas nécessaire pour l'implémentation simple ici
        }
    }

    iterator insert(const_iterator pos, const T& value) {
        if (pos < _start || pos > _finish) {
            throw std::out_of_range("Invalid position for insert");
        }

        if (_finish == _end_of_storage) {
            size_t offset = pos - _start;
            reserve(capacity() == 0 ? 4 : capacity() * 2);
            pos = _start + offset; // Recalculer pos après réallocation
        }

        // Décaler les éléments pour faire de la place
        // Utilisation de std::move pour potentiellement optimiser
        for (iterator it = _finish; it != pos; --it) {
            *(it) = std::move(*(it - 1));
        }

        *const_cast<t>(pos) = value; // Insérer la nouvelle valeur
        ++_finish;
        return const_cast<t>(pos);
    }

    iterator erase(const_iterator pos) {
        if (pos < _start || pos >= _finish) {
            throw std::out_of_range("Invalid position for erase");
        }

        // Décaler les éléments pour combler le trou
        // Utilisation de std::move pour potentiellement optimiser
        for (iterator it = const_cast<t>(pos); it != _finish - 1; ++it) {
            *it = std::move(*(it + 1));
        }

        --_finish;
        // Détruire l'élément supprimé si nécessaire (pour les types non triviaux)
        // (_finish)->~T();
        return const_cast<t>(pos);
    }

    // Accès aux éléments
    T& operator[](size_t pos) {
        // Pas de vérification de limites pour la performance, comme std::vector
        return _start[pos];
    }

    const T& operator[](size_t pos) const {
        return _start[pos];
    }

    T& at(size_t pos) {
        if (pos >= size()) {
            throw std::out_of_range("Vector out of range");
        }
        return _start[pos];
    }

    const T& at(size_t pos) const {
        if (pos >= size()) {
            throw std::out_of_range("Vector out of range");
        }
        return _start[pos];
    }

    // Itérateurs
    iterator begin() {
        return _start;
    }

    const_iterator begin() const {
        return _start;
    }

    iterator end() {
        return _finish;
    }

    const_iterator end() const {
        return _finish;
    }
    
    // Méthode d'assignation à partir d'itérateurs
    template<class inputiterator="">
    void assign(InputIterator first, InputIterator last) {
        clear(); // Vider le contenu actuel
        size_t count = 0;
        for (InputIterator it = first; it != last; ++it) {
            ++count;
        }
        reserve(count); // Réserver la capacité nécessaire
        for (InputIterator it = first; it != last; ++it) {
            push_back(*it);
        }
    }
    
    void clear() {
        // Pour les types non triviaux, il faudrait détruire les éléments
        // for(iterator it = _start; it != _finish; ++it) { it->~T(); }
        _finish = _start;
    }
};

}