Solved

re-index vector

Posted on 2013-11-18
11
462 Views
Last Modified: 2013-11-18
I am try to reading a set of records from a file to a vector of data  structures.

for example

DataSturcture {

string Name;
int ID;
string AlternateName;

}

I like create a index of each member so I don't have to search everytime I try to access them.  How would I do that?  Is any class in std library or boost can do that?
0
Comment
Question by:tommym121
  • 5
  • 4
  • 2
11 Comments
 
LVL 86

Assisted Solution

by:jkr
jkr earned 224 total points
ID: 39656558
By what field would you like to index them? A std::map is what comes to my mind when thinking about this, i.e. if you want the ID to be the index, you could

#include <map>
using namespace std;

//...
DataSturcture {

string Name;
int ID;
string AlternateName;
};

map<int,DataStructure&> mapIDtoDataStructure;

while(!infile.eof()) {

  DataStructure ds;

  ReadDataStructure(ds);

  // enter to map based on ID

  mapIDtoDataStructure.insert(map::int,DataStructure&>::value_type(ds.ID,da));
}

// ...

// sample lookup for ID = 42
int id = 42;
DataStructure tmp = mapIDtoDataStructure[id];

Open in new window


See also http://en.cppreference.com/w/cpp/container/map
0
 
LVL 86

Assisted Solution

by:jkr
jkr earned 224 total points
ID: 39656572
Ooops, correction, that should be

#include <map>
using namespace std;

//...
DataSturcture {

string Name;
int ID;
string AlternateName;
};

map<int,DataStructure> mapIDtoDataStructure;

while(!infile.eof()) {

  DataStructure ds;

  ReadDataStructure(ds);

  // enter to map based on ID

  mapIDtoDataStructure.insert(map::int,DataStructure>::value_type(ds.ID,ds));
}

// ...

// sample lookup for ID = 42
int id = 42;
DataStructure tmp = mapIDtoDataStructure[id];
                                            

Open in new window


In this case you would not even need a vector and all the structs would be stored in a map instead of that. However, if you still want to keep the vector, my first comment (with a map of references) would still work, yet the storing would be a bit different:

#include <map>
using namespace std;

//...
DataSturcture {

string Name;
int ID;
string AlternateName;
};

map<int,DataStructure&> mapIDtoDataStructure;
vector<DataStructure> vStructs;

// fill vector...

for(vector<DataStructure>::iterator i = vStructs.begin(); i != vStructs.end(); ++i) {
  // enter to map based on ID

  mapIDtoDataStructure.insert(map::int,DataStructure&>::value_type(i->ID,*i));
}

// ...

// sample lookup for ID = 42
int id = 42;
DataStructure tmp = mapIDtoDataStructure[id];
                                            

Open in new window

0
 

Author Comment

by:tommym121
ID: 39656601
jkr,

If I understand what you mean.  I should put the data sturcture into map.  How can I optimize the retrieve of the record,  Sometime I need to use the Name, other time to use the ID or the AlternateName.

I am trying to borrow the same concept in database, i.e. to use each of the field as a key to index so I can simply

Now with you example I can do mapIDTodDataStructure, But I would also like to perform
& mapNameTodDataStructure (Name)
& mapAlternateNameToDataStucture (AlternateName)

Do I have to read the file 3 times or a better way to handle this?

Thanks
0
 
LVL 32

Assisted Solution

by:sarabande
sarabande earned 276 total points
ID: 39656621
you can use a std::vector where you store all records. then have three maps for each search field which would point into the vector.

note, a std::map has a unique key. if you have duplicate values you need tu use a multimap or better a map to vector.

Sara
0
 
LVL 86

Assisted Solution

by:jkr
jkr earned 224 total points
ID: 39656635
No, you could just use 3 maos for that:

#include <map>
using namespace std;

//...
DataSturcture {

string Name;
int ID;
string AlternateName;
};

map<int,DataStructure&> mapIDtoDataStructure;
map<string,DataStructure&> mapNameToDataStructure ;
map<string,DataStructure&> mapAlternateNameToDataStructure ;

