1

As stated in the answer to my question, I will use vectors just to resize to N, read and write the nth element where n < N. If n is too close to N then I will create another vector of size N+M and copy all the elements from 1st vector to the 2nd and delete the 1st one. So if I am doing the memory management and no insertion and deletion take place, are there any advantages of using a vector instead of an array particularly for this case?

P.S. Resizing and block copying will be needed rarely.

EDIT: As David Rodríguez - dribeas demanded, it is a technical analysis program. Historical stock prices are kept as OHLC bars in vectors. So I really need to store the elements in vectors. Also there are some other calculation classes called indicators, do calculations based on prices of stocks. When a new price arrived via tcp, first, the stock updates its bars and immediately calls all of its related indicators' calculate methods, saying, "ok guys my nth bar has been updated at this spesific time. Go calculate yourself." All operations are task based, that is, a stock never updates itself before finishing the last update and similarly an indicator never do a calculation while last one is going on. One task at a time. And if new updates keep coming too quickly, they can be cached as tasks. So a stock can wait for its last update to finish and an indicator can similarly store its tasks while its been calculated, BUT a stock must not wait for its indicators to finish their work. This is where the problem begins. If an update arrives, a stock firstly looks its bar vector size and checks if it must be resized. If needed it resizes its vectors, while there may be some indicators still working prior to the previous update. An indicator may reach its stock data, as the data may being resized. Up to now I do not have any problems because indicator calculations have been done very very quickly. But I am concerned. As a solution a stock can generate a second larger bar vector and tell its indicators they can reach to the second vector for upcoming calculations. Eventually, after a couple of second, all the access to the first vector perishes and it can be deleted grafully.

Improve this question
6
  • As I explained in comments to my answer, you can't insert elements into a vector from one thread and read elements from the same vector in another thread. Vector reallocation is not the only problem; the internal bookkeeping performed by the vector is also a problem and you can't make any assumptions about what that involves. Once you give access to the vector to the consumer threads, you cannot modify it again unless either (a) you synchronize access to it, which you said you don't want do do, or (b) you get all of the consumers to stop accessing the vector, which is probably difficult. Commented Dec 4, 2010 at 1:01
  • For optimal performance in a multithreaded environment, you may want to consider implementing your own container. Commented Dec 4, 2010 at 1:03
  • @James McNellis: What do you mean by internal bookkeeping? Commented Dec 4, 2010 at 1:04
  • @Bahadir Turkmen: The vector has to keep track of its size and capacity somehow. There are two typical implementations of this: one uses two integers that store size and capacity; the other uses two pointers, one to the element one past the end of the current data (indicating the size) and one to the element one past the end of the underlying array (indicating the capacity). The size is modified by any insertion into the vector. The size may also be read by any member function of vector, including operator[]. Commented Dec 4, 2010 at 1:06
  • @James McNellis: I see, so I need a container that does not check for its size when reach its elements. Also I guarantee that the required index is in the range of [0,n] myself. So I do not need to use a vector at all. I can easily devise an array for grabbing its elements, even for multithreded case. Do you think so? Commented Dec 4, 2010 at 1:14

4 Answers 4

Reset to default
2

It sounds like the structure you really want is std::deque which can be appended in ammortized constant time.

Actually, the resizing strategy is exactly the one already used by std::vector. In fact the precise strategy it uses means that this operation is essentially O(1), but only in terms of many appends over a long period of time. At any rate, there doesn't seem to be any reason to reinvent the wheel on this. just use std::vector.push_back() or std::queue.push_back()

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

2 Comments

operator[] of std::deque is slower than of std::vector. Since read and write operations are really used frequently in my application, I do not want to lose perfomance. Also said that there may be some dangerous situations involved in multithreaded scenarios with deque.
The cost of appending to an std::deque is constant time, while the cost of appending to an std::vector is amortized constant time.
1
  1. Why you just not resize existing vector?
  2. If you can't resize existing vector then you can use array for it i don't see any pros for using std:vector in this case, for copy you can use memcopy
  3. You can use array and resize her with realloc.
Improve this answer

5 Comments

Because while one thread is resizing the vector, another consumer thread may reach the vector.
It depends on what you want to store in the container, but in general you cannot use memcpy with anything that is not a POD type --anything with non-trivial constructor or destructor.
@David Rodríguez - dribeas: I will store just numerical types.
@David Rodríguez: you dont have right, you thinking about object like a some lenght data of array but is not a true, not exactly, for accessing her you have only pointer to place where this object starting, and with her you want do what you want, nobody give you orders for copy object, only copy address of her starting place (this is pointers you can read about her on google).
At any rate, you can also use memcpy with vectors (might be slightly better performing than std::copy: std::vector<int> a; /* ... */ std::vector<int> b( 2*a.size() ); memcpy( &b[0], &a[0], a.size()*sizeof a[0] );
0

I read the original question, and I think that it might be worth handling the multithreading so that you have a guarantee that no thread will be accessing the container when you grow it.

On the particular question at hand, unless there is a strong reason not to do it, I would always go for an std::vector over an array, if for no other reason just because many operations are already implemented and you do not need to manually manage the memory.

There are anyway, a lot of information that you have not provided in either question, as to what the usage pattern is, what the consumer threads are doing with the data (do you really need to keep the elements in the vector? could the threads just pick a set of values and work with that?), what synchronization mechanisms are in place (how do consumers get notified that there is extra data in the container, when does extra data arrive..) All this questions together with their answers might provide hints to other designs.

Improve this answer

Comments

0

I'd say that in your case, at worst, the vector's going to be no better than a dynamically allocated raw array. Probably, it'll be more convenient.

As for your dilemma, this sounds like something that would be way easier with implicit memory management. You could store your incoming data in shared pointers. Then, indicators grab a shared pointer to the data they need whenever they start calculating. If new data comes in that would require invalidating the old data, just replace the shared pointer in the stock containing the old data with a shared pointer containing the new data. Any indicator still using the old data could continue using it because it still has a shared pointer to the old data (preventing the old data from being cleaned up), and the old data would get cleaned up when all the indicators using the data finished and reset their shared pointers.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.