7. hét: Tároló osztályok

A memóriát char[] tömbből kell építeni, de Gadget objektumokat fog tartalmazni, és azokra mutató pointerekkel kell dolgozni. Ezért kell reinterpret_cast<Gadget*>-ot használni, amikor a memóriaterületen a Gadget-ek címeit ki kell számolni.

Az összes Gadget-et felszabadító függvény meghívhatja a Gadget-ek destruktorait is.

A Gadget osztály ha final, nem lehet már leszármazni belőle. Így nincs olyan veszély, hogy egy nagyobb méretű leszármazottal kel foglalkoznia az allocate() függvénynek.

A két osztály deklarációi és definíciói egymásra hivatkoznak; a Gadget::operator new előre hivatkozik a GadgetAllocator::allocate() függvényre, a GadgetAllocator osztály definíciója pedig a sizeof(Gadget) értékére. Ezért nem tudjuk osztályon belül definiálni a függvényeket.

#include <new>
#include <iostream>
#include <stdexcept>
#include <vector>

#define DEBUG 0

//
// Sample object which will be allocated from a memory pool
//
class Gadget final {
  public:
    Gadget(int i) : i_(i) { std::cout << "Gadget " << i_ << " ctor\n"; }
    ~Gadget() { std::cout << "Gadget " << i_ << " dtor\n"; }
    
    void * operator new(size_t size);
    void operator delete(void *mem) noexcept;
  private:
    int i_;
};


//
// Memory pool for Gadget objects
//
class GadgetAllocator {
  public:
    friend class Gadget;
    static void show_allocation_map();
    static void delete_all();
    
  private:
    static void *allocate();
    static void free(void *mem);
    static constexpr size_t poolsize_ = 64;
    static char pool_[sizeof(Gadget) * poolsize_];
    static bool allocated_[poolsize_];
};

char GadgetAllocator::pool_[sizeof(Gadget) * poolsize_];
bool GadgetAllocator::allocated_[poolsize_];


void *GadgetAllocator::allocate() {
    /* find first unallocated */
    size_t i;
    for (i = 0; i != poolsize_; ++i)
        if (allocated_[i] == false)
            break;
    /* if did not break, no more memory left */
    if (i == poolsize_) {
#if DEBUG
        std::cerr << "Cannot allocate Gadget" << std::endl;
#endif
        throw std::bad_alloc{};
    }
    /* set allocated flag */
#if DEBUG
    std::cerr << "Allocating Gadget at " << i << std::endl;
#endif
    allocated_[i] = true;
    return static_cast<void*>(reinterpret_cast<Gadget*>(pool_) + i);
}


void GadgetAllocator::free(void *mem) {
    /* calculate index */
    size_t i = static_cast<Gadget*>(mem) - reinterpret_cast<Gadget*>(pool_);
    /* check if proper pointer and allocated */
    if (i >= poolsize_ || !allocated_[i]) {
#if DEBUG
        std::cerr << "Cannot deallocate " << mem << std::endl;
#endif
        throw std::bad_alloc{};
    }
    /* reset allocated flag */
#if DEBUG
    std::cerr << "Freeing Gadget at " << i << std::endl;
#endif
    allocated_[i] = false;
}


void GadgetAllocator::show_allocation_map() {
    for (size_t i = 0; i != poolsize_; ++i) {
        std::cout << allocated_[i];
        if ((i+1) % 16 == 0)
            std::cout << std::endl;
    }
}


void GadgetAllocator::delete_all() {
    for (size_t i = 0; i != poolsize_; ++i) {
        if (allocated_[i]) {
            reinterpret_cast<Gadget*>(pool_)[i].~Gadget();
            allocated_[i] = false;
        }
    }
}


// Allocator and deallocator for Gadgets - calls GadgetAllocator's functions
void * Gadget::operator new(size_t size) {
    return GadgetAllocator::allocate();
}

void Gadget::operator delete(void *mem) noexcept {
    return GadgetAllocator::free(mem);
}


