C++ 支持两种索引的排行榜模板

时间：2021-05-30 03:43:36

version 1:

#ifndef RANK_TMPL_H_
#define RANK_TMPL_H_

#include <stdio.h>
#include <stdint.h>
#include <vector>
#include <algorithm>
#include <map>

// RECORD 需要实现小于号 和 .Key() 函数
template<typename RECORD,typename KEY,uint32_t MAX_SIZE>
class VectorBasedRank
{
    typedef std::vector<RECORD> RECORDS;
    typedef std::vector<RECORD*> RECORDS_PTR;
    typedef std::map<KEY, RECORD*> RECORDS_KEYMAP;
public:
    VectorBasedRank(){}
public:
    int32_t Load(const RECORDS &records);
    int32_t Insert(RECORD &record);
    RECORD *FindByIndex(uint32_t index);
    RECORD *FindByKey(uint32_t key);
    void ReSort();
private:
    int32_t InsertNew(RECORD &record);
    int32_t InsertReplace(RECORD &record);
public:
    void DisplaySortedRecords();
    void DisplayMapRecords();
private:
    RECORDS m_records;
    RECORDS_PTR m_sortedRecords;
    RECORDS_KEYMAP m_keyMapRecords;
};

template<typename RECORD, typename KEY, uint32_t MAX_SIZE>
RECORD * VectorBasedRank<RECORD, KEY, MAX_SIZE>::FindByKey(uint32_t key)
{
    RECORDS_KEYMAP::iterator it = m_keyMapRecords.find(key);
    if (it == m_keyMapRecords.end())
    {
        return NULL;
    }
    return it->second;
}

template<typename RECORD, typename KEY, uint32_t MAX_SIZE>
void VectorBasedRank<RECORD, KEY, MAX_SIZE>::ReSort()
{
    std::sort(m_sortedRecords.begin(), m_sortedRecords.end(), Less<RECORD>);
}

template<typename RECORD, typename KEY, uint32_t MAX_SIZE>
RECORD * VectorBasedRank<RECORD, KEY, MAX_SIZE>::FindByIndex(uint32_t index)
{
     && index < m_sortedRecords.size())
    {
        return m_sortedRecords[index];
    }
    return NULL;
}

template<typename RECORD, typename KEY, uint32_t MAX_SIZE>
int32_t VectorBasedRank<RECORD, KEY, MAX_SIZE>::InsertReplace(RECORD &record)
{
    uint32_t lastIndex = m_sortedRecords.size() - ;
    if (Less(m_sortedRecords[lastIndex], &record))
    {
        ;
    }
    m_keyMapRecords.erase(m_sortedRecords[lastIndex]->Key());
    *m_sortedRecords[lastIndex] = record;
    RECORD *ptr = m_sortedRecords[lastIndex];
    std::sort(m_sortedRecords.begin(), m_sortedRecords.end(), Less<RECORD>);
    m_keyMapRecords[m_sortedRecords[lastIndex]->Key()] = ptr;
    ;
}

template<typename RECORD, typename KEY, uint32_t MAX_SIZE>
int32_t VectorBasedRank<RECORD, KEY, MAX_SIZE>::InsertNew(RECORD &record)
{
    m_records.push_back(record);
    uint32_t i = m_records.size() - ;
    RECORD *ptr = &m_records[i];
    m_sortedRecords.push_back(ptr);
    std::sort(m_sortedRecords.begin(), m_sortedRecords.end(), Less<RECORD>);
    m_keyMapRecords[m_records[i].Key()] = ptr;
    ;
}

template<typename RECORD>
bool Less(const RECORD* left, const RECORD* right)
{
    return *left < *right;
}

template<typename RECORD, typename KEY, uint32_t MAX_SIZE>
int32_t VectorBasedRank<RECORD, KEY, MAX_SIZE>::Insert(RECORD &record)
{
    // 元素已满,跟最后一个比较,若新元素小于最后一名,则放弃插入,若大于最后一名,则替换掉最后一名,然后排序
    if (m_records.size() >= MAX_SIZE)
    {
        return InsertReplace(record);
    }
    // 元素未满,直接插入
    else
    {
        return InsertNew(record);
    }
}

