For any experts out there. Can you please let me the most efficient way to get the desired output?
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";
}
}
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.