int main() {
    std::vector<Gadget*> my_gadgets;
    
    std::cout << "Allocate 10 gadgets:" << std::endl;
    for (int i = 0; i < 10; ++i)
        my_gadgets.push_back(new Gadget{i});
    GadgetAllocator::show_allocation_map();
    
    std::cout << "Delete 5 random gadgets:" << std::endl;
    for (int i = 0; i < 5; ++i) {
        int del = rand() % my_gadgets.size();
        delete my_gadgets[del];
        my_gadgets[del] = my_gadgets.back();
        my_gadgets.pop_back();
    }
    GadgetAllocator::show_allocation_map();
    
    std::cout << "2 new gadgets to empty slots:" << std::endl;
    my_gadgets.push_back(new Gadget{11});
    my_gadgets.push_back(new Gadget{12});
    GadgetAllocator::show_allocation_map();
    
    std::cout << "Use up all remaining slots:" << std::endl;
    try {
        while (true)
            my_gadgets.push_back(new Gadget{rand() % 100});
    } catch (std::bad_alloc &) {
    }
    GadgetAllocator::show_allocation_map();
    
    std::cout << "Delete all gadgets not deleted so far:" << std::endl;
    GadgetAllocator::delete_all();
    GadgetAllocator::show_allocation_map();
}

#include <new>
#include <iostream>
#include <stdexcept>
#include <vector>

#define DEBUG 0

class GadgetAllocator;

class Gadget final {
  public:
    Gadget(int i) : i_(i) { std::cout << "Gadget " << i_ << " ctor\n"; }
    ~Gadget() { std::cout << "Gadget " << i_ << " dtor\n"; }
    
    void * operator new(size_t size);
    void * operator new(size_t size, GadgetAllocator &allocator);
    void operator delete(void *mem) noexcept;
  private:
    int i_;
    GadgetAllocator *allocator_;
};


//
// Memory pool for Gadget objects
//
class GadgetAllocator {
  public:
    
    GadgetAllocator() : allocated_{} {}
    GadgetAllocator(GadgetAllocator const &) = delete;
    GadgetAllocator& operator=(GadgetAllocator const &) = delete;
    ~GadgetAllocator() { delete_all(); }
    void show_allocation_map();
    void delete_all();

    friend class Gadget;
    
  private:
    void *allocate();
    void free(void *mem);
    static constexpr size_t poolsize_ = 64;
    char pool_[sizeof(Gadget) * poolsize_];
    bool allocated_[poolsize_];
};

void GadgetAllocator::show_allocation_map() {
    for (size_t i = 0; i != poolsize_; ++i) {
        std::cout << allocated_[i];
        if ((i+1) % 16 == 0)
            std::cout << std::endl;
    }
}
    
void *GadgetAllocator::allocate() {
    /* find first unallocated */
    size_t i;
    for (i = 0; i != poolsize_; ++i)
        if (allocated_[i] == false)
            break;
    /* if did not break, no more memory left */
    if (i == poolsize_) {
#if DEBUG
        std::cerr << "Cannot allocate Gadget" << std::endl;
#endif
        throw std::bad_alloc{};
    }
    /* set allocated flag */
#if DEBUG
    std::cerr << "Allocating Gadget at " << i << std::endl;
#endif
    allocated_[i] = true;
    return static_cast<void*>(reinterpret_cast<Gadget*>(pool_) + i);
}

void GadgetAllocator::free(void *mem) {
    /* calculate index */
    size_t i = static_cast<Gadget*>(mem) - reinterpret_cast<Gadget*>(pool_);
    /* check if proper pointer and allocated */
    if (i >= poolsize_ || !allocated_[i]) {
#if DEBUG
        std::cerr << "Cannot deallocate " << mem << std::endl;
#endif
        throw std::bad_alloc{};
    }
    /* reset allocated flag */
#if DEBUG
    std::cerr << "Freeing Gadget at " << i << std::endl;
#endif
    allocated_[i] = false;
}