template<typename RECORD, typename KEY, uint32_t MAX_SIZE>
int32_t VectorBasedRank<RECORD, KEY, MAX_SIZE>::Load(const RECORDS &records)
{
    m_records.reserve(MAX_SIZE);
    m_sortedRecords.reserve(MAX_SIZE);
    ; i < records.size() && i < MAX_SIZE; ++i)
    {
        m_records.push_back(records[i]);
        RECORD *ptr = &m_records[i];
        m_sortedRecords.push_back(ptr);
        m_keyMapRecords[m_records[i].Key()] = ptr;
    }
    std::sort(m_sortedRecords.begin(), m_sortedRecords.end(), Less<RECORD>);
    ;
}

template<typename RECORD, typename KEY, uint32_t MAX_SIZE>
void VectorBasedRank<RECORD, KEY, MAX_SIZE>::DisplayMapRecords()
{
    for (RECORDS_KEYMAP::const_iterator it = m_keyMapRecords.begin(); it != m_keyMapRecords.end(); ++it)
    {
        it->second->Display();
    }
}

template<typename RECORD, typename KEY, uint32_t MAX_SIZE>
void VectorBasedRank<RECORD, KEY, MAX_SIZE>::DisplaySortedRecords()
{
    ; i < m_sortedRecords.size(); ++i)
    {
        m_sortedRecords[i]->Display();
    }
}

#endif

测试代码:

#include <stdint.h>
#include <stdio.h>
#include "rank_tmpl.h"

struct StarInfo
{
    int32_t roleid, likes;
    StarInfo() :likes(), roleid(){}
    StarInfo(int32_t like) :likes(like),roleid( - like){}
    bool operator < (const StarInfo &info) const
    {
        return likes < info.likes;
    }
    int32_t Key()
    {
        return roleid;
    }
    void Display()
    {
        printf("roleid = %d,likes = %d\n", roleid, likes);
    }
};

int32_t main()
{
    StarInfo infos[] = { , , , ,  };
    std::vector<StarInfo> vecInfos(infos, infos + ]));
    VectorBasedRank<StarInfo, int32_t, > ranks;
    ranks.Load(vecInfos);
    ranks.DisplaySortedRecords();
    ranks.DisplayMapRecords();
    printf("------------\n");
    StarInfo *p = ranks.FindByKey();
    p->likes += ;
    ranks.DisplaySortedRecords();
    ranks.DisplayMapRecords();
    printf("------------\n");
    ranks.ReSort();
    ranks.DisplaySortedRecords();
    ranks.DisplayMapRecords();
    getchar();
    ;
}

version 2:

#ifndef RANK_TMPL_H_
#define RANK_TMPL_H_

#include <stdio.h>
#include <stdint.h>
#include <vector>
#include <algorithm>
#include <map>

// RECORD 需要实现小于号 和 .Key() 函数
template<typename RECORD, typename KEY, uint32_t INIT_SIZE, bool ASC = true>
class VectorBasedRank
{
    typedef std::vector<RECORD> RECORDS;
    typedef std::vector<uint32_t> RECORDS_SORTED_INDEX;
    typedef std::map<KEY, uint32_t> RECORDS_KEY_MAP;
public:
    VectorBasedRank(){ m_capacity = INIT_SIZE; }
public:
    int32_t Load(const RECORDS &records);
    uint32_t Size(){ return m_records.size(); }
    uint32_t Capacity(){ return m_capacity; }
    void SetCapacity(uint32_t capacity){ m_capacity = capacity; }
    int32_t Insert(const RECORD &record);
    uint32_t AdjustIndex(uint32_t index);
    uint32_t Adjust();
    RECORD *RecordByIndex(uint32_t index);
    RECORD *RecordByKey(const KEY &key);
public:
    void DisplaySortedRecords();
    void DisplayMapRecords();
private:
    bool Less(const uint32_t left, const uint32_t right, const RECORDS &records);
    void QSort(int32_t start, int32_t end, RECORDS_SORTED_INDEX &recordIndexs, const RECORDS &records);
    uint32_t AdjustBack(uint32_t index);
    uint32_t AdjustFront(uint32_t index);
private:
    uint32_t m_capacity;
    RECORDS m_records;
    RECORDS_SORTED_INDEX m_sortedRecords;
    RECORDS_KEY_MAP m_keyMapRecords;
};

