Solved

re-index vector

Posted on 2013-11-18
11
484 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

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

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

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
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 be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

705 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