Ankündigung

Einklappen
Keine Ankündigung bisher.

Codeschnippsel für C++

Einklappen
Das ist ein wichtiges Thema.
X
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Codeschnippsel für C++

    Hallo Leutz!!

    da ich mir dachte für die C++ Sparte wäre auch eine Rubrik Codeschnippsel nicht verkehrt, poste ich hier mal eine Klasse, die ich vorhin geschrieben habe.

    Ist eine PriorityQueue. Da die STL ja keine Prioritäts-Warteschlange für min-Elemente hergibt und erst recht keine, die sich zur Laufzeit verändern lässt, musste eine kleine Eigenerfindung her.

    Hier der Code:

    PHP-Code:
    #ifndef _PRIORITYQUEUE_H_
    #define _PRIORITYQUEUE_H_

    /////////////////////////////////////////////////////////////
    // A mutable min-priority queue, based on a list. Allows
    // to modify the key of an item on runtime, which eventually
    // will cause a rearrangement.
    /////////////////////////////////////////////////////////////

    #include <list>
    #include <algorithm>
    #include <functional>

    template<typename Ttypename K>
    class 
    PriorityQueue
    {
    public:
        
    struct Element
        
    {
            
    Element(const Tv) : value(v) { }
            
    Element(const Tv, const Kk) : value(v), key(k) { }
            
    bool operator==(const Elementother) const { return (value == other.value); } 
            
    bool operator<(const Elementother) const { return key other.key; }
            
    T value;
            
    K key;
        };

        
    PriorityQueue();
        
    PriorityQueue(const PriorityQueue&);
        
    PriorityQueueoperator=(const PriorityQueue&); 
        ~
    PriorityQueue();
        
    bool empty() const;
        
    size_t size() const;
        
    void clear();
        
    void push(const T&, const K&);
        
    void update(const T&, const K&);
        
    T top() const;
        
    void pop();
        
    void print() const;

    private:
        
    std::list<Elementm_list;
    };

    template<typename Ttypename K>
    PriorityQueue<TK>::PriorityQueue()
    {
    }

    template<typename Ttypename K>
    PriorityQueue<TK>::PriorityQueue(const PriorityQueue<TK>& rhs)
    {
        *
    this rhs;
    }

    template<typename Ttypename K>
    PriorityQueue<TK>& PriorityQueue<TK>::operator=(const PriorityQueue<TK>& rhs)

        if(
    this == &rhs)
            return *
    this

        
    m_list rhs.m_list;

        return *
    this;
    }

    template<typename Ttypename K>
    PriorityQueue<TK>::~PriorityQueue()   
    {
    }

    template<typename Ttypename K>
    bool PriorityQueue<TK>::empty() const
    {
        return 
    m_list.empty();
    }

    template<typename Ttypename K>
    size_t PriorityQueue<TK>::size() const
    {
        return 
    m_list.size();
    }

    template<typename Ttypename K>
    void PriorityQueue<TK>::clear()
    {
        
    m_list.clear();
    }

    template<typename Ttypename K>
    void PriorityQueue<TK>::push(const Tx, const Kkey)
    {
        
    std::list<PriorityQueue::Element>::iterator it;

        for(
    it m_list.begin(); it != m_list.end(); it++) {
            if((*
    it).key key) {
                
    m_list.insert(itElement(xkey));
                return;
            }
        }

        
    m_list.push_back(Element(xkey));
    }

    template<typename Ttypename K>
    T PriorityQueue<TK>::top() const
    {
        return 
    m_list.front().value;
    }

    template<typename Ttypename K>
    void PriorityQueue<TK>::pop()
    {
        
    m_list.pop_front();
    }

    template<typename Ttypename K>
    void PriorityQueue<TK>::update(const Tx, const Kk)
    {
        
    std::list<PriorityQueue::Element>::iterator it;

        
    it std::find(m_list.begin(), m_list.end(), Element(x));

        (*
    it).key k;

        
    m_list.sort();    // Comparisons are performed using operator<
    }

    template<typename Ttypename K>
    void PriorityQueue<TK>::print() const
    {
        
    std::list<PriorityQueue::Element>::const_iterator it;

        for(
    it m_list.begin(); it != m_list.end(); it++) {
            
    std::cout << (*it).value << ":" << (*it).key << std::endl;
        }
    }

    #endif 
    Und eine Demo, wie sie benutzt werden kann. Die Objekte sind Strings, der Key ist ein unsigned int.

    PHP-Code:
    PriorityQueue<std::stringunsigned intpq;

    pq.push("A"3);
    pq.push("C"1);
    pq.push("F"2);
    pq.push("Z"44);
    pq.push("H"32);
    pq.push("Y"111);

    pq.print();

    cout << "Toping..." << endl;

    cout << pq.top() << endl;

    cout << "Poping..." << endl;

    pq.pop();

    pq.print();

    cout << "Changing A to 400..." << endl;

    pq.update("A"400);

    pq.print(); 
    Man kann natürlich auch nur Integer nehmen, dank Template.

    Ist ganz nützlich, wenn man den gängigen Dijkstra Algo implementieren will, da man dort eben eine mutable priority queue braucht.


  • #2
    Gepinnt!

    Kommentar


    • #3
      Hi! werd demnächst noch ein paar Sources nachschieben.

      Kommentar


      • #4
        POSIX Threads - Speisende Philosophen

        Wie versprochen, hier ein anderer Codesnippet

        Diesmal ist es eine lösung für die speisenden philosophen (Dining Philosophers) mit POSIX Semaphoren und threads.

        PHP-Code:
        #include <stdio.h>
        #include <stdlib.h>
        #include <pthread.h>
        #include <signal.h>
        #include <unistd.h>
        #include <semaphore.h>

        #define N  5
        #define ROUNDS  4
        #define THINKTIME   4
        #define EATTIME 2
        #define RIGHT(i) (((i) + 1) % N)
        #define LEFT(i) (((i) == 0) ? N - 1 : (i) - 1)

        typedef enum THINKINGHUNGRYEATINGUNDEFINED phil_state;

        phil_state state[N];
        sem_t mutex;
        sem_t s[N]; // One per philosopher

        void think(int i)
        {
            
        printf("Philosopher %d is thinking!\n"i);
            
        sleep(THINKTIME);
        }

        void eat(int i)
        {
            
        printf("Philosopher %d is eating!\n"i);
            
        sleep(EATTIME);
        }

        void get_forks(int i)
        {
            
        state[i] = HUNGRY;
            while(
        state[i] == HUNGRY) {
                
        sem_wait(&mutex);
                if(
        state[i] == HUNGRY && state[LEFT(i)] != EATING && state[RIGHT(i)] != EATING) {
                        
        printf("Philosopher %d takes fork %d and %d.\n"ii1);
                    
        state[i] = EATING;
                    
        sem_post(&s[i]);    // Increment semaphore
                
        }
                
        sem_post(&mutex);
                
        sem_wait(&s[i]);    // Main control point
            
        }
        }

        void put_forks(int i)
        {
            
        // Atomar operation
            
        sem_wait(&mutex);
            
        state[i] = THINKING;
            if(
        state[LEFT(i)] == HUNGRY)
                
        sem_post(&s[LEFT(i)]);
            if(
        state[RIGHT(i)] == HUNGRY)
                
        sem_post(&s[RIGHT(i)]);
            
        sem_post(&mutex);
        }

        int philosopher(int process)
        {
            
        int i;
            
        printf("Philosopher %d was born!\n"process);

            for(
        0ROUNDSi++) {
                
        think(process);
                
        get_forks(process);
                
        eat(process);
                
        put_forks(process);
            }

            
        pthread_exit((void *)process);
        }

        int main()
        {
            
        int istatus;
            
        pthread_t phil[5];

            
        printf("The Dining-Philosophers Problem.\n");

            
        //  Initialize each semaphore with 0
            
        for(0Ni++) {
                
        state[i] = UNDEFINED;        
                
        sem_init(&s[i], 00);
            }

            
        // Initialize binary semaphore
            
        sem_init(&mutex01);
            
            
        // Create Threads
            
        for(0Ni++) {
                if(
        pthread_create(&phil[i], 0, (void*(*)(void*))philosopher, (void*)i)) {
                    return 
        EXIT_FAILURE;
                }
            }

            
        // Waiting main for terminating philosopher threads
            
        for(0Ni++) {
                
        pthread_join(phil[i], (void**)&status);

                if(
        status == i) {
                    
        printf("Philosopher %d died in peace.\n"i);
                } else {
                    
        printf("Philosopher %d disappeared.\n"i);
                }
            }

            
        // Destroy the semaphores
            
        for(0Ni++) {
                
        sem_destroy(&s[i]);
            }

            
        sem_destroy(&mutex);

            return 
        EXIT_SUCCESS;

        Kommentar

        Lädt...
        X