template<typename RECORD, typename KEY, uint32_t INIT_SIZE, bool ASC /*= true*/>
RECORD * VectorBasedRank<RECORD, KEY, INIT_SIZE, ASC>::RecordByKey(const KEY &key)
{
    typename RECORDS_KEY_MAP::iterator it = m_keyMapRecords.find(key);
    if (it != m_keyMapRecords.end())
    {
        if (it->second < m_records.size())
        {
            return &m_records[it->second];
        }
    }
    return NULL;
}

template<typename RECORD, typename KEY, uint32_t INIT_SIZE, bool ASC /*= true*/>
RECORD * VectorBasedRank<RECORD, KEY, INIT_SIZE, ASC>::RecordByIndex(uint32_t index)
{
    if (index < m_sortedRecords.size())
    {
        if (m_sortedRecords[index] < m_records.size())
        {
            return& m_records[m_sortedRecords[index]];
        }
    }
    return NULL;
}

template<typename RECORD, typename KEY, uint32_t INIT_SIZE, bool ASC /*= true*/>
uint32_t VectorBasedRank<RECORD, KEY, INIT_SIZE, ASC>::Adjust()
{
    uint32_t index = ;
    )
    {
        ], m_sortedRecords[index], m_records))
        {
            AdjustIndex(index);
            AdjustIndex(index + );
        }
        ++index;
    }
    ;
}

template<typename RECORD, typename KEY, uint32_t INIT_SIZE, bool ASC /*= true*/>
uint32_t VectorBasedRank<RECORD, KEY, INIT_SIZE, ASC>::AdjustIndex(uint32_t index)
{
    )
    {
        return AdjustFront(index);
    }
    )
    {
        return AdjustBack(index);
    }
    else
    {
        ], m_records))
        {
            return AdjustFront(index);
        }
        ], m_sortedRecords[index], m_records))
        {
            return AdjustBack(index);
        }
    }
    return index;
}

template<typename RECORD, typename KEY, uint32_t INIT_SIZE, bool ASC /*= true*/>
uint32_t VectorBasedRank<RECORD, KEY, INIT_SIZE, ASC>::AdjustBack(uint32_t index)
{
     && Less(m_sortedRecords[index + ], m_sortedRecords[index], m_records))
    {
        uint32_t tmp = m_sortedRecords[index];
        m_sortedRecords[index] = m_sortedRecords[index + ];
        m_sortedRecords[index + ] = tmp;
        ++index;
    }
    return index;
}

template<typename RECORD, typename KEY, uint32_t INIT_SIZE, bool ASC /*= true*/>
uint32_t VectorBasedRank<RECORD, KEY, INIT_SIZE, ASC>::AdjustFront(uint32_t index)
{
     && Less(m_sortedRecords[index], m_sortedRecords[index - ], m_records))
    {
        uint32_t tmp = m_sortedRecords[index];
        m_sortedRecords[index] = m_sortedRecords[index - ];
        m_sortedRecords[index - ] = tmp;
        --index;
    }
    return index;
}

// 返回值:
// -1        :    表示插入失败
// 非负数    :    表示新插入的元素的排名
template<typename RECORD, typename KEY, uint32_t INIT_SIZE, bool ASC /*= true*/>
int32_t VectorBasedRank<RECORD, KEY, INIT_SIZE, ASC>::Insert(const RECORD &record)
{
    // 超出容量上限
    if (m_records.size() >= Capacity())
    {
        ;
    }
    // Key 重复
    if (m_keyMapRecords.find(record.Key()) != m_keyMapRecords.end())
    {
        ;
    }
    m_records.push_back(record);
    uint32_t index = m_records.size() - ;
    m_sortedRecords.push_back(index);
    m_keyMapRecords[record.Key()] = index;
    return AdjustIndex(index);
}

