C++ Vector of class - finding the max subindex for a index

Question

For any experts out there. Can you please let me the most efficient way to get the desired output?

• Want to fetch the Index/SubIndex values only for the highest subindex records
• Want to get only the index/Subindex for any given input.
• Want to fetch the Indexes for a given Range

Have around 2 million Indexes and for each index there are around 100 SubIndexes. All of them are inserted sequentially(Both Indexes and SubIndexes). Trying to find an efficient way to fetch the desired data. Even I am open to use a different data structure as needed as well as use C++20 Ranges as needed.

Thank you in advance. Would post the final solution if I could find one.

#include <iostream>
#include <vector>

class testclass {
public:
   int Index;
   int SubIndex;
   int Data;
   // There are few more elements
};

class DataObject {
   testclass Rec;
};

std::vector<testclass> v;


int main()
{
   testclass Rec;

   Rec.Index = 1;
   Rec.SubIndex = 0;
   Rec.Data = 1;
   v.emplace_back(Rec);

   Rec.Index = 2;
   Rec.SubIndex = 0;
   Rec.Data = 1;
   v.emplace_back(Rec);

   Rec.Index = 2;
   Rec.SubIndex = 1;
   Rec.Data = 2;
   v.emplace_back(Rec);

   Rec.Index = 3;
   Rec.SubIndex = 1;
   Rec.Data = 4;
   v.emplace_back(Rec);

   // Q1 - How to print only the records with highest SubIndex -  Desired output -  1 0 1, 2 1 2 & 3 1 4
   // Q2 - How to fetch the Record for a given Index (to fetch the record of the highest subIndex value for a given Index - example Fetch Index 2 --- Output -- 2 1 2 (Highest SubIndex value)
   // Q3 - How to fetch the records for a given Index Range with Highest SubIndex - Example - Fetch the Indexes from 2 to 3 - Output - 2 1 2 & 3 1 4

   for(auto &i : v) {
       std::cout << i.Index << " " << i.SubIndex << i.Data << "\n";
   }
}

Answer 1

We can use a transparent compare to find the range of testclass instances that share an Index, and the end of that range is the highest SubIndex

It would actually be easier if your data was ordered in the opposite direction, so we can take the first element of the range, but we can use reverse iterators to do that.

struct compare_index {
    using is_transparent = void;
    bool operator()(testclass lhs, testclass rhs)
    {
        return lhs.index > rhs.index;
    }
    bool operator()(int lhs, testclass rhs)
    {
        return lhs > rhs.index;
    }
    bool operator()(testclass lhs, int rhs)
    {
        return lhs.index > rhs;
    }
};

// can swap std::vector for another range here
std::vector<testclass> highest_subindices()
{
    if (v.empty()) { return {}; }
    std::vector<testclass> result;

    auto range = std::equal_range(v.rbegin(), v.rend(), v.back(), compare_index{});
    while (range.second != range.first)
    {
        result.push_back(*range.first);
        range = std::equal_range(range.second, v.rend(), *range.second, compare_index{});
    }
    return result;
}

testclass * highest_subindex(int Index)
{
    auto range = std::equal_range(v.rbegin(), v.rend(), Index, compare_index{});
    return range.first != range.second ? &*range.first : nullptr;
}

// can swap either std::vector for another range here
std::vector<testclass *> highest_subindices(std::vector<int> Indices)
{
    std::vector<testclass> result(Indices.size());
    std::transform(Indices.begin(), Indices.end(), result.begin(), highest_subindex);
    return result;
}

Answer 2

As I understand it, you need a quick search and at the same time keep the sequence of objects.

For this, you can use additional Associative containers. Sample code below:

#include <iostream>
#include <vector>
#include <map>


class testclass {
public:
    int Index;
    int SubIndex;
};

class RecQuery
{
public:

    /**
     * @brief      Pushes a record.
     *
     * @param[in]  Rec   The record.
     */
    void PushRec(const testclass& Rec)
    {
        m_mapIndexToSubIndexToRecordIndex[Rec.Index][Rec.SubIndex] = m_vecRecords.size();
        m_vecRecords.emplace_back(Rec);
    }

