Solved

re-index vector

Posted on 2013-11-18
11
466 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 34

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
 
LVL 34

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 34

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 34

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 34

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

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

733 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