이렇게 구현하면 위험할까요? ^^;;

빈번하게 일정한 범위(색인기반)의 데이터를 추가 및 삭제, 그리고 검색이 이루어지는 프로그램을 구현하는 중입니다.
처음에는 std::map 을 고려하였으나, 데이터의 범위가 넓어지면 넓어질수록 추가연산에서 시간이 오래걸리더군요.

어느정도 예상은 하였지만, 이마저도 개선할 수 있는 방법이 없을까.. 고민끝에, 다음과 같이 다소 엉뚱하게
구현하게 되었습니다.

참고로, UserData의 크기는 50 ~ 100 byte 정도입니다.

[1차 시도]

UserData bigDataArray[655360]; // 배열의 Bound는 0부터, 최대 655360까지 보장해야함.

while ( 1 )
{
// Index에 의한 참조로, 검색속도가 보장됨.
UserData &usrData = bigDataArray[ GetUserDataIndex() ];
DoSomething ( userData);
}

위와 같이 구현하게 되면, 컴파일은 되나, Stack Over Flow가 발생하면서, 프로그램이 죽더군요. -_-;;;

[2차 시도]

UserData *pBigDataArray = new UserData[655360];

while ( 1 )
{
// Index에 의한 참조로, 검색속도가 보장됨.
UserData &usrData = pBigDataArray[ GetUserDataIndex() ];
DoSomething ( userData);
}

위와 같이 구현하게 되면, 컴파일 및 실행까지 잘됩니다. 하지만, 무언가 위험해 보이기도 하고, 다소, 무식하게
힙을 사용하는건 아닌지.. ^^

색인의 범위는 0 ~ 655360, 각각의 데이터의 크기는 100 바이트 내/외, 빈번한 추가/삭제/검색시...
위와 같이 구현하면 위험할까요?

조언 부탁드리겠습니다. ^^/