Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

re-index vector

Posted on 2013-11-18
11
Medium Priority
?
511 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 896 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 896 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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 35

Assisted Solution

by:sarabande
sarabande earned 1104 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 896 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 35

Assisted Solution

by:sarabande
sarabande earned 1104 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 35

Assisted Solution

by:sarabande
sarabande earned 1104 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 35

Assisted Solution

by:sarabande
sarabande earned 1104 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 35

Assisted Solution

by:sarabande
sarabande earned 1104 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 896 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

Important Lessons on Recovering from Petya

In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.

Question has a verified solution.

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

This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
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.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
Suggested Courses

618 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