Which data structure is better for an array of std string

Question

I need a structure as follow:

The structure must hold fixed size std::strings so that the number of its elements is finit (100 - 10000000).

I would like to be able to access each element randomly as follow:

std::string Temp = MyStrcuture[i];

or

MyStrcuture[i] = std::string Temp;

I have to use the fastest structure with no (possibly) memory leak.

Which one is better for me?

std::string* MyStrcuture = new std::string[Nu_of_Elements];
std::queue< std:string> MyStrcuture(Nu_of_Elements);
std::vector< std:string> MyStrcuture(Nu_of_Elements);
boost::circular_buffer< std::string> MyStrcuture(Nu_of_Elements);
Your suggestion?

I don't think you'll get what you want if I'm reading this correctly. Even with reserved storage, the `std::string`'s data is not necessarily contained within the `std::string`.You will likely wind up with what is essentially an array of pointers to data stored elsewhere. — user4581301, Nov 02 '16 at 15:22
`MyStrcuture[i] = std::string Temp;` is really nontrivial to implement. — L. F., Jul 18 '19 at 02:30

score 12 · Accepted Answer · edited May 23 '17 at 12:10

12

std::vector< std:string> MyStrcuture(Nu_of_Elements);

Vector is the best fit for your requirements. It supports index-based element access as the elements are stored in continuous memory addresses, and has flexibility with size.

std:string* MyStrcuture = new std::string[Nu_of_Elements]; No

C++ STL vector vs array in the real world
std::queue< std:string> MyStrcuture(Nu_of_Elements); No

How do I get the nth item in a queue in java?
Index-based element access is not supported.
std::vector< std:string> MyStrcuture(Nu_of_Elements); Yes

Clean-up : The vector's destructor automatically invokes the destructor of each element in the vector.
Boost::circular_buffer< std::string> MyStrcuture(Nu_of_Elements); No

Same reason as second one. Know more

edited May 23 '17 at 12:10

Community

1
1

answered Nov 02 '16 at 06:12

Saurav Sahu

13,038
6
64
79

2

Instead of `std::vector`, `std::vector>` makes more sense from a memory perspective. – themagicalyang Nov 02 '16 at 06:37
1

@themagicalyang: yes and no, since it would require a huge block of contiguous memory, which may not be available in e.g. a fragmented 32 bit address space. – Matteo Italia Nov 02 '16 at 06:49
@MatteoItalia I concur. But if that is the case, then some error checking for allocation is due. But contiguous memory memory would still be my first choice. If not fall back, on a different allocation pattern. – themagicalyang Nov 02 '16 at 06:54

score 4 · Answer 2 · edited May 23 '17 at 11:54

Well, since your string have fixed size, if you don't have dedicated requirement when processing string and have enough free memory for contiguous allocation. You can use std::array< char, 400 > or std::unique_ptr< char* > instead of std::string.

You have to manage memory in C way. consider smart pointer
std::queue doesn't have random access, Access c++ queue elements like an array
std::vector is suitable if the number of string will be changed. However, the clear() function just call the destructor of elements, not free vector allocated memory (you can check the capacity after clear).
After reading boost documentation. The random access circular buffer is suitable if your number of string have an upper limit (that you said 10 millions). But its a waste of memory if actually you have so few strings. So I suggest to use with smart pointer.
If your number of string are fixed and unchanged from the beginning. You can have a look at C++11 array container

Denis Sheremet · Answer 3 · 2016-11-02T10:09:25.527

0

If number of elements and length is fixed and memory is critical, you may consider using plain char array, which provides minimal memory overhead and fast accessibility. Your code will look like this:

char* MyStructure = new char[n * 401];
memset(MyStructure, 0, n * 401);

std::string Temp = MyStructure[i * 401]; // Get value
strcpy(MyStructure[i * 401], Temp.c_str()); // Put value

401 here is for 400 bytes of your string and 1 trailing zero.

edited Nov 02 '16 at 10:09

answered Nov 02 '16 at 06:27

Denis Sheremet

2,453
2
18
34

2

This is the proper solution. Why would one go for dynamically allocated std::string when the strings are fixed sized and can be held in character array. More benefits to this is fast access, and no memory hops. Though I would use `std::array` for the string instead. So this could turn out to be `std::vector` – themagicalyang Nov 02 '16 at 06:33
1

I'm sure you mean a *trailing* zero. – celtschk Nov 02 '16 at 06:39
"1 leading zero"? Did you mean zero-termination? – khôi nguyễn Nov 02 '16 at 06:41
You are not allocating the actual memory for the characters - there you allocated just an array of pointers. That `strcpy` is going to segfault badly. – Matteo Italia Nov 02 '16 at 06:47

Which data structure is better for an array of std string

3 Answers3