template<typename RECORD, typename KEY, uint32_t INIT_SIZE, bool ASC /*= true*/>
void VectorBasedRank<RECORD, KEY, INIT_SIZE, ASC>::QSort(int32_t start, int32_t end, RECORDS_SORTED_INDEX &recordIndexs, const RECORDS &records)
{
    if (start >= end){ return; }
    uint32_t i = start, j = end;
    uint32_t tmp = recordIndexs[i];
    while (i < j)
    {
        while (i < j && Less(tmp, recordIndexs[j], records)){ --j; }
        if (i < j)
        {
            recordIndexs[i] = recordIndexs[j];
            ++i;
        }
        while (i < j && !Less(tmp, recordIndexs[i], records)){ ++i; }
        if (i < j)
        {
            recordIndexs[j] = recordIndexs[i];
            --j;
        }
    }
    recordIndexs[i] = tmp;
    QSort(start, i - , recordIndexs, records);
    QSort(i + , end, recordIndexs, records);
}

template<typename RECORD, typename KEY, uint32_t INIT_SIZE, bool ASC /*= true*/>
bool VectorBasedRank<RECORD, KEY, INIT_SIZE, ASC>::Less(const uint32_t left, const uint32_t right,const RECORDS &records)
{
    if (left < records.size() && right < records.size())
    {
        if (ASC)
        {
            return records[left] < records[right];
        }
        else
        {
            return !(records[left] < records[right]);
        }
    }
    return false;
}

template<typename RECORD, typename KEY, uint32_t INIT_SIZE, bool ASC /*= true*/>
int32_t VectorBasedRank<RECORD, KEY, INIT_SIZE, ASC>::Load(const RECORDS &records)
{
    m_records.clear();
    m_sortedRecords.clear();
    m_keyMapRecords.clear();
    m_records.reserve(INIT_SIZE);
    m_sortedRecords.reserve(INIT_SIZE);
    ; i < records.size(); ++i)
    {
        m_records.push_back(records[i]);
        m_sortedRecords.push_back(i);
        m_keyMapRecords[records[i].Key()] = i;
    }
    QSort(, m_sortedRecords.size() - , m_sortedRecords, m_records);
    ;
}

template<typename RECORD, typename KEY, uint32_t INIT_SIZE, bool ASC /*= true*/>
void VectorBasedRank<RECORD, KEY, INIT_SIZE, ASC>::DisplayMapRecords()
{
    for (typename RECORDS_KEY_MAP::const_iterator it = m_keyMapRecords.begin(); it != m_keyMapRecords.end(); ++it)
    {
        m_records[it->second].Display();
    }
    printf("------\n");
}

template<typename RECORD, typename KEY, uint32_t INIT_SIZE, bool ASC /*= true*/>
void VectorBasedRank<RECORD, KEY, INIT_SIZE, ASC>::DisplaySortedRecords()
{
    ; i < m_sortedRecords.size(); ++i)
    {
        m_records[m_sortedRecords[i]].Display();
    }
    printf("------\n");
}

#endif
#include <stdint.h>
#include <stdio.h>
#include "rank.h"

struct StarInfo
{
    int32_t roleid, likes;
    StarInfo() :likes(), roleid(){}
    StarInfo(int32_t like) :likes(like), roleid( - like){}
    bool operator < (const StarInfo &info) const
    {
        return likes < info.likes;
    }
    int32_t Key() const
    {
        return roleid;
    }
    void Display()
    {
        printf("roleid = %d,likes = %d\n", roleid, likes);
    }
};

int32_t main()
{
    StarInfo infos[] = { , , , , , , , , , , , ,  };
    StarInfo infos2[] = { , ,  };
    std::vector<StarInfo> vecInfos(infos, infos + ]));
    std::vector<StarInfo> vecInfos2(infos2, infos2 + ]));
    VectorBasedRank<StarInfo, int32_t, , true> ranks;
    ranks.Load(vecInfos);
    ranks.DisplaySortedRecords();
    // ranks.DisplayMapRecords();
    ; i < ]); ++i)
    {
        StarInfo *pInfo = ranks.RecordByKey(infos[i].Key());
        if (pInfo)
        pInfo->likes *= ;
        pInfo->Display();
        printf("------\n");
        ranks.Adjust();
        ranks.DisplaySortedRecords();
        // ranks.DisplayMapRecords();
    }
    getchar();
    ;
}

相关文章