    /**
     * @brief      Finds a record.
     *
     * @param[in]  Index  The index.
     *
     * @return     The reference to the record.
     */
    testclass& FindRecord(const int Index)
    {
        const std::map<int, size_t>& subIndexToRecordMap = m_mapIndexToSubIndexToRecordIndex.at(Index);
        return m_vecRecords[std::rbegin(subIndexToRecordMap)->second];
    }


    /**
     * @brief      Visits the Index/SubIndex values only for the highest subindex records.
     *
     * @param      visitor   The visitor.
     *
     * @tparam     FVisitor  The type of visitor.
     */
    template<typename FVisitor>
    void VisitHighestSubIndexes(FVisitor&& visitor)
    {
        for (const auto& [Index, SubIndexToRecIndex] : m_mapIndexToSubIndexToRecordIndex)
        {
            auto maxIndexIt = std::rbegin(SubIndexToRecIndex);
            visitor(m_vecRecords[maxIndexIt->second]);
        }
    }

    /**
     * @brief      Visits all records in the Index range. [from, to]
     *
     * @param[in]  from      The begin of the index range.
     * @param[in]  to        The end of the index range.
     * @param      visitor   The visitor.
     *
     * @tparam     FVisitor  The type of visitor.
     */
    template<typename FVisitor>
    void VisitRangeByIndex(const int from, const int to, FVisitor&& visitor)
    {
        const auto fromIt = m_mapIndexToSubIndexToRecordIndex.find(from);
        if (fromIt == std::end(m_mapIndexToSubIndexToRecordIndex))
        {
            throw std::out_of_range{ "Index not found." };
        }
        auto toIt = m_mapIndexToSubIndexToRecordIndex.find(to);
        if (toIt == std::end(m_mapIndexToSubIndexToRecordIndex))
        {
            throw std::out_of_range{ "Index not found." };
        }

        // If you do not need to visit the last element of the back range, delete this line.
        ++toIt;

        for (auto it = fromIt; it != toIt; ++it)
        {
            visitor(m_vecRecords[std::rbegin(it->second)->second]);
        }
    }


    /**
     * @brief      Returns an iterator pointing to the first record.
     *
     * @return     Iterator to the element.
     */
    auto begin() const noexcept
    {
        return std::begin(m_vecRecords);
    }

    /**
     * @brief      Returns an iterator pointing to the last record.
     *
     * @return     Iterator to the element.
     */
    auto end() const noexcept
    {
        return std::end(m_vecRecords);
    }

private:
    std::vector<testclass> m_vecRecords;
    // for more performance can you use boost::container::flat_map.
    // boost::container::flat_map<int, boost::container::flat_map<int, size_t>> m_mapIndexToSubIndexToRecordIndex;
    std::map<int, std::map<int, size_t>> m_mapIndexToSubIndexToRecordIndex;
};

int main()
{
    RecQuery recQuery;
    testclass Rec;

    Rec.Index = 1;
    Rec.SubIndex = 0;
    recQuery.PushRec(Rec);

    Rec.Index = 2;
    Rec.SubIndex = 0;
    recQuery.PushRec(Rec);

    Rec.Index = 2;
    Rec.SubIndex = 1;
    recQuery.PushRec(Rec);


    // Q1 - How to print only the records with highest SubIndex(Highest) -  Desired output -  1 0 & 2 1
    std::cout << "Q1 ===========================================" << std::endl;
    recQuery.VisitHighestSubIndexes([](testclass& rec)
        {
            std::cout << "Index: " << rec.Index << " Subindex: " << rec.SubIndex << std::endl;
        });
    std::cout << "Q2 ===========================================" << std::endl;
    // Q2 - How to get only a specific Index/Subindex(highest) for a given input value  - 2 1
    testclass rec2 = recQuery.FindRecord(2);
    std::cout << "Index: " << rec2.Index << " Subindex: " << rec2.SubIndex << std::endl;

    // Q3
    std::cout << "Q3 ===========================================" << std::endl;
    recQuery.VisitRangeByIndex(1, 2, [](testclass& rec)
        {
            std::cout << "Index: " << rec.Index << " Subindex: " << rec.SubIndex << std::endl;
        });
    std::cout << "===========================================" << std::endl;


    for (auto& i : recQuery)
    {
        std::cout << i.Index << " " << i.SubIndex << "\n";
    }

    return 0;
}

I used std::map, but it is better if using boost::flat_map. The boost::flat_map example is commented out.