void GadgetAllocator::delete_all() {
    for (size_t i = 0; i != poolsize_; ++i) {
        if (allocated_[i]) {
            reinterpret_cast<Gadget*>(pool_)[i].~Gadget();
            allocated_[i] = false;
        }
    }
}


// Allocator and deallocator for Gadgets - calls GadgetAllocator's functions
// Default operator new: allocate from free store
void * Gadget::operator new(size_t size) {
    void *mem = ::operator new(size);
    Gadget *constructed_gadget = static_cast<Gadget *>(mem);
    constructed_gadget->allocator_ = nullptr;
    return mem;
}

// Allocate from GadgetAllocator
void * Gadget::operator new(size_t size, GadgetAllocator &allocator) {
    void *mem = allocator.allocate();
    Gadget *constructed_gadget = static_cast<Gadget *>(mem);
    constructed_gadget->allocator_ = &allocator;
    return mem;
}

// Deallocate Gadget. If allocator is null, delete from free store,
// if not null, ask allocator to deallocate.
void Gadget::operator delete(void *mem) noexcept {
    Gadget const *deleted_gadget = static_cast<Gadget const *>(mem);
    if (deleted_gadget->allocator_ == nullptr)
        ::operator delete(mem);
    else
        deleted_gadget->allocator_->free(mem);
}


int main() {
    {
        GadgetAllocator a1;
        
        std::vector<Gadget*> my_gadgets;
        
        std::cout << "Allocate 10 gadgets:" << std::endl;
        for (int i = 0; i < 10; ++i)
            my_gadgets.push_back(new (a1) Gadget{i});
        a1.show_allocation_map();
        
        std::cout << "Delete 5 random gadgets:" << std::endl;
        for (int i = 0; i < 5; ++i) {
            int del = rand() % my_gadgets.size();
            delete my_gadgets[del];
            my_gadgets[del] = my_gadgets.back();
            my_gadgets.pop_back();
        }
        a1.show_allocation_map();
        
        std::cout << "2 new gadgets to empty slots:" << std::endl;
        my_gadgets.push_back(new (a1) Gadget{11});
        my_gadgets.push_back(new (a1) Gadget{12});
        a1.show_allocation_map();
        
        std::cout << "Use up all remaining slots:" << std::endl;
        try {
            while (true)
                my_gadgets.push_back(new (a1) Gadget{rand() % 100});
        } catch (std::bad_alloc &) {
        }
        a1.show_allocation_map();
        
        std::cout << "Exiting code block, allocator will be destructed:" << std::endl;
    }
    std::cout << "Allocator destructed." << std::endl;
}

Az előbbi int, az utóbbi viszont std::initializer_list<int>. Az egy elemű kapcsos zárójelre külön szabályok vonatkoznak, épp emiatt. Eredetileg ez el is volt rontva a C++11 szabványban, később javították.

#include <vector>
#include <list>
#include <iostream>
 
template <typename C>
class ReverseView {
    private:
        C & container;
    public:
        ReverseView(C & container) : container(container) {}
        
        auto begin() const {
            return std::rbegin(container);
        }
        auto end() const {
            return std::rend(container);
        }
        auto rbegin() const {
            return std::begin(container);
        }
        auto rend() const {
            return std::end(container);
        }
};
 
template <typename C>
auto make_reverse_view(C & container) {
    return ReverseView<C>(container);
}
 
int main() {
    std::vector<int> vec = { 1, 2, 3 };
    for (auto i : make_reverse_view(vec))
        std::cout << i;                 // 3 2 1

    std::list<int> const lis = { 1, 2, 3 };
    for (auto i : make_reverse_view(lis))
        std::cout << i;

    int arr[3] = { 1, 2, 3 };
    for (auto i : make_reverse_view(arr))
        std::cout << i;
}

A megoldás C++14-es, és igényel némi magyarázatot.

A tároló tagfüggvényeinek hívása lényegében triviális; a view.begin() a tároló rbegin() függvényét, a view.rbegin() a tároló begin() függvényét hívja meg, így oda-vissza megfordul a sorrend.

