10

Databases usually look like this

┃Name|Age|..┃ ┠────┼───┼──┨ ┃John│025│..┃ ┃Carl│033│..┃ ┃....│...│..┃

In this case I mean a table with a fixed column size and a variable size of unsorted rows which can be addressed by an id.

Is there a data structure in C++11 (or earlier) that can represent data like this?

I thought of a couple of ways of cheating such a structure, but none of them is perfect.

1. Separate std::vector

std::vector<std::string> name; std::vector<unsigned int> age; // Write name.push_back("John"); age.push_back(25); // Read std::cout << "The first entry is (" << name[0] << " | " << age[0] << ")\n";

Defining a table with many columns takes a lot of markup, though, and writing to it by calling push_back on each std::vector is really tedeous.

2. std::vector of std::tuple

(std::pair would be enough in this case)

std::vector<std::tuple<std::string, unsigned int>> table; // Write table.push_back(std::make_tuple("John", 25)); // Read 1 std::string name; unsigned int age; std::tie(name, age) = table[0]; std::cout << "The first entry is (" << name << " | " << age << ")\n"; // Read 2 enum { NAME = 0, AGE } std::cout << "The first entry is (" << std::get<NAME>(table[0]) << " | " << std::get<AGE>(table[0]) << ")\n";

(Sorry, if I messed something up here; I've known about the existence of std::tuple since yesterday)

This is fine, but reading from it takes a lot of markup, this time, when you have to define new variables that you want to put the values in. You could just do the std::tie to whatever variable you need the values at, but that becomes unreadable. The second method is almost perfect, but using implicit enums is not something I want to do in C++11.

3. std::vector of std::array

enum { NAME = 0, AGE } std::vector<std::array<std::string, 2> table; // Write table.push_back({"John", "25"}); // Read std::cout << "The first entry is (" << table[0][NAME] << " | " << table[0][AGE] << ")\n";

This is also pretty good, but it suffers the same problem as 2.2 did. Also this only allows std::string values. In exchange it offers shorter and nicer syntax, though.

Improve this question
13
  • 2
    std::list<row> which row is a class that represent data that you want to store in each row. Actually it depend on your requirements. Commented Jan 20, 2017 at 16:27
  • 1
    Most databases use the classical B-Tree data structure Commented Jan 20, 2017 at 16:27
  • 7
    Datastructures are tied to algorithms. Talking about what you are going to do to the database is required to determine how you should store it. Even scale matters; a "database" with 10 petabytes of data is going to use a different structure than one with 10 kilobytes. What operations need to be fast? Lookup by name? Lookup by age? How about joining one table to another by name? Is threading a concern? Are the data columns hard typed, or soft typed? How comon are reads and writes? Etc etc. Commented Jan 20, 2017 at 16:30
  • 1
    You might be interested in Boost MultiIndex Commented Jan 20, 2017 at 16:31
  • 1
    There are a whole pile of ways to do this. Which one is best depends on the above questions, and more. Commented Jan 20, 2017 at 19:52

4 Answers 4

Reset to default
4

I suggest a std::vector<Record> to hold your records.

Use std::map<key, vector_index> as an index into your records. This will enable you to access records by different search criteria without sorting the vector all the time.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Why not just std::map<key, Record>?
@kim366: Your suggestion will make an optimized search for the given key, but it will be slower if a record needs to be found by using a different key. With the vector, all records are in one place. One can use multiple maps for different search criteria. See database theory - index tables.
1

One thing you have't considered is using a std::vector of some kind of associative array, be that a std::map or std::unordered_map.

This would allow you to inspect a given item in the vector (or other sequential container) using the database column names

item["Name"] item["Age"]

and so on. You would have to use a variant or something like boost::any for the value, obviously.

If you wish to talk to a database in C++, and know at compile time the type the columns have (as you appear to from your suggestions) it might be worth considering ways to generate code with appropriate structures for you directly from the data base scehema. There are a couple of questions around this topic already here and here. What if the db value is null?

Improve this answer

3 Comments

But a std::map only allows for two values
@kim366 those values are the keys used to retrieve the data stored in the data type, which itself may be a type that can contain multiple varieties of data, as doctorlove explains in the answer.
Map allows lots of values, one corrsponding to each key. And a vlaue could be another map - if you use the right type.
1

Since this question is still seeing activity after 5 years, I will answer it myself with the 5 years of programming experience since then.

There is no point in using std::array or std::tuple to represent a row. A struct is more expressive and has less boilerplate.

The question basically asks the difference between AOS (array of structs), SOA (struct of arrays) and hash maps. The choice between the two depends on what you want to do with the data and how much data there is.

Data is loaded cache lines of 64 bytes with automatic cache preloading when iterating over the data. Since the hash map is non-contiguous and thus cannot take advantage of the caching mechanism, it should only be preferred when individual entries are accessed based on their keys rather than iterating over the entire data set.

The choice between AOS and SOA depends on whether the columns are iterated over individually or together. When iterating separately, by using SOA we can fit more of the same data on the cache line by not looking at the other arrays. For both AOS and SOA, the preferable data structure is std::vector which is a simple contiguous data structure and thus the processor has a lot of information for on-the-fly optimizations.

Improve this answer

Comments

0 
#------------------------------------------- #Try with this piece of code based on <map> #------------------------------------------- #include <iostream> #include <map> using namespace std; //--- class myBook { public: string ISBN; string Title; int Pages; myBook(); myBook(const myBook &); ~myBook(){}; myBook &operator=(const myBook &pTr); int operator==(const myBook &pTr) const; int operator<(const myBook &pTr) const; }; myBook::myBook() { ISBN = ""; Title = ""; Pages = 0; } myBook::myBook(const myBook &copyin) { ISBN = copyin.ISBN; Title = copyin.Title; Pages = copyin.Pages; } ostream &operator<<(ostream &output, const myBook &myBook) { output << myBook.ISBN << ':' << myBook.Title << ':' << myBook.Pages << std::endl; return(output); } myBook& myBook::operator=(const myBook &pTr) { this->ISBN = pTr.ISBN; this->Title = pTr.Title; this->Pages = pTr.Pages; return(*this); } int myBook::operator==(const myBook &pTr) const { if( this->ISBN != pTr.ISBN) return(0); if( this->Title != pTr.Title) return(0); if( this->Pages != pTr.Pages) return(0); return(1); } //--------------------------- main() { map<string, myBook> BooksLibrary; myBook book1; //--- book1.ISBN="1243954-23"; book1.Title="Autobiography by Ben Franklin"; book1.Pages=432; BooksLibrary["0001"] = book1; //--- book1.ISBN="555-USA991"; book1.Title="I Robot by Isac Asimov"; book1.Pages=323; BooksLibrary["0002"] = book1; //--- for( map<string, myBook>::iterator ii=BooksLibrary.begin(); ii!=BooksLibrary.end(); ii++) { std::cout << (*ii).first << "|" << (*ii).second << endl; } //--- return(0); }
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.