vector<DataStructure> vStructs;

// fill vector...

for(vector<DataStructure>::iterator i = vStructs.begin(); i != vStructs.end(); ++i) {
  // enter to map based on ID

  mapIDtoDataStructure.insert(map::int,DataStructure&>::value_type(i->ID,*i));
  mapNametoDataStructure.insert(map::string,DataStructure&>::value_type(i->Name,*i));
  mapAlternateNametoDataStructure.insert(map::string,DataStructure&>::value_type(i->AlternateName,*i));
}
                           

Open in new window


This way, you have all maps covering all lookup aspects, and the storage will only happen in the vector - the maps only hold references.
0
Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

 
LVL 32

Assisted Solution

by:sarabande
sarabande earned 276 total points
ID: 39656675
note, the struct may not use std::string if you use it with a binary write or binary read. a std::string has a pointer internally which is not valid anymore when read from file. you may use fixed char buffers instead.


struct DataStructure 
{
      char name[30];
      int    id;
      char alternate[30];
};

std::vector<DataStructure> data;
std::map<std::string, std::vector<int> > nameMap;
std::map<std::string, std::vector<int> > alternateMap;
std::map<int, std::vector<int> > idMap;  // I assume the id is unique

DataStructure ds = { 0 };
int count = 0;
std::ifstream infile(szpath, std::ios::binary | std::ios::in); 
while (infile.read((char*)&ds, sizeof(ds)))
{
      data.push_back(ds);
      idMap[ds.id] = count;
      nameMap[ds.name].push_back(count);
      alternateMap[ds.alternate].push_back(count);
      count++;
}
infile.close();

Open in new window


Sara
0
 
LVL 32

Assisted Solution

by:sarabande
sarabande earned 276 total points
ID: 39656704
you also can use one map for the nameMap and alternateMap using the above technique.

to search for a 'name' you would do:

std::map<std::string, std::vector<int> >::iterator f;

if ((f = nameMap.find("John")) != nameMap.end())
{
    std::vector<int> & refs = f->second;
    for (int i =0; i < (int)refs.size(); ++i)
    {
          std::cout << "ID: " << data[refs[i]].id" << std::endl;
    }
}

Open in new window


Sara
0
 
LVL 32

Assisted Solution

by:sarabande
sarabande earned 276 total points
ID: 39656716
map<int,DataStructure&> mapIDtoDataStructure;

it is not possible to store a reference to class object in a map. you either have to use a pointer or an index to the all-data-vector (as in my sample code).

Sara
0
 
LVL 32

Assisted Solution

by:sarabande
sarabande earned 276 total points
ID: 39656769
should be

// the map maps an ID to an index in the vector of all records
std::map<int, int > idMap;  // I assume the id is unique

Open in new window


Sara
0
 
LVL 86

Accepted Solution

by:
jkr earned 224 total points
ID: 39656770
That is correct - yoet an iterator to the vector works (and this corrects a whole bunch of typos as well):

#include <map>
#include <vector>
#include <string>
using namespace std;

//...
struct DataStructure {

string Name;
int ID;
string AlternateName;
};

vector<DataStructure> vStructs;


map<int,vector<DataStructure>::iterator> mapIDToDataStructure;
map<string,vector<DataStructure>::iterator> mapNameToDataStructure ;
map<string,vector<DataStructure>::iterator> mapAlternateNameToDataStructure ;


void main () {

// fill vector...

for(vector<DataStructure>::iterator i = vStructs.begin(); i != vStructs.end(); ++i) {
  // enter to map based on ID

  mapIDToDataStructure.insert(map<int,vector<DataStructure>::iterator>::value_type(i->ID,i));
  mapNameToDataStructure.insert(map<string,vector<DataStructure>::iterator>::value_type(i->Name,i));
  mapAlternateNameToDataStructure.insert(map<string,vector<DataStructure>::iterator>::value_type(i->AlternateName,i));
}

}
                           
                                            

Open in new window

0
 

Author Closing Comment

by:tommym121
ID: 39657046
Thanks. I learn a lot. Thank you again.
0

Featured Post

What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

747 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now