A megoldás konstans tároló esetén is működik. Ilyen esetben ugyanis a make_reverse_view() függvénysablon képes példányosodni: az std::list<int> const listát paraméterként átadva T = std::list<int> const lesz a sablonparaméter, ezért a függvény paramétere konstans referencia, és a ReverseView objektum is konstans referenciát fog tárolni. Az abból meghívott begin/end, illetve rbegin/rend tagfüggvényeknek pedig szokott lenni const overloadja (!), ami a tároló const_iterator belső típusát adja (vagy const_reverse_iterator-t).

Így egyébként a konstans és nem konstans tároló esetén a tagfüggvények auto visszatérési értékei is hol konstans, hol nem konstans iterátorrá vezetődnek le. Ezeket C++98-ban nagyon körülményes lett volna megadni.

Tömbre azért működik a dolog, mert az std::begin() és std::rbegin() és párjaik működnek tömbre is (tömb referenciáját veszik át paraméterként). Tömbökre az std::begin() talán pointert ad (az elvégre is iterátorként használható). Az std::rbegin() pedig bizonyára valamilyen segédosztályból példányosított iterátort, mert ennek a ++ operátora visszafelé kell lépkedjen (--), de ez pointerrel nem lenne megoldható.

Legjobb lenne a make_reverse_view függvénynél C && referenciát használni, de erről a tananyag későbbi részében lesz csak szó.

Python enumerate()-hez hasonló létrehozás, és az iterálás (index; érték) párokat ad:

#include <functional>
#include <iostream>
#include <list>

template <typename T>
class Enumerator {
  private:
    T & container;
    int startidx;

  public:
    /* megjegyzi, melyik tárolóról van szó, és hányadik indexről */
    Enumerator(T & container, int startidx) : container(container), startidx(startidx) {}
    
    /* becsomagolja az iterátort, hozzá tartozóan egy indexszel */
    class Iterator {
      private:
        using Iterator_of_T = decltype(std::begin(container));
        Iterator_of_T it; // iterator_of<container>
        int idx;

      public:
        Iterator(Iterator_of_T it, int idx = 0) : it(it), idx(idx) {}

        /* minimál iterátor interfész, hogy működhessen a range-based for:
         * léptetés, egyenlőségvizsgálat és dereferálás */
        Iterator & operator++() {
            ++it;
            ++idx;
            return *this;
        }
        bool operator==(Iterator const & rhs) const {
            return it == rhs.it;
        }
        bool operator!=(Iterator const & rhs) const {
            return it != rhs.it;
        }
        /* ez főként ez határozza meg az interfészt a range-based for-ban.
         * egy párt ad vissza, .first és .second érik majd el az indexet és az adatot.
         * *it valószínűleg egy referencia, ezért a párban is referencia lesz. */
        auto operator*() const {
            return std::pair<int, decltype(*it)>(idx, *it);
        }
    };

    Iterator begin() {
        return Iterator(std::begin(container), startidx);
    }
    Iterator end() {
        return Iterator(std::end(container));
    }
};

template <typename T>
auto enumerate(T & container, int startidx) {
    return Enumerator<T>(container, startidx);
}

int main() {
    std::list<std::string> szavak = {"alma", "körte", "barack"};
    for (auto p : enumerate(szavak, 1))
        std::cout << p.first << " " << p.second << std::endl;
}

Ugyanez .index() és .value()-képes segédobjektumokkal:

template <typename T>
class Enumerator {
    /* ... */
    class Iterator {
        /* ... */
        auto operator*() const {
            /* a pár helyett egy segédosztály */
            return ValueHelper(*this);
        }
    };

    /* a segédosztály csak eltárolja a fenti iterátort, hogy aztán abból
     * kiolvashassa az elemet és az indexet */
    class ValueHelper {
        private:
            Iterator it;
        public:
            ValueHelper(Iterator it) : it(it) {}
            decltype(auto) value() const {
                return *it.it;
            }
            int index() const {
                return it.idx;
